Or, in sage notebook language, so you can just paste it in to the
"Edit" box:
Untitled
system:sage
{{{id=2|
G = Graph({0:{1:'a', 3:'b'}, 2:{1:'b', 3:'a'}})
}}}
{{{id=3|
H = Graph({0:{1:'b', 3:'a'}, 2:{1:'a', 3:'b'}})
}}}
{{{id=4|
graphs_list.show_graphs([G,H], edge_labels=True, vertex_labels=True,
vertex_size=0)
}}}
{{{id=5|
from sage.graphs.graph_isom import search_tree
}}}
{{{id=6|
G_aut_gp_gens, _, G_can_map = search_tree(G, [G.vertices()],
dict=False, certify=True)
}}}
{{{id=8|
_, _, H_can_map = search_tree(H, [H.vertices()], dict=False,
certify=True)
}}}
{{{id=9|
G_can_map, H_can_map
///
({0: 0, 1: 2, 2: 1, 3: 3}, {0: 0, 1: 2, 2: 1, 3: 3})
}}}
{{{id=17|
H_can_inv_map = {}
for i in range(4):
H_can_inv_map[H_can_map[i]] = i
}}}
{{{id=11|
G_aut_gp_gens
///
[[0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3]]
}}}
{{{id=16|
def foo(perm, G_aut_gp_gens, seen):
works = True
for i in range(4):
for j in range(i):
if G.has_edge(i,j):
if G.edge_label(i,j) !=
H.edge_label(H_can_inv_map[G_can_map[perm[i]]],
H_can_inv_map[G_can_map[perm[j]]]):
works = False
if works:
return [H_can_inv_map[G_can_map[perm[i]]] for i in range(4)]
for gen in G_aut_gp_gens:
new_perm = [perm[gen[i]] for i in range(4)]
if new_perm in seen: continue # go to next generator (else:)
seen.append(new_perm)
return foo(new_perm, G_aut_gp_gens, seen)
}}}
{{{id=10|
perm = [0,1,2,3] # identity in S_4
seen = [perm]
foo(perm, G_aut_gp_gens, seen)
///
[0, 3, 2, 1]
}}}
On Nov 10, 1:28 pm, Robert Miller <[EMAIL PROTECTED]> wrote:
> Dustin,
>
> At the moment, graph isomorphism with edge labeling is not
> implemented. The modifications to the code needed for such a feature
> aren't incredibly complicated, but they do require some time. To be
> completely specific, what you would need to do, to modify the
> isomorphism program itself, is
> modifyhttp://www.sagemath.org/hg/sage-main/file/ce4aa966e4c1/sage/graphs/gr...
> as follows. The loop on lines 565-568 (and again on lines 610-613 in
> the case of a digraph) calculates the degree from one cell of a
> partition to another, without regard to edge labels. It then uses
> these degrees to refine the partition, on line 574 (and 618). What
> would need to be done is to incorporate edge labels into the data used
> in these loops, which could probably be just part of the output of the
> _degree_square_matrix function. One modification you could make is to
> establish an enumeration, so that the output could be probably a long
> long or something, so that it would have room - the first n integers
> would mean so many edges with label "0", the next n could be those
> with label "1", etc.
>
> Eventually this feature will be implemented, exactly when depends on
> who's feeling up to the challenge. After I finish my current project,
> I might go back in and do some other optimizations too. However, in
> the meantime, you can do the following.
>
> If they are isomorphic as edge-labeled graphs, they are certainly
> isomorphic as graphs, so you can rule out some possibilities right
> there. Once you have a non-labeled isomorphism between the graphs (at
> which point you can also have the automorphism group), you can use one
> of the automorphism groups to check on the orbits of the edges of each
> label. If they don't line up, then again you can rule out some
> possibilities. At last, when nothing else has worked, you can use the
> generators of the automorphism group to do like a breadth-first search
> through the automorphism group to find an explicit edge-labeled
> isomorphism. Of the two options described here, (1) being to modify
> graph_isom.pyx and (2) being to traverse the automorphism group, the
> first is most likely much faster, but harder to implement, and the
> second is something you could have going in a day or two, but it
> wouldn't be as fast. Here is an example of method (2) to get you
> started. It involves some abusive notation, and may very well only
> work from the notebook, but you can at least get the idea from this-
>
> sage: G = Graph({0:{1:'a', 3:'b'}, 2:{1:'b', 3:'a'}})
> sage: H = Graph({0:{1:'b', 3:'a'}, 2:{1:'a', 3:'b'}})
> sage: graphs_list.show_graphs([G,H], edge_labels=True,
> vertex_labels=True, vertex_size=0)
> sage: from sage.graphs.graph_isom import search_tree
> sage: G_aut_gp_gens, _, G_can_map = search_tree(G, [G.vertices()],
> dict=False, certify=True)
> sage: _, _, H_can_map = search_tree(H, [H.vertices()], dict=False,
> certify=True)
> sage: G_can_map, H_can_map
> ({0: 0, 1: 2, 2: 1, 3: 3}, {0: 0, 1: 2, 2: 1, 3: 3})
> sage: H_can_inv_map = {}
> sage: for i in range(4):
> ... H_can_inv_map[H_can_map[i]] = i
> sage: G_aut_gp_gens
> [[0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3]]
> sage: def foo(perm, G_aut_gp_gens, seen):
> ... works = True
> ... for i in range(4):
> ... for j in range(i):
> ... if G.has_edge(i,j):
> ... if G.edge_label(i,j) !=
> H.edge_label(H_can_inv_map[G_can_map[perm[i]]],
> H_can_inv_map[G_can_map[perm[j]]]):
> ... works = False
> ... if works:
> ... return [H_can_inv_map[G_can_map[perm[i]]] for i in
> range(4)]
> ... for gen in G_aut_gp_gens:
> ... new_perm = [perm[gen[i]] for i in range(4)]
> ... if new_perm in seen: continue # go to next generator
> (else:)
> ... seen.append(new_perm)
> ... return foo(new_perm, G_aut_gp_gens, seen)
> sage: perm = [0,1,2,3] # identity in S_4
> sage: seen = [perm]
> sage: foo(perm, G_aut_gp_gens, seen)
> ...
> [0, 3, 2, 1]
>
> On Nov 8, 1:35 pm, Dustin Pluta <[EMAIL PROTECTED]> wrote:
>
> > Hi,
>
> > I'm working on a problem for which I have symmetric matrices with
> > arbitrary entries. I'm interpreting these matrices as adjacency
> > matrices where the (i,j) entry gives the color for the i-j edge of a
> > graph, and I need to know if the graphs given by these matrices are
> > isomorphic. My current work around is to split the edges with
> > additional nodes and color these new edge nodes appropriately. I was
> > wondering if edge colorings will be implemented anytime soon into
> > sage, or if someone can suggest a cleaner and more efficient approach.
>
> > Thanks,
>
> > -Dustin Pluta
> > University of California-Davis
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://sage.math.washington.edu/sage/ and http://sage.scipy.org/sage/
-~----------~----~----~----~------~----~------~--~---
