Revision history [back]

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$ example:

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$ example:

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)]]

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$ ~~example:~~orientations:

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$ ~~example:~~orientations:

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 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 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)]]

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:~~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:~~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)]]