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.stack.imgur.com/pAE51.png

Improve this question
$\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$
    – LarrySnyder610
    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$
    – Ramin Fakhimi
    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$
    – Michael Feldmeier
    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$
    – Mark L. Stone
    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$
    – LarrySnyder610
    Jun 22, 2019 at 15:33

4 Answers 4

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This seems more like a comment than an answer. OTOH the OP accepted it, so... $\endgroup$
    – LarrySnyder610
    Jun 22, 2019 at 15:35
  • $\begingroup$ I think the link leads to a good source of materials for this question. $\endgroup$
    – Ramin Fakhimi
    Jun 23, 2019 at 15:57
4
$\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

```
Improve this answer
$\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/

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

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

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