How can I search and count all induced subgraphs in a directed graph with edge labels?

[bsste...@gmail.com]

Hello all,

I can extract all induced subgraphs and count them in a graph. My question is how I can search and count all induced subgraphs in a labeled graph (a graph with edge labels)? In documentation of g.subgraph() and g.subgraph_search_count() is mentioned that these functions should work on labeled graphs as well. but it does not work. Here is an example:

sage: g=DiGraph()
sage: g.add_vertex(0)
sage: g.add_vertex(1)
sage: g.add_vertex(2)
sage: g.add_edge(0,1,label="a")
sage: g.add_edge(1,2,label="b")
sage: g.plot(color_by_label="true")
sage: g.plot(color_by_label=true)

sage: s=DiGraph()
sage: s.add_vertex(0)
sage: s.add_vertex(1)
sage: s.add_edge(0,1,label="a")
sage: s.plot(color_by_label=true)

sage: g.subgraph_search_count(s)
2


While it should return 1 not 2.

Any response and help is appreciated!
Thanks

[Nathann Cohen]

Hello,

These functions do not take edge labels into account. When the documentation says that it counts/enumerates/find 'labeled' copies of a graph, it means precisely that the number of copies of a graph G in itself is equal to the size of Aut(G), the automorphism group of G.

It is the same terminology used here, for instance:

http://oeis.org/A001187

In this terminology, an unlabeled graph is a "graph up to isomorphism".

Nathann

[Nathann Cohen]

By the way: in Sage, you do not need to create the vertices before creating the edges. Adding the edges will also add the vertices.

Nathann

[Nathann Cohen]

I created ticket #18296 to try to make it clearer.

http://trac.sagemath.org/ticket/18296

Nathann

[bsste...@gmail.com]

Hello Nathann,


Thank you for your comments and follow up for creating a ticket. Apparently the text of the documentation is already changed. Just, how can I search induced subgraphs in labeled graphs? This is the main problem. Are there any method or suggestion which helps me to do that?

Regards
Mohsen

[Nathann Cohen]

Helloooooo,

Just, how can I search induced subgraphs in labeled graphs? This is the main problem. Are there any method or suggestion which helps me to do that?

Hmmmmmm.... Well, at the moment I would say that there is none. No way to find induced subgraph of labelled digraphs. Even though for "induced subgraphs of (simple) labelled undirected graphs" we ca manage a trick.

See, the problem is that it is rather hard to design a somewhat efficient data structure for "labelled digraphs". Your problem of "induced subgraph of labelled simple digraph" (*) could be rather well emulated by a "induced subgraph of directed multigraph" (though we can't do that either). And a "proper implementation" should probably deal with non-induced subgraphs as well, and that's where it becomes hell. To deal with that problem we should probably copy at low-level, for each label that you have, the graph induced by all edges having that label.

The more I think about how this should be implemented, the more it scares me.

Nathann

(*) you don't have paralell edges, right?

[bsste...@gmail.com]

Hello,

Right now, no. My graphs do not have parallel edges.

You are right it is horrible to provide an efficient implementation for labeled subgraph extractions. Just one idea makes my mind busy. I believe what makes the function "subgraph" does not work for labeled graphs is isomorphic checking.
while function "g.is_isomorphic" in sage has an argument (called edge_labels) which if it is true then this function checks isomorphism with considering edge labels. Now if in implementation of function "subgraph" we call function "is_isomorphic" with setting the parameter "edge_labels=True", then it should work.

What is your opinion?
Regards,

[Nathann Cohen]

Hello,

I am not sure that I understood your message very well. Are you saying
that one way to achieve what you do would be to call the current
"subgraph_search" methods, and to *filter* among its results those
which are actually *equal* (considering edge labels) to the graph you
are looking for?

If so, it works. It is just.. Well, ugly in the backscene. But if you
only deal with very small instances, then the following does what you
like:

g = DiGraph({0: {1: 'a'}, 1: {2: 'b'}})
s = DiGraph({0: {1: 'a'}})

def subgraphs_with_labels(G,H):
r"""
An iterator over all subgraphs of G isomorphic to H (edge labels are taken
into account)
"""
G = G.copy()
H = H.copy()
G.weighted(True)
H.weighted(True)
Hverts = H.vertices()
for g in G.subgraph_search_iterator(H):
gg = G.subgraph(vertices=g)
gg_rel = gg.relabel(dict(zip(g,Hverts)),inplace=False)
if H == gg_rel:
yield gg

sage: list(subgraphs_with_labels(g,s))
[Subgraph of (): Digraph on 2 vertices]

Nathann