Re: weighted subgraph monomorphism

[CE]

On Saturday, April 27, 2013 11:26:29 PM UTC-5, never...@gmail.com wrote:

Hi group,

I have two questions with relation to this title:
1. I have AdjGraph class as following:

class AdjGraph(nx.Graph):

def __init__(self):

super(AdjGraph,self).__init__()

self.ax=None

self._nodesize=30

self._pos={}

and I have object adj1, adj2 of class AdjGraph,

then I want to use

import networkx.algorithms.isomorphism as iso
em=***
GM=iso.GraphMatcher(adj1,adj2,edge_match=em)
print GM

This works just fine for me.  You need to provide a complete, minimal example that demonstrates your problem.

import networkx as nx

class AdjGraph(nx.Graph):

    def __init__(self):

        super(AdjGraph, self).__init__()

        self.ax = None

        self._nodesize = 30

        self._pos = {}

adj1 = AdjGraph()

adj2 = AdjGraph()

em = None

GM = nx.isomorphism.GraphMatcher(adj1, adj2, edge_match=em)

assert GM is not None

print GM

2.Does networkx 1.7 support weighted subgraph monomorphism,
and how to use it?

Unfortunately, the isomorphism class do not support checking monomorphisms.  In principle, it should be a straight-forward modification.  If you get something working, please submit it for inclusion in NetworkX. 

[never...@gmail.com]

Thanks for your reply.

1 . It works if em=None and I want to define edge match function.
With the help of
https://groups.google.com/forum/?fromgroups=#!topic/networkx-discuss/rIR2tTG_kNs
and
https://networkx.lanl.gov/trac/ticket/566#comment:7
finally I have done a test code as following:

def my_edge_match(data1, data2):

if data1==data2:

return True

else:

return False

# if 'weight' in data1:

# if 'weight' in data2:

# return data1['weight']==data2['weight']

# else:

# return False

# else:

# return True

def test():

G1=nx.Graph()

G1.add_cycle(['a','b','c','d'])

G1.edge['a']['b']['weight'] = "red"

G2=nx.Graph()

G2.add_cycle([0,1,2,3])

G2.edge[1][2]['weight'] = "red"

em=iso.generic_edge_match("weight","2",my_edge_match)

GM = iso.GraphMatcher(G1,G2,edge_match=em)

if GM.subgraph_is_isomorphic()==True:

sub= GM.subgraph_isomorphisms_iter()

for s in sub:

print s

if __name__=="__main__":

test()

the output is
{'a': 2, 'c': 0, 'b': 1, 'd': 3}
{'a': 1, 'c': 3, 'b': 2, 'd': 0}
which is good, but I am not quite sure about second parameter in iso.generic_edge_match().
It seems to be unused since output unchanged even though I modified "2" to others, "blue",eg.
Does I follow the right way of using nx's weighted subgraph matching functionality?

2. Currently I am not quite sure about whether ISO or MONO is better for my work,

I use these functions to get matched parts of 3D models. For example, I want G-H not

be matched since the whole structure are of diffrent topologies. But G-G1,H-G1 can be
partially matched.
        G         H         G1
     a     c  a'----c'    a1   c1
      \   /     \   /        \    /
       \ /       \ /          \  /
        b        b'          b1
                              /  \
                             /    \
                           d1----e1
part of the fig. is from https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.python/Ns7dol8zCUY
it said "matched nodes must have the same number of edges"
"a and a' do not have the same number of edges." so G-H is not sub-ISO but sub-MONO.
to test the  coded :

def testiso():

G=nx.Graph()

G.add_path(['a','b','c'])

H=nx.Graph()

H.add_cycle(['a1','b1','c1'])

GM = iso.GraphMatcher(H,G)

if GM.subgraph_is_isomorphic()==True:

sub= GM.subgraph_isomorphisms_iter()

for s in sub:

print s

the output is Nothing, so the link seems to be right(G-H are not subISO).
I continue to test:

def testpartial():

G=nx.Graph()

G.add_path(['a','b','c'])

G1=nx.Graph()

G1.add_path(['a1','b1','c1'])

G1.add_cycle(['d1','b1','e1'])

GM = iso.GraphMatcher(G1,G)

if GM.subgraph_is_isomorphic()==True:

sub= GM.subgraph_isomorphisms_iter()

for s in sub:

print s

the output is
{'a1': 'a', 'c1': 'c', 'b1': 'b'}
{'a1': 'a', 'e1': 'c', 'b1': 'b'}
{'a1': 'a', 'b1': 'b', 'd1': 'c'}
{'a1': 'c', 'c1': 'a', 'b1': 'b'}
{'c1': 'a', 'e1': 'c', 'b1': 'b'}
{'c1': 'a', 'b1': 'b', 'd1': 'c'}
{'a1': 'c', 'e1': 'a', 'b1': 'b'}
{'c1': 'c', 'e1': 'a', 'b1': 'b'}
{'a1': 'c', 'b1': 'b', 'd1': 'a'}
{'c1': 'c', 'b1': 'b', 'd1': 'a'}
I notice in the first row {'a1': 'a', 'c1': 'c', 'b1': 'b'}
b1 and b “do not have the same number of edges”,
but still can be matched with subISO of networkx.
I probably misunderstood subISO and subMONO,please correct me.

在 2013年4月30日星期二UTC+8上午3时46分49秒，CE写道：

[CE]

On Tuesday, April 30, 2013 12:56:11 PM UTC-5, never...@gmail.com wrote:

[snip]

 

the output is
{'a': 2, 'c': 0, 'b': 1, 'd': 3}
{'a': 1, 'c': 3, 'b': 2, 'd': 0}
which is good, but I am not quite sure about second parameter in iso.generic_edge_match().
It seems to be unused since output unchanged even though I modified "2" to others, "blue",eg.
Does I follow the right way of using nx's weighted subgraph matching functionality?

Yes, but your test is fragile and will not work if the attribute dictionaries contain float-value attributes.  As to the second parameter, it specifies the default value for the 'weight' attribute if an edge does not have the 'weight' attribute.  The default value, in this test case you provided, will not matter since it will be the same for all edges.  To see how it works, add:

    G1.edge['c']['d']['weight'] = "3"

And keep your default value at "2".

 

I notice in the first row {'a1': 'a', 'c1': 'c', 'b1': 'b'}
b1 and b “do not have the same number of edges”,
but still can be matched with subISO of networkx.
I probably misunderstood subISO and subMONO,please correct me.

I believe that you have it correct.   

The VF2 algorithm works with edge-induced subgraphs.  So when doing a subgraph-isomorphism test, we keep only the edges that exist between the nodes of the subgraph currently considered...and then, we test for an isomorphism.  So if you consider the subgraph involving a1 b1 and c1, the edges from b1 to d1 and e1 are gone (since d1 and e1 are deleted, essentially).  This leave a subgraph which is isomorphic to G.

So when working with subgraphs, the statement must be modified to "must have the same number of induced edges".

Hope that helps.

[never...@gmail.com]

Clear now. I think I will choose subISO. Also I will improve the function as you said.
Thank you very much, as well as this group, really helpful.

在 2013年5月1日星期三UTC+8上午2时23分44秒，CE写道：