I am studying graph algorithms.
I need a database of graphs on which I can test my algorithms.
Where can I find a reliable database of graphs of all kinds?
Thanks!
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI am studying graph algorithms.
I need a database of graphs on which I can test my algorithms.
Where can I find a reliable database of graphs of all kinds?
Thanks!
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.
There's a nice collection of data on regular graphs at Markus Meringer's webpage.
Sage (http://www.sagemath.org/) provides access to a large collection of graphs, as well as tools for working with them.
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."
Discrete ZOO should also be mentioned here. As of 2 March 2018, it reports to host 212238 graphs.
Two such websites I am aware of are:
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.
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
Some hint useful in year 2020: google: "graph dataset", but NOT "graph database" (which means somewhat different thing).
Google will give a lot. Let me also give some direct links with some comments:
Let me also mention that modern software tools have ready to use graph examples or can easily generate them. For example
Expanders Provides explicit constructions of expander graphs. margulis_gabber_galil_graph(n[, create_using]) Returns the Margulis-Gabber-Galil undirected MultiGraph on n^2 nodes. chordal_cycle_graph(p[, create_using]) Returns the chordal cycle graph on p nodes. Random Graphs: erdos_renyi_graph(n, p[, seed, directed]) Returns a Gn,p random graph, also known as an Erdős-Rényi graph or a binomial graph. binomial_graph(n, p[, seed, directed]) Returns a Gn,p random graph, also known as an Erdős-Rényi graph or a binomial graph. newman_watts_strogatz_graph(n, k, p[, seed]) Returns a Newman–Watts–Strogatz small-world graph. watts_strogatz_graph(n, k, p[, seed]) Returns a Watts–Strogatz small-world graph. connected_watts_strogatz_graph(n, k, p[, …]) Returns a connected Watts–Strogatz small-world graph. random_regular_graph(d, n[, seed]) Returns a random d-regular graph on n nodes. barabasi_albert_graph(n, m[, seed]) Returns a random graph according to the Barabási–Albert preferential attachment model. dual_barabasi_albert_graph(n, m1, m2, p[, seed]) Returns a random graph according to the dual Barabási–Albert preferential attachment model.
So one might generate/explore/plot graphs with few lines of code, for example: