Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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()]
    for C in powerset(Edges):
        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
    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...