Possible to access all of the mappings in a graph isomorphism
baoilleach
I would like to access all of the isomorphic mappings between two
graphs. Currently it seems that it is only possible to accesss a
single mapping as shown below. Is this correct? If so, could I request
this feature in a future version?
>>> GM = GraphMatcher(G1,G2)
>>> GM.is_isomorphic()
True
>>> GM.mapping
Noel
Christopher Ellison
> Hello all,
>
> I would like to access all of the isomorphic mappings between two
> graphs. Currently it seems that it is only possible to accesss a
> single mapping as shown below. Is this correct? If so, could I request
> this feature in a future version?
>
Hmm. The current algorithm can be seen as some sort of intelligent
search through the space of mappings, and so it is not particularly
suited for determining all isomorphisms. However, I would need to
re-examine the code to say for sure.
In principle, we're going to need to look at every possible mapping
(however briefly) and we could definitely use similar ideas to quickly
rule them out.
So sure. I'll commit to working on this for a future version, but it
might be a little while before I can do it. And be warned, the
algorithm might be fairly slow...
I'll create a ticket in the next day or so, and you can follow the
status there.
Other ideas/thoughts?
Chris
Günter Ladwig
On Aug 13, 6:01 pm, Christopher Ellison <celli...@cse.ucdavis.edu>
wrote:
> search through the space of mappings, and so it is not particularly
> suited for determining all isomorphisms. However, I would need to
> re-examine the code to say for sure.
>
> In principle, we're going to need to look at every possible mapping
> (however briefly) and we could definitely use similar ideas to quickly
> rule them out.
>
> So sure. I'll commit to working on this for a future version, but it
> might be a little while before I can do it. And be warned, the
> algorithm might be fairly slow...
and DiGraphMatcher to save the mapping instead of raising an
exception? This should automatically compute all mappings, as far as I
can tell. The original vflib also has this functionality and I can't
imagine the implementation to be much different.
Regards,
Günter
Christopher Ellison
> Shouldn't it be possible to modify the match method in GraphMatcher
> and DiGraphMatcher to save the mapping instead of raising an
> exception? This should automatically compute all mappings, as far as I
> can tell. The original vflib also has this functionality and I can't
> imagine the implementation to be much different.
Yup. Looks like this will be fairly simple. I can take a look at this
later today and will send something out then.
Chris
Noel O'Boyle
a single mapping they could get it quickly...
> Chris
>
> >
>
Christopher Ellison
I've attached a new version of isomorphvf2.py. Place it in your networkx
folder and give it a try. To obtain all mappings, you could do:
>>> import networkx as nx
>>> # create graphs
>>> GM = nx.isomorphvf2.GraphMatcher(G1,G2)
>>> GM.find_isomorphisms()
find_isomorphisms() will return a list of all isomorphisms, represented
as dictionaries relating nodes in G1 to nodes in G2. The list is also
available at GM.isomorphisms.
Other changes:
Since NetworkX now requires Python 2.4, the builtin 'set' is used
rather than the 'Set' object. I also cleaned up some of the code and
this should result with a slightly faster algorithm.
It would be great (thanks Noel) if the isomorphisms could be obtained
from a generator, but I didn't see an obvious way to do that. If anyone
can come up with a good idea, please post back to the list with advice.
Otherwise, I'm planning on taking more time to see if I can redesign the
implementation so that it is possible. Core issue: The match()
function calls itself recursively, and the 'yield' would have occur at
varying levels of recursion---this seems to disqualify treating match()
as a generator. I hope I am wrong.
Enjoy,
Chris
Noel O'Boyle
Google "recursive generator python" says it's okay, or at least it's
possible in some cases. I will test out the attached code asap.
> Enjoy,
> Chris
>
> >
>
Günter Ladwig
On Aug 21, 12:37 pm, Christopher Ellison <celli...@cse.ucdavis.edu>
wrote:
> as dictionaries relating nodes in G1 to nodes in G2. The list is also
> available at GM.isomorphisms.
adding this method:
def find_subgraph_isomorphisms(self):
self.test = 'subgraph'
self._allmatch(self.state)
return self.isomorphisms
This should work, I think, but I found a bug. Consider the following
three graphs:
g1.add_edge("A", "B")
g1.add_edge("B", "C")
g2.add_edge("Y", "Z")
g3.add_edge("Z", "Y")
g2 and g3 are subgraph isomorphic to g1 and both should return two
matches, but g3 only returns one match. The node labels should not
matter, which is why I think there is a problem with the candidate
pairs and the ordering of the node set. Not having studied the code
closely, this is only a guess, though.
Here is a short program which exhibits this problem:
import networkx as NX
import isomorphvf2
g1 = NX.DiGraph()
g2 = NX.DiGraph()
g3 = NX.DiGraph()
g1.add_edge("A", "B")
g1.add_edge("B", "C")
g2.add_edge("Y", "Z")
g3.add_edge("Z", "Y")
gm12 = isomorphvf2.DiGraphMatcher(g1, g2)
isos = gm12.find_subgraph_isomorphisms()
print len(isos), isos
gm13 = isomorphvf2.DiGraphMatcher(g1, g3)
isos = gm13.find_subgraph_isomorphisms()
print len(isos), isos
Regards,
Günter
Christopher Ellison
> This should work, I think, but I found a bug. Consider the following
> three graphs:
Wonderful! I reexamined the code and figured out the problem. As you
suggested, the problem is indeed with the candidate pairs function, and
I believe that the problem only affects subgraph isomorphisms. More
details below.
>
> g1.add_edge("A", "B")
> g1.add_edge("B", "C")
>
> g2.add_edge("Y", "Z")
>
> g3.add_edge("Z", "Y")
>
> g2 and g3 are subgraph isomorphic to g1 and both should return two
> matches, but g3 only returns one match. The node labels should not
> matter, which is why I think there is a problem with the candidate
> pairs and the ordering of the node set. Not having studied the code
> closely, this is only a guess, though.
So when we compare g1 and g3, the algorithm proceeds like this:
A,Y are tested
-> not feasible
C,Y are tested
-> feasible
B,Z are tested
-> feasible
** isomorphism found **
B,Y are tested
-> feasible
Now, the candidate pairs function computes T1_out and T2_out:
T1_out = ['C']
T2_out = []
In the (attached) source code of the module, you will find references to
two papers, [1] and [2]. In [2], the following statement is made:
"""In the case that only one of the in-terminal sets or only one of the
out-terminal sets is empty, it can be demonstrated that the state s
cannot be part of a matching, and is not further explored."""
Thus, the algorithm concludes that it doesn't need to test this further
(when it should find that A,Z are feasible). For the isomorphism check,
it seems correct to return no candidate pairs, but it doesn't hold for
the subgraph isomorphism....hence, the bug.
In [1], I found a statement which seems to contradict the above
statement---but it leaves some other logic ambiguous. I'm gone ahead
and made some changes that resolve the issue, but I am awaiting
clarification from the paper's author.
So, I've attached an update which **seems* to fix the problem, but we
really need to do some tests to make sure this works. Messing with the
candidate pairs function has the potential to make it so that the
algorithm visits the same 'state' multiple times, and thus, it might
return the same isomorphism multiple times (unsubstantiated claim).
Either tonight or tomorrow, I will run this modified algorithm against a
database of subgraph isomorphisms (and also again on graph isomorphism).
I will also rerun the original code to see if that database was not
catching this error. In the meantime, if you are daring, give this a try
and report back any errors.
Chris
Christopher Ellison
> So, I've attached an update which **seems* to fix the problem, but we
> really need to do some tests to make sure this works.
Whoops...I left a few print statements in there.
Fixed and attached,
Chris
Günter Ladwig
wrote:
using your implementation as a reference. This is the same solution I
came up with later and corresponds with the paper where the algorithm
is presented [1]. The other paper you mentioned is a few years older
and probably refers to a previous iteration of the algorithm, I think.
I'll test your fix tomorrow.
I'm having other problems with the algorithm, though, which do not
pertain to your implementation. If I have a graph (A->B), (B->A), i.e.
a cycle, the subgraph matching for, e.g. (Y->Z), should find two
matches, but in fact does not match at all. This probably stems from
the formulation of the subgraph problem in the paper, which says that
a match has to preserve the branch structure, which is not the case
here. Ah, well, maybe I'll find a solution.
Regards,
Günter
Christopher Ellison
> I'll test your fix tomorrow.
With the exception of the problem you listed below, did the fix work
well for you? ---- I'm also curious to hear if anyone else was able to
test the fix.
I ran it against a decent number of known cases from the vf2 graph
database, and I found the proper number of subgraph isomorphisms in each
case. Without the fix, they definitely fail.
Also, I still have not received confirmation on the fix from the
original author. Oh well. I'd like to get this fix into the library,
but I still wanted to see if I could make this a generator...and I need
to write additional units tests.
>
> I'm having other problems with the algorithm, though, which do not
> pertain to your implementation. If I have a graph (A->B), (B->A), i.e.
> a cycle, the subgraph matching for, e.g. (Y->Z), should find two
> matches, but in fact does not match at all. This probably stems from
> the formulation of the subgraph problem in the paper, which says that
> a match has to preserve the branch structure, which is not the case
> here. Ah, well, maybe I'll find a solution.
Interesting. Did you happen to find anything?
Chris
Günter Ladwig
On 07.09.2008, at 08:23, Christopher Ellison wrote:
> Günter Ladwig wrote the following on 08/21/2008 06:28 PM:
>> I'll test your fix tomorrow.
>
> With the exception of the problem you listed below, did the fix work
> well for you? ---- I'm also curious to hear if anyone else was able to
> test the fix.
Yes, it did work for me, although I performed only very limited testing.
>> I'm having other problems with the algorithm, though, which do not
>> pertain to your implementation. If I have a graph (A->B), (B->A),
>> i.e.
>> a cycle, the subgraph matching for, e.g. (Y->Z), should find two
>> matches, but in fact does not match at all. This probably stems from
>> the formulation of the subgraph problem in the paper, which says that
>> a match has to preserve the branch structure, which is not the case
>> here. Ah, well, maybe I'll find a solution.
>
> Interesting. Did you happen to find anything?
Yes. The terminology is somewhat confusing. Wikipedia refers to two
subgraph isomorphism problems, the "standard" subgraph isomorphism
(which is what I need) and the induced subgraph isomorphism problem (http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem
), which has the additional condition that if an edge is absent in G1
it also has to be absent in G2. This is what is implemented in
networkx, where the induced subgraph isomorphism problem is called
subgraph isomorphism. This is the terminology from the VF2 paper and
VFlib, where the "standard" subgraph isomorphism problem is referred
to as subgraph *monomorphism*. Luckily, VFlib does implement the
subgraph monomorphism problem and I was able to adapt that to my use
case.
Regards,
Günter
Christopher Ellison
>
> Yes. The terminology is somewhat confusing. Wikipedia refers to two
> subgraph isomorphism problems, the "standard" subgraph isomorphism
> (which is what I need) and the induced subgraph isomorphism problem (http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem
> ), which has the additional condition that if an edge is absent in G1
> it also has to be absent in G2. This is what is implemented in
> networkx, where the induced subgraph isomorphism problem is called
> subgraph isomorphism. This is the terminology from the VF2 paper and
> VFlib, where the "standard" subgraph isomorphism problem is referred
> to as subgraph *monomorphism*. Luckily, VFlib does implement the
> subgraph monomorphism problem and I was able to adapt that to my use
> case.
Aha. I'll add that to the networkx one as well.
Thanks!
Chris