Graph isomorphism with edge weights in mathematica

From: Kris Kennaway <kkenn@xxxxxxxxxxxxxxxxxx>
Date: Wed, 6 Apr 2005 19:31:32 -0700

I want to use Mathematica to test whether two graphs are isomorphic,
where both graphs have a set of edge weights. Using Combinatorica, I
can construct a graph with the edge weights using

FromAdjacencyMatrix[matrix1, EdgeWeights]

but the function

Isomorphism[FromAdjacencyMatrix[matrix1, EdgeWeights],
FromAdjacencyMatrix[matrix2, EdgeWeights]]

only tests isomorphism of the underlying graphs, i.e. by ignoring the
edge weights. Thus, it finds "isomorphisms" that do not map the first
set of weights into the second.

Does anyone know whether there is a way to do this?

Kris
.

Prev by Date: Re: Any views about an *unmoderated* Mathematica newsgroup?
Next by Date: Animation of rotating axes
Previous by thread: which software allows this: defining functions by cases
Next by thread: Animation of rotating axes
Index(es):
- Date
- Thread

Relevant Pages

Re: New algorithm for the isomorphism of graphs
... of the planar ones. ... of two trees, or the case of two planar graphs, then you can solve the ... since the Graph Isomorphism problem would be known to be in P. ...
(sci.math)
Re: (Probably flawed) Polynomial time Graph Isomorphism
... On random input graphs graph isomorphism ... Note that testing degree sequences is a deterministic algorithm. ... The problem here is the algorithm relies on a hash function, ...
(comp.theory)
Re: Need Graph Isomorphism Algorithm De-bunked
... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. ...
(sci.crypt)
Re: New algorithm for the isomorphism of graphs
... in bottom there are all the adjacent vertices at the vertex S. ... then the problem of the isomorphism of graphs is ... We want to explicitly construct an isomorphism F from G to ... neighbors of some candidate for F. ...
(sci.math)
New algorithm for the isomorphism of graphs
... Here a method to find the function of isomorphism between two ... In the second graph there is a vertex which has the same pseudo-tree. ... then the problem of the isomorphism of graphs is ... one seeks in G' all the vertices which one dismantles equal ...
(sci.math)