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

digraph

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

klaaa
691 ●4 ●17 ●41

updated 2024-04-12 20:12:24 +0100

FrédéricC

5251 ●3 ●44 ●116

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

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?
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

add a comment

3 Answers

Sort by » oldest newest most voted

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

rburing

10919 ●4 ●80 ●218 https://www.rburing.nl/

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

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

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 ( 2022-04-17 10:58:16 +0100 )edit

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

rburing ( 2022-04-17 11:03:29 +0100 )edit

Thank you very much again!

klaaa ( 2022-04-17 11:07:18 +0100 )edit

add a comment

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

Emmanuel Charpentier
7764 ●6 ●50 ●153

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

Comments

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 ( 2022-04-16 22:44:37 +0100 )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 ( 2022-04-16 23:15:12 +0100 )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 ( 2022-04-17 10:11:20 +0100 )edit

The break in the code should be continue instead.

rburing ( 2022-04-17 10:31:53 +0100 )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 ( 2022-04-17 10:46:50 +0100 )edit

add a comment

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

David Coudert
766 ●12 ●20 http://www-sop.inria.f...

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

add a comment

Your Answer

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

Add Answer

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

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

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

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

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