Finding all possible directed graphs given a number of vertices

Question

Is it possible to find all possible directed graphs given a pair of vertices and the information that an edge exists between them? For example if we know the vertices with edge pairs like

1 2
2 3
1 3

The possible directed graphs will be:

1→2, 2→3, 1→3 
1→2, 2→3, 3→1 
1→2, 3→2, 1→3 
1→2, 3→2, 3→1 
2→1, 2→3, 1→3 
2→1, 2→3, 3→1 
2→1, 3→2, 1→3 
2→1, 3→2, 3→1

What data-structure to be used here to work with? What can be the working logic?

I was thinking of using adjacency matrix data structure and compute all possible adjacency matrix. Each adjacency matrix will represent a graph. We can use the graph as and when needed for tasks like checking whether cycle is present or not etc.

Apologies that this is more of a discussion than a programming question, but any help will be appreciated

Each edge can extend one direction or the other, so looks like the answer is 2^n where n is the number of edges, assuming each edge is mono directional. — user5994461
@user5994461 I actually didn't ask for the number of graphs obtained but the graphs so obtained. — Hamsa
This is not clear. "all possible directed graphs" that have what to do with a given "pair of vertices and the information that an edge exists between them"? Also your words disgree with your example input which is a set of vertex pairs, not a graph & a vertex pair. We can guess what you're trying to say & ask for confirmation but you should find how to say it. Use enough words, sentences & references to parts of examples to clearly & fully say what you mean. Otherwise you can't search for, ask about or code solutions. — philipxy
What is your question? Discussions are off-topic. Asking for "approaches" is off-topic. You give no criteria to choose one approach over another. You are basically asking us to solve your problem without any effort by you. Work out as much of a solution as you can & ask one specific question re the first place you get stuck. — philipxy

Heather Guarnera Heather Guarnera · Accepted Answer · 2019-08-02T20:54:09

You could maintain one undirected graph data structure G and work with the knowledge that the existence of an edge (u,v) means that there is only one directed edge in a particular instance of digraph possibility D.

If you want to maintain all possible digraphs separately, you would need 2^m many of them, where m is the number of edges. If the vertices and edges are always the same and only the direction is the invariant, then you could maintain 2^m bit-strings, each of length m. Each bit has a 0 or 1 depending on whether the edge (u,v) it corresponds to is u-->v or v<--u. Use the bit string to give direction to the undirected graph suggested above. You just need to generate all 2^m bit strings. Not very efficient... but you can't do better if you need to work with all possibilities.

You could use the bit string to construct a digraph. But, it would be more memory efficient at least to maintain only one bit-string per 'graph' rather than repeating the entire graph data structure with only directional changes. Record bit strings in a hash table: use each edge as a key and then bit value 0/1 depending on direction. Any graph traversal of one of the many possible digraphs D works on undirected G. Then in constant time you can check for incident (undirected) edges of a vertex, which are outgoing/incoming in D. So traversals can occur just as quickly by maintaining only 1 graph object and 1 bit hash table of size 2^m (rather than 2^m graph objects).

Finding all possible directed graphs given a number of vertices

1 Answers