Re: [igraph] subgraph enumeration given a labeled directed graph.

[Tamás Nepusz]

> Now the problem I meet is that I would like to enumerate all the
> connected subgraphs or connected subgraphs with smaller node size (like
> 1--5) given a graph which is directed and uniquely labelled. It's
> unknown whether there are circles in the graphs.
> 
> Do you have any idea how I can solve this problme?
The only idea that pops into my mind is as follows.

Suppose you want to generate all directed graphs with n vertices. Such graphs 
may have at most m = n*(n-1) edges if we don't consider loop or multiple edges. 
Enumerate all the numbers from 0 to 2^m-1. For each number, find out its binary 
form. Each digit in the binary form corresponds to one edge in the directed 
graph, and you can simply add the edge if the corresponding binary digit is 1. 
Then you have to check for the connectedness of each such graph explicitly. 
This is quite a time consuming process and the only shortcut that you may take 
easily is to count the number of 1s in the binary representation; if it is less 
than n-1, you can be sure that the graph is not connected, and if it is larger 
than (n-1)*(n-2), you can be sure it is connected. For n=5, you have to check 
all numbers from 0 to 2^30-1.

There are probably better graph enumeration algorithms than this simple one, 
but you have to search the literature yourself as none of them are implemented 
in igraph.

Also note that the number of such graphs will be huge. Even for undirected 
graphs, the number of all the connected graphs with n vertices is given by 
sequence A001187 in OEIS:

http://oeis.org/A001187

Even for n = 8, you have 251 million such graphs -- and these are only the 
undirected ones.

Best,
T.