igraph-help
[Top][All Lists]

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

 From: Tamás Nepusz Subject: Re: [igraph] subgraph enumeration given a labeled directed graph. Date: Thu, 19 Apr 2012 22:37:20 +0200

```> 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.

```