2

Possible Duplicate:
Data for testing graph algorithms

I recently developed a parallel algorithm to solve the vertex cover problem.
now i need some graphs so i can test the speed of my algorithm vs the sequential code.
where can i find graphs? i am looking for something similar to this text file: 

3 3
1 0
1 2
0 2

the first 2 numbers (3 and 3) states that there are 3 vertices and 3 edges in the graph. following this line is 3 edges.

Community
  • 1
scatman
  • 311
  • 1
  • 3
  • 4
  • 1
    Hi @scatman: I'm not so sure that your question is within scope, so you may want to try other SE sites as well. – Hsien-Chih Chang 張顯之 May 17 '11 at 11:15
  • 1
    Related MO question Database of graphs – Pratik Deoghare May 17 '11 at 13:42
  • You can also generate random graphs, using packages such as Jung or R or probably any graph library. This would give you some flexibility, as you could vary the kind of graph generated by changing the various parameters available, including the kind of graph. – Dave Clarke May 17 '11 at 15:29
  • 1
    (The other question specifically asks for directed graphs, but I think it would be a good idea to slightly edit the question to make it more general, and then merge the answers. Also, it might be a good idea to CW the question.) – Jukka Suomela May 17 '11 at 16:47
  • @Jukka, I have edited the other question (and in fact was going to merge the questions) but then I thought that it might not be a good thing (there is no way to reverse a merge) since this question is asking for graphs for a specific problem. (ps: as result of my closing as duplicate and reopening the question the close votes for this question has been lost. I should have been more careful. Sorry.) – Kaveh May 18 '11 at 04:34
  • 1
    Hi scatman, please read the FAQ. Specifying the format of the input is making your question too localized IMO, so I would suggest that edit that part. Also take a look at the question linked above by Jukka to see if the answers for that question would also answer your question (in which case I can merge the questions so all of the answers are in one place). Thanks. – Kaveh May 18 '11 at 04:36
  • Check out the answers for the related questions http://cstheory.stackexchange.com/questions/3409/graphs-from-real-life-problems http://cstheory.stackexchange.com/questions/739/data-for-testing-graph-algorithms – Snowie May 17 '11 at 13:03

3 Answers3

8

If you want challenging instances for the vertex cover problem:

http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
3

You can check out the graphs at NetWiki. Of course, you'll have to sort out the formatting yourself.

James King
  • 2,613
  • 18
  • 25
2

Here's a collection of graphs that we used for analyzing a vertex cover heuristic: http://www.ru.is/kennarar/eyjo/vertexcover.html

You can download a zipfile containing all the graphs here: http://www.ru.is/kennarar/eyjo/vertexcover/graphs.zip

The format is not exactly as you specified but it's close enough.

Eyjolfur Ingi Asgeirsson
  • 21
  • 2