How to generate all directed permutations of an undirected graph?

Viewed 133

I am looking for a way to generate all possible directed graphs from an undirected template. For example, given this graph "template":

Undirected template graph. A triangle missing an edge

I want to generate all six of these directed versions:

All versions of the graph with directed edges

In other words, for each edge in the template, choose LEFT, RIGHT, or BOTH direction for the resulting edge.

There is a huge number of outputs for even a small graph, because there are 3^E valid permutations (where E is the number of edges in the template graph), but many of them are duplicates (specifically, they are automorphic to another output). Take these two, for example:

Two isomorphic options

I only need one.


I'm curious first: Is there is a term for this operation? This must be a formal and well-understood process already?

And second, is there a more efficient algorithm to produce this list? My current code (Python, NetworkX, though that's not important for the question) looks like this, which has two things I don't like:

  1. I generate all permutations even if they are isomorphic to a previous graph
  2. I check isomorphism at the end, so it adds additional computational cost
Results := Empty List
T := The Template (Undirected Graph)

For i in range(3^E):
    Create an empty directed graph G
    convert i to trinary
    For each nth edge in T:
        If the nth digit of i in trinary is 1:
            Add the edge to G as (A, B)
        If the nth digit of i in trinary is 2:
            Add the edge to G as (B, A)
        If the nth digit of i in trinary is 0:
            Add the reversed AND forward edges to G
   
    For every graph in Results:
        If G is isomorphic to Results, STOP
    Add G to Results
0 Answers
Related