subgraph isomorphism in networkx

[Stefan Klingelschmitt]

I'm trying to solve a subgraph isomorphism problem with networkx. I'm struggeling with the results of the .sugraph_is_isomorphic()...

A quick example:

import networkx as nx
G_1 = nx.Graph()
G_1.add_path([1,2,3])
G_1.add_path([1,3])   #wihout this line everything works like expected

G_2 = nx.Graph()
G_2.add_path([1,2,3])

GM = nx.isomorphisms.GraphMatcher(G1,G2)
print GM.subgraph_is_isomorphic()

It seems, when I'm adding this "loop" (it's an undirected Graph), the function returns False.

What is the problem here? Am I missing something?

Thanks

[Daniel Schult]

This documentation discusses the isomorphism routines:

http://networkx.github.io/documentation/latest/reference/algorithms.isomorphism.vf2.html

I think the relevant section is the definitions in the section "subgraph isomorphism" where the word subgraph is defined to be a node induced subgraph.  There are indeed no isomorphisms between the triangle and the 2-path using node induced subgraphs.

Dan 

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Stefan Klingelschmitt]

Hello Dan,

Thanks for your reply and the explanation. "Unfornutately" you are right and in terms of and induced subgraph there is acutally none. In the documenation you recommended, I found this line: "Edge-induced subgraph isomorphisms are not directly supported, but one should be able to perform the check by making use of nx.line_graph()". I looked at the line_graph() generator but I don't see how this could solve my problem. Any suggestions?

Thanks Stefan

[Daniel Schult]

Well, the line_graph() turns edges into nodes and nodes into edges so an edge-induced subgraph becomes a node-induced subgraph of the line graph.  If you want a length-2-path to be identified with a subgraph of a triangle then edge-induced subgraphs won't work for you either.  What kind of subgraph do you want? 

--

[Stefan Klingelschmitt]

Well, the line_graph() turns edges into nodes and nodes into edges so an edge-induced subgraph becomes a node-induced subgraph of the line graph.  If you want a length-2-path to be identified with a subgraph of a triangle then edge-induced subgraphs won't work for you either.  What kind of subgraph do you want? 

The triangle was a very simplified example for the task I would like solve. But I cannot guarantee that this will not happen. Actually I was'nt aware that this so hard to define. I guess I have to give some thoughts to this first, because the first test I made, I used graph-tool (and perhaps by accident) everything has worked fine. (I guess the developer had the same idea of the term "subgraph" as me :) )

But nevertheless thanks, or do you have some idea for a work around regarding my problem?

[CE]

(I thought I had already replied to this...trying again).

It sounds like you are looking for a subgraph monomorphism instead of a subgraph isomorphism.  Unfortunately, the current implementation does not provide support for monomorphisms. Contributions are greatly appreciated!

More information: http://stackoverflow.com/questions/459799/whats-the-difference-between-subgraph-isomorphism-and-subgraph-monomorphism

[Stefan Klingelschmitt]

Thank you for your comment. Actually, you are right, I am looking for a graph monomorphism! Thanks for pointing that out for me!

Fornutately I can formulate my problem in a way that I can rely subgraph isomorphisms (node-induced)

But your right an implementation of a monorphism for networkx would be really nice! I don't think that I will have the capacities to do so....

Do you know any potent algorithm, well documented? Just in case I get bored ;-)

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/bFErKN8pC_I/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.