vertex_label and edge_label in subgraph-isomorphism

graph-tool
1

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

2

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

3

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))

4

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.