1

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.

Nicolas FRANCOIS
  • 113
  • 5
  • 1
    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. – D.W. Aug 06 '20 at 00:01
  • Cross-posted: https://cseducators.stackexchange.com/q/6454/1106, https://cstheory.stackexchange.com/q/47342/5038, https://cs.stackexchange.com/q/128968/755. Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). – D.W. Aug 06 '20 at 05:18
  • @D.W. : As I said : shortest paths, and flows. – Nicolas FRANCOIS Aug 07 '20 at 00:47
  • 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. – D.W. Aug 07 '20 at 01:22
  • Hi Nicolas, welcome to [cseducators.se]! 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? – thesecretmaster Aug 08 '20 at 14:25

1 Answers1

3

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

Jon Guiton
  • 523
  • 2
  • 6