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!

Improve this question
$\endgroup$
4
  • 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. ♦
    Commented Mar 31, 2017 at 7:27
  • $\begingroup$ What are non-isomorphic directed graphs? Yes the number of vertices will be on the order of 10 $\endgroup$
    – Carpetfizz
    Commented Mar 31, 2017 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. ♦
    Commented Mar 31, 2017 at 17:14
  • $\begingroup$ @D.W. ah, that kills my idea then, thanks for letting me know $\endgroup$
    – Carpetfizz
    Commented Mar 31, 2017 at 17:15

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. Do you mind explaining isomorphism in graphs? The number of vertices I'm dealing with will be very small $\endgroup$
    – Carpetfizz
    Commented Mar 31, 2017 at 13:01
  • $\begingroup$ @Carpetfizz Wikipedia. $\endgroup$
    – David Richerby
    Commented Mar 31, 2017 at 14:18
  • $\begingroup$ I think you mean $2^{n(n-1)}$ different graphs. $\endgroup$
    – D.W. ♦
    Commented Mar 31, 2017 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
    Commented Mar 31, 2017 at 17:19
3
$\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.

Improve this answer
$\endgroup$

Your Answer

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

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