1
$\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

$\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 '19 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$ Jun 21 '19 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$ Jun 21 '19 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$ Jun 21 '19 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 '19 at 15:33
7
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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