Welcome to MathOverflow

Question

8

4

I am studying graph algorithms.

I need database of graphs on which I can test my algorithms.

Where can I find reliable database of graphs of all kinds?

Thanks!

flag	asked May 6 2010 at 17:09 Pratik Deoghare 265●8

6

You might want to be more specific. Do you want all graphs on $n$ vertices or less? Do you want pathological examples? How do you want your graphs presented to you? Graphically? An edge list? As an input to a specific piece of software. SAGE has large classes of graphs built-in. – Cam McLeman May 6 2010 at 17:42

One option is to generate random graphs -- the usefulness of this would depend on the specific application in mind. – Douglas S. Stones May 7 2010 at 1:41

grshutt · Accepted Answer · 2010-05-06 18:24:14Z UTC

8

You might want to look at Donald Knuth's Stanford GraphBase: A Platform for Combinatorial Computing (1994, 2009) and the accompanying website.

See also The Stony Brook Algorithm Repository.

answered May 6 2010 at 18:24

grshutt
480●5●7

Noah Snyder · Answer 2 · 2010-05-06 18:29:01Z UTC

5

There's a nice collection of data on regular graphs at Markus Meringer's webpage.

answered May 6 2010 at 18:29

Noah Snyder
11.6k●1●27●72

Chris Godsil · Answer 3 · 2010-05-07 00:54:57Z UTC

3

Sage (http://www.sagemath.org/) provides access to a large collection of graphs, as well as tools for working with them.

answered May 7 2010 at 0:54

Chris Godsil
5,901●1●8●24

Douglas S. Stones · Answer 4 · 2010-05-07 01:33:27Z UTC

nauty comes with some additional programs. In particular, you might be interested in geng. As the website says "geng can generate non-isomorphic graphs very quickly. There are also generators for bipartite graphs, digraphs, and multigraphs."

James · Answer 5 · 2010-05-07 20:19:59Z UTC

Maple 13 or newer has a GraphTheory package that has a graph generator which allows you to generate all non-isomorphic graphs satisfying various criteria. You can use that to produce graphs and export them in various formats. In addition, you can produce random graphs using this package.

Yaroslav Bulatov · Answer 6 · 2010-07-15 20:46:20Z UTC

1

Here's a collection of 3054 "standard named graphs" from Mathematica's GraphData collection http://yaroslavvb.com/upload/graphs2.txt

It's one graph per line, description followed by pairs of adjacent vertices

answered Jul 15 2010 at 20:46

Yaroslav Bulatov
1,120●4●17

Where on the internet I can find database of graphs?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

6 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.