[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Maximum Common Subgraph

From: Mark Galea
Subject: Re: [igraph] Maximum Common Subgraph
Date: Fri, 11 Mar 2011 15:43:38 +0000

Hi Tamas,á

I have actually managed to compile the code and tried the example. á

The example worked however I believe that there is a problem. á

Have a look at the following example. á


from igraph importá GraphBase;á

from igraph import Graph;á

class IsomorphicTest(object):

á á def test(self):

g = Graph.Formula("A-B-D-E")

g2 = Graph.Formula("B-C")

all_names = set(g.vs["name"]).union(g2.vs["name"])

names_to_colors = dict((v, k) for k, v in enumerate(all_names))

print all_names

print names_to_colors

print "========================================"

colors1 = [names_to_colors[name] for name in g.vs["name"]]

print g.vs["name"]á

print colors1

print "========================================"

colors2 = [names_to_colors[name] for name in g2.vs["name"]]

print g2.vs["name"]á

print colors2

print "========================================"

print g.get_subisomorphisms_vf2(g2)

print g.get_subisomorphisms_vf2(g2, colors1, colors2)

áá á

if __name__ == '__main__':

á á IsomorphicTest().test()


This is the output. á

set(['A', 'C', 'B', 'E', 'D'])

{'A': 0, 'C': 1, 'B': 2, 'E': 3, 'D': 4}


['A', 'B', 'D', 'E']

[0, 2, 4, 3]


['B', 'C']

[2, 1]


[[0, 1], [1, 0], [1, 2], [2, 1], [2, 3], [3, 2]]


Clearly we are expecting to find the mapping [1,0] Referring to the mapping B from the first graph to B onto the second graph. áAm I missing something. á

Thanks a lot for your time. á



áá á á á

On Fri, Mar 11, 2011 at 3:16 PM, Mark Galea <address@hidden> wrote:
Hi Tamas,á

Thanks a lot for your response.á

Hopefully everything will work :) Thanks for the updates example. Will wait for the build. á

Thanks a lot mate. áMuch appreciated. á



On Fri, Mar 11, 2011 at 2:56 PM, Tamas Nepusz <address@hidden> wrote:

I am slightly confused what the new build will do. áDoes this also update the python bindings I am already using?
Yes, beacuse the two versions (0.5 and 0.6) are binary incompatible; i.e. there were a few updates in the C layer that require the recompilation of the Python interface as well.

I have provided an example so that I'm sure that I am understanding what I should do exactly.á

This is my test case.á

from igraph import áGraphBase;
You don't need GraphBase; Graph derives from GraphBase and the latter is an internal thing anyway :)

Also, there is one other modification that you have to do; get_subisomorphisms_vf2 does not start using the vertex names "magically", it requires a numeric vector where each element specifies the "color" (or "label") of the corresponding vertex. You have to construct that mapping from names to numeric IDs yourself, and then pass the vectors mapping vertices to "colors" to get_subisomorphisms_vf2. I'll try to adapt your example:

def test(self):
ááá g = Graph.Formula("A-B-D")
ááá g2 = Graph.Formula("B-D")
ááá all_names = set(g.vs["name"]).union(g2.vs["name"])
ááá names_to_colors = dict((v, k) for k, v in enumerate(all_names))
ááá colors1 = [names_to_colors[name] for name in g.vs["name"]]
ááá colors2 = [names_to_colors[name] for name in g2.vs["name"]]
ááá print g.get_subisomorphisms_vf2(g2, colors1, colors2)

This one prints "[[1, 2]]" for me; I think this is the correct result as vertex 0 of the second graph maps to vertex 1 of the first one and vertex 1 of the second graph maps to vertex 2 of the first one, and there is no other mapping, right?

I'll prepare a Snow Leopard installer for you in the evening or tomorrow, when time allows.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]