1
$\begingroup$

I hope I'm addressing the right community. I was redirected here from CS.SE. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...). The idea is for them (and me) :

  1. to test their code on small examples (running code with the processor they have between the ears ;-), but not completely trivial,
  2. to test their code on a bunch of larger examples (say from 10 to 10000 nodes) to find the complexity from experience, and compare it with what they would expect from their algorithms.

The algorithms I want them to study :

  • Dijkstra,
  • Bellman-Ford,
  • Floyd-Warshal
  • Ford-Fullkerson (for the good ones).

There are a few samples on the companion site of the ALGS4 course from R. Sedgewick (Shortest Paths), it could be OK for benchmarking, but I would like some more datas, encoded in this simplest way (or easily convertible). Examples don't have to contain background (I mean, if there is one, it can be interesting, but then I would have to strip the original datas from all the commentaries...).

Maybe someone here is aware of some samples and could point me to it.

Thanks in advance.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ You don't list any requirements on the graphs (apparently any will do), so we have no way to evaluate answers -- I'm not sure that kind of question is a good fit for the Stack Exchange model. You could just generate your own graphs randomly. $\endgroup$
    – D.W.
    Aug 6, 2020 at 0:01
  • $\begingroup$ Cross-posted: cseducators.stackexchange.com/q/6454/1106, cstheory.stackexchange.com/q/47342/5038, cs.stackexchange.com/q/128968/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Aug 6, 2020 at 5:18
  • $\begingroup$ @D.W. : As I said : shortest paths, and flows. $\endgroup$
    – Nicolas FRANCOIS
    Aug 7, 2020 at 0:47
  • $\begingroup$ Yes, I saw that, and I stand by my comment. That doesn't provide any requirements - you can compute shortest paths on any weighted graph (and flows on any graph, if you pick a pair of source and destination edge). If you have no requirements, generating random graphs should meet the requirements. $\endgroup$
    – D.W.
    Aug 7, 2020 at 1:22
  • $\begingroup$ Hi Nicolas, welcome to Computer Science Educators! I think that as it currently stands, your question is a little to broad for us to give a helpful answer. Could you edit to possibly describe the project so that we'll have a better idea of the kind of graphs you're looking for? $\endgroup$
    – thesecretmaster ♦
    Aug 8, 2020 at 14:25

1 Answer 1

Reset to default
3
$\begingroup$

enter image description hereFor any problems involving graphs for which you need test data you can use Knuth's less well known work 'The Stanford Graph Base'. This includes many data sets designed to test all kinds of graph problems. The materials are described at https://www-cs-faculty.stanford.edu/~knuth/sgb.html and are available for download at ftp://ftp.cs.stanford.edu/pub/sgb/sgb.tar.gz

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Perfect answer given the vagueness of the question!! Nice! $\endgroup$
    – Ben I. ♦
    Nov 29, 2020 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.