I've faced difficulties using the package graph_tool.topology - Assessing graph topology. Specifically, I am trying to use the function graph_tool.topology.subgraph_isomorphism, but incorporating the values of the arguments vertex_label edge_labels. At the documentation provided at the graph-tool web site does not appear explicit examples of how these value can be defined. The aim is to identify isomorphisms, with coincidence on vertices and edges labels. Can you give me an example or page where this is explained clearly? Thanks, I hope I have been clear in my question!! Regards
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 06/20/2014 03:27 AM, yandim601 wrote:
I've faced difficulties using the package graph_tool.topology - Assessing graph topology. Specifically, I am trying to use the function graph_tool.topology.subgraph_isomorphism, but incorporating the values of the arguments vertex_label edge_labels. At the documentation provided at the graph-tool web site does not appear explicit examples of how these value can be defined. The aim is to identify isomorphisms, with coincidence on vertices and edges labels. Can you give me an example or page where this is explained clearly?
Sorry for the delay. I seem to have missed this message when it was posted.
The edge/vertex labels should be property maps which specify the values at each node or edge witch must be identical if two vertices or edges in each graph are mapped in the resulting isomorphism.
I don't have an example handy at the moment, but I think the interpretation should be straightforward. If you have any trouble using it, please post succinctly what you are trying to achieve, and what is the difficulty you are encountering.
Best, Tiago
Hi,
Here's an example:
Imaging your subgraph (let's call it sub. save it in a file called sub.gml) looks like this in .gml format:
graph [ directed 1 node [ id 0 name "a" status "down" ] node [ id 1 name "b" status "up" ] ]
And your larger graph (let's call it g. save it in a file called g.gml) looks like this:
graph [ directed 1 node [ id 0 name "a" status "up" ] node [ id 1 name "b" status "up" ] node [ id 0 name "a" status "down" ] node [ id 1 name "b" status "up" ] node [ id 4 name "c" status "down" ] ]
When you load your graphs, the properties load in the graphs' property maps (you can retrieve them with g.vertex_properties['status'] for example). Here's 2 ways you can find subgraphs that are isomorphic:
vertex_mapping_name, edge_mapping_name=gt.subgraph_isomorphism(sub, g, vertex_label=(sub.vertex_properties["name"],g.vertex_properties["name"]),random=True) vertex_mapping_status, edge_mapping_status=gt.subgraph_isomorphism(sub, g, vertex_label=(sub.vertex_properties["status"],g.vertex_properties["status"]),random=True)
If I have multiple criteria, I perform an intersection of sorts after the fact. I'm not sure if there's a better way to use different labels at the same time.
I've pasted the python code below.
Hope that helps!
Reem
import graph_tool.all as gt
g = gt.load_graph("./g.gml") sub = gt.load_graph("./sub.gml")
vertex_mapping_name, edge_mapping_name=gt.subgraph_isomorphism(sub, g, vertex_label=(sub.vertex_properties["name"],g.vertex_properties["name"]),random=True) vertex_mapping_status, edge_mapping_status=gt.subgraph_isomorphism(sub, g, vertex_label=(sub.vertex_properties["status"],g.vertex_properties["status"]),random=True)
print(len(vertex_mapping_name)) print(len(vertex_mapping_status))
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
Sorry, g.gml should look like this:
graph [ directed 1 node [ id 0 name "a" status "up" ] node [ id 1 name "b" status "up" ] node [ id 2 name "a" status "down" ] node [ id 3 name "b" status "up" ] node [ id 4 name "c" status "down" ] ]
As output, you should get: 4 6
These are a list of mappings from sub to g. If you want to access a particular one, for example you can use a_mapping = vertex_mapping_name[index]. Then you can say a_mapping[sub.vertex(0)] to access which vertex in g this maps to.
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
-
Reem Mokhtar -
rmokhtar
-
Tiago de Paula Peixoto -
yandim601