0
$\begingroup$

Is it possible to find all simple directed graphs given a set of nodes? I was thinking of just finding all permutations of an adjacency list of lists. For example, given nodes A, B I can have the adjacency lists:

A | \
B | \

A | B
B | \

A | \
B | A

A | B
B | A

The constraints are: no self loops, simple graph, directed edges

I can probably code up the way I described above, but I wanted to make sure doing this wasn't hitting some sort of fundamental boundary of graph theory or cs.

I was also thinking about using an adjacency matrix where I can store the matrix in row-major or column-major order in a uni-dimensional array of 0s and 1s - permute the uni-dimensional array (which has to be possible) and rebuild the NxM matrix to represent the graph that way.

Apologies that this is more of a discussion than a question, but any advice would be much appreciated!

$\endgroup$
  • 2
    $\begingroup$ Do you want a set of all non-isomorphic directed graphs? Or all directed graphs, period? You do realize that the number grows exponentially and so this won't be feasible unless the number of vertices is very small, right? $\endgroup$ – D.W. Mar 31 '17 at 7:27
  • $\begingroup$ What are non-isomorphic directed graphs? Yes the number of vertices will be on the order of 10 $\endgroup$ – Carpetfizz Mar 31 '17 at 13:00
  • $\begingroup$ With 10 vertices, there are $2^{90}$ possible directed graphs -- way too many to enumerate all of them within your lifetime. $\endgroup$ – D.W. Mar 31 '17 at 17:14
  • $\begingroup$ @D.W. ah, that kills my idea then, thanks for letting me know $\endgroup$ – Carpetfizz Mar 31 '17 at 17:15
2
$\begingroup$

Any of those will work, as long as you view the graphs $A\to B$ and $B\to A$ as different graphs. If you view them as being the same graph, then things are much more complex as you have to either do isomorphism testing or somehow enumerate in a way that doesn't produce isomorphic graphs more than once.

The fundamental barrier is that, in an $n$-vertex digraph has $n(n-1)$ possible edges, each of which may be present or not, so there are $2^{n(n-1)}$ possible digraphs on $n$ vertices. Your program must output all of these which is going to be infeasible for all but small graphs.

$\endgroup$
  • $\begingroup$ Thanks. Do you mind explaining isomorphism in graphs? The number of vertices I'm dealing with will be very small $\endgroup$ – Carpetfizz Mar 31 '17 at 13:01
  • $\begingroup$ @Carpetfizz Wikipedia. $\endgroup$ – David Richerby Mar 31 '17 at 14:18
  • $\begingroup$ I think you mean $2^{n(n-1)}$ different graphs. $\endgroup$ – D.W. Mar 31 '17 at 17:14
  • $\begingroup$ @D.W. Oops. Fixed. (And I changed the reasoning, since it's easier to justify the correct answer that way.) $\endgroup$ – David Richerby Mar 31 '17 at 17:19
2
$\begingroup$

Enumerate all possible adjacency matrices. A matrix is a possible adjacency matrix for a directed graph if it is a $n\times n$ matrix with 0 or 1 in every entry, except that the diagonal has to be all zeros. It is easy to enumerate them, because this is equivalent to enumerating all bit-strings of length $n(n-1)$.

Consequently, there are $2^{n(n-1)}$ directed graphs. Thus unless $n$ is very small, the number of such graphs is enormous -- too many to enumerate all of them.

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