Ask Your Question
1

Finding all digraphs up to isomorphism for a given undirected graph using Sage

asked 2022-04-16 19:05:57 +0200

klaaa gravatar image

updated 2022-04-16 22:31:40 +0200

Given an undirected finite connected graph (without loops). I have two questions:

  1. Is there an easy way using Sage to obtain all ways to make it a directed graph (such that for each edge there is now one directed edge) up to isomorphism of graphs?

  2. Is there an easy way using Sage to obtain all ways to make it a directed graph up to isomorphism of graphs and such that additionally the two opposite directed graphs get also identified?

Interesting examples might be graphs of Dynkin type such as E_8.

For $A_3$ for example in the first question there are 3 ways to make it into a directed graph. In the second question there are two ways for $A_3$.

So the input should be a undirected finite connected graph and the output all possible orientations up to graph isomorphisms (and maybe up to taking the opposite graph as in question 2).

edit retag flag offensive close merge delete

3 Answers

Sort by ยป oldest newest most voted
4

answered 2022-04-17 10:46:31 +0200

rburing gravatar image

updated 2022-04-17 11:05:13 +0200

An efficient way is to use directg from nauty, which is accessible in SageMath through digraphs.nauty_directg. The option -o serves to orient each edge in only one direction.

$D_4$ orientations up to isomorphism:

sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (1, 3)],
 [(0, 1), (1, 2), (3, 1)],
 [(0, 1), (2, 1), (3, 1)],
 [(1, 0), (1, 2), (1, 3)]]

$E_6$ orientations up to isomorphism:

sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in digraphs.nauty_directg(G, options='-o')]
[[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4)],
 [(0, 1), (1, 2), (2, 3), (2, 5), (4, 3)],
 [(0, 1), (1, 2), (2, 3), (3, 4), (5, 2)],
 [(0, 1), (1, 2), (2, 3), (4, 3), (5, 2)],
 [(0, 1), (1, 2), (2, 5), (3, 2), (3, 4)],
 [(0, 1), (1, 2), (2, 5), (3, 2), (4, 3)],
 [(0, 1), (1, 2), (3, 2), (3, 4), (5, 2)],
 [(0, 1), (1, 2), (3, 2), (4, 3), (5, 2)],
 [(0, 1), (2, 1), (2, 3), (2, 5), (3, 4)],
 [(0, 1), (2, 1), (2, 3), (2, 5), (4, 3)],
 [(0, 1), (2, 1), (2, 3), (3, 4), (5, 2)],
 [(0, 1), (2, 1), (2, 3), (4, 3), (5, 2)],
 [(0, 1), (2, 1), (2, 5), (3, 2), (3, 4)],
 [(0, 1), (2, 1), (3, 2), (3, 4), (5, 2)],
 [(1, 0), (1, 2), (2, 3), (2, 5), (3, 4)],
 [(1, 0), (1, 2), (2, 3), (3, 4), (5, 2)],
 [(1, 0), (1, 2), (2, 5), (3, 2), (3, 4)],
 [(1, 0), (1, 2), (3, 2), (3, 4), (5, 2)],
 [(1, 0), (2, 1), (2, 3), (2, 5), (3, 4)],
 [(1, 0), (2, 1), (2, 3), (3, 4), (5, 2)]]

Here's how you could quotient by your equivalence relation:

def orientations_up_to_opposites(G):
    results = []
    for g in digraphs.nauty_directg(G, options='-o'):
        g_canon = g.canonical_label()
        g_opposite_canon = DiGraph([(b,a) for a,b in g.edges(labels=False)]).canonical_label()
        if not (g_canon in results or g_opposite_canon in results):
            results.append(g_canon)
    return results

$D_4$ orientations up to isomorphism and opposites:

sage: G = Graph({1: [2], 2: [3,4]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 3), (3, 1), (3, 2)], [(0, 3), (1, 3), (2, 3)]]

$E_6$ orientations up to isomorphism and opposites:

sage: G = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: [g.edges(labels=False) for g in orientations_up_to_opposites(G)]
[[(0, 4), (3, 2), (4, 5), (5, 1), (5, 3)],
 [(0, 5), (1, 3), (3, 4), (4, 2), (4, 5)],
 [(0, 5), (1, 4), (2, 3), (3, 5), (5, 4)],
 [(0, 4), (1, 3), (1, 5), (4, 5), (5, 2)],
 [(0, 4), (1, 3), (3, 5), (4, 5), (5, 2)],
 [(0, 5), (1, 4), (2, 3), (2, 5), (4, 5)],
 [(0, 5), (1, 4), (2, 3), (3, 5), (4, 5)],
 [(0, 5), (1, 4), (2, 3), (2, 4), (2, 5)],
 [(0, 5), (1, 4), (2, 3), (3, 4), (3, 5)],
 [(0, 5), (1, 3), (1, 4), (4, 2), (4, 5)]]
edit flag offensive delete link more

Comments

Thanks, this looks like a very elegant solution. Is there a trick to also obtain the directed graphs up to isomorphism and opposite orientation as in question 2?

klaaa gravatar imageklaaa ( 2022-04-17 10:58:16 +0200 )edit

I've updated the answer to address the second part of the question.

rburing gravatar imagerburing ( 2022-04-17 11:03:29 +0200 )edit

Thank you very much again!

klaaa gravatar imageklaaa ( 2022-04-17 11:07:18 +0200 )edit
1

answered 2022-04-18 19:05:27 +0200

For the first question, you can use the iterator over all orientations of a graph

sage: def orientations_up_to_isomorphisms(G):
....:     s = set()
....:     for d in G.orientations():
....:         c = d.canonical_label().copy(immutable=True)
....:         s.add(c)
....:     return s
....: 
sage: D4 = Graph({1: [2], 2: [3,4]})
sage: len(orientations_up_to_isomorphisms(D4))
4
sage: E6 = Graph({1: [2], 2: [3], 3: [4,6], 4: [5]})
sage: len(orientations_up_to_isomorphisms(E6))
20
edit flag offensive delete link more
1

answered 2022-04-16 22:31:19 +0200

Emmanuel Charpentier gravatar image

Ignoring edge labels (what to do with them ?), weights (ditto) and possible loops, a crude brute-force approach is :

def directify(G):
    # Finding all digraphs up to isomorphism for a given undirected
    # graph using Sage.
    # Returns the *set* of such digraphs.
    # Left to the reader : managing loops and edge labels
    # Left to the reader : checking G
    Edges=[tuple(u[:2]) for u in G.edges()]
    L=set()
    for C in powerset(Edges):
        l=[]
        for e in Edges:
            l+=[tuple([e[1], e[0]])] if e in C else [e]
        c=DiGraph(l, immutable=True)
        if any([c.is_isomorphic(u) for u in L]): break
        L|=set([c])
    return L

Micro-tests :

sage: [u.edges() for u in directify(Graph([(a, b), (a, c)]))]
[[(b, a, None), (c, a, None)], [(a, b, None), (c, a, None)]]
sage: [u.edges() for u in directify(Graph([(a, b), (a, c), (b, c)]))]
[[(b, a, None), (c, b, None), (c, a, None)]]

As all brute-force approaches, this is probably highly ameliorable...

HTH,

edit flag offensive delete link more

Comments

1

Thank you very much! I tested it for Dynkin type $E_6$ and the result is that there should be 7 isomorphism types using your code:

d = {1: [2], 2: [3], 3: [4,6], 4: [5]}
G = Graph(d); G
GG=directify(G)
GG2=list(GG)
display(GG2)
display(len(GG2))

Can this be really true? In all 7 cases the arrow points from 3 to 6, which makes me feel like that there are isomorphism types missing (you addressed the first case of the question, so that opposite isomorphism types do not get identified right?)

klaaa gravatar imageklaaa ( 2022-04-16 22:44:37 +0200 )edit

Another example: Dynkin type $D_4$:

d = {1: [2], 2: [3,4]}

There are 3 isomorphism types according to your code (I would think there are 4). It seems the directed graph where all arrows point away from 2 and the directed graph where all arrows point towards 2 are isomorphic according to your code, but I think this is not true, or do I have a big thinking error?

klaaa gravatar imageklaaa ( 2022-04-16 23:15:12 +0200 )edit

Your definition of "isomorphic" may not match Sage's definition embodied in DiGraph.is_isomorphic() :

sage: DiGraph([(0, 1), (1, 2), (2, 0)]).is_isomorphic(DiGraph([(1, 0), (2, 1), (0, 2)]))
True
Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-04-17 10:11:20 +0200 )edit
1

The break in the code should be continue instead.

rburing gravatar imagerburing ( 2022-04-17 10:31:53 +0200 )edit

Thank you very much to both of you again. After the modification of rburing, it seems that it gives better results. At least for $D_4$ the result is now 4 which seems to be correct. For $E_6$ the number is now 20, does anyone know if that is correct ? My feeling is that it is correct. And is there an easy modification of the code for question 2 so that two directed graphs get identified if they have opposite orientation?

klaaa gravatar imageklaaa ( 2022-04-17 10:46:50 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-04-16 19:05:57 +0200

Seen: 74 times

Last updated: Apr 18