2
$\begingroup$

I am looking for an efficient algorithm to generate all of the unique graphs for a given number of nodes.

For small instances, the total number of graphs are as follows:

n=2 G=2

n=3 G=4

n=4 G=11

n=5 G=34

I used the complementarity property of graphs to make it easier to enumerate all of them.

enter image description here

[3]: https://i.sstatic.net/pAE51.png

$\endgroup$
9
  • $\begingroup$ What’s your question exactly? Are you asking for a way to do this? It seems you have a way in mind already. $\endgroup$ Commented Jun 20, 2019 at 21:39
  • $\begingroup$ I am looking for a method to track all the generated graphs. A simple algorithm is to generate all $2^{{n}\choose{2}}$ cases. But, as the number of nodes increases, the difference between the total number of unique graphs and that number super exponentially grows. I have some basic idea but for large n's it doesn't work since some weird cases happen. I wanted to realize whether there exists any method for it or not. The method should ensure that at each step we have a new graph. I am not sure but I think realizing the similarity of two unlabeled and undirected graphs is an NP-hard problem. $\endgroup$ Commented Jun 21, 2019 at 1:44
  • $\begingroup$ Maybe I am missing something obvious, but what is the connection to OR? this should be in the CS or math stackexchange. $\endgroup$ Commented Jun 21, 2019 at 7:18
  • 1
    $\begingroup$ @Michael Feldmeier Graph theory is part of/aplicable to OR. True it could be postedoin another SE site. But that is ture for almost every OR SE question. I take a big, flexible, and evolving tent view of OR, and apparently have a bigger and more flexible tent view of OR than you do (and not just based on this question).. $\endgroup$ Commented Jun 21, 2019 at 11:52
  • $\begingroup$ To me this question is on the borderline. I think math or CS might have been a better fit for this question, but I think it's close enough that I'm not planning to cast a close vote (or, probably, an open vote, if it gets closed). I think graph theory is close enough to OR (especially since there is an algorithmic aspect to this question) that it can be in scope. $\endgroup$ Commented Jun 22, 2019 at 15:33

4 Answers 4

7
$\begingroup$

See http://oeis.org/A000088, which gives a different number (34) for n = 5.

$\endgroup$
2
  • 1
    $\begingroup$ This seems more like a comment than an answer. OTOH the OP accepted it, so... $\endgroup$ Commented Jun 22, 2019 at 15:35
  • $\begingroup$ I think the link leads to a good source of materials for this question. $\endgroup$ Commented Jun 23, 2019 at 15:57
5
$\begingroup$

There is a program that generates those graphs for the small number of vertices. http://users.cecs.anu.edu.au/~bdm/data/graphs.html

The following code converts the file with the g6 format to an array (it is written in python).

import numpy as np

file_contents = open("graph3c.txt", "r")

lines = file_contents.readlines()

for line in lines:

    n = ord(line.split()[0][0]) - 63
    h = ''

    l = n - 1
    for i in range(1,l):
        temp = bin(ord(line.split()[0][i])-63)[2:]
        if len(temp) < 6:
            for k in range(6 - len(temp)):
                h = h + '0'
        h = h + temp
    
     
    A = [[0]*n for j in range(n)]
    k = 0;
    for i in range(1,n):
        for j in range(0,i):
            A[i][j] = int(h[k])
            A[j][i] = A[i][j]
            k = k+1

```   
$\endgroup$
2
$\begingroup$

I've seen several researchers using the NAUTY package to generate all graphs of a given size:

https://pallini.di.uniroma1.it/

$\endgroup$
1
$\begingroup$

The GraphsInGraphs contains a database of all undirected graphs with up to 10 nodes, and code to generate larger ones. One of the original goals was to detect sub-graphs and isomorphisms.

You can find the mathematical background here: https://www.gerad.ca/fr/papers/G-2016-10

$\endgroup$

Your Answer

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

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