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 modify
http://www.sagemath.org/hg/sage-main/file/ce4aa966e4c1/sage/graphs/graph_isom.pyx
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/
-~----------~----~----~----~------~----~------~--~---
