3

我有点卡在我的图表问题上，而且不是这个主题的专家，我想我会求助于互联网。我有两个图 A 和 B，我想检查 B 是否是 A 的子图。我尝试使用 igraph 执行此操作，但它似乎声称 B 是 A 的子图，即使它不是。这是一个说明这一点的例子：

from igraph import *

def func(g1, g2, e1, e2):
    if g1.es[e1]["color"] == g2.es[e2]["color"]:
        return True
    else:
        return False


a = Graph(4, directed=True)
a.add_edge(0,1,color=1)
a.add_edge(1,2,color=1)
a.add_edge(2,3,color=1)
a.add_edge(0,2,color=2)
a.add_edge(2,0,color=2)
a.add_edge(1,3,color=2)
a.add_edge(3,1,color=2)

b = Graph(2, directed=True)
b.add_edge(0,1,color=1)
b.add_edge(0,1,color=2)
b.add_edge(1,0,color=2)

t = a.get_subisomorphisms_vf2( other=b, edge_compat_fn=func)
print t

程序打印“[[0, 2], [1, 3]]”

我认为 B 不是 A 的子同构，因为从顶点 0 开始的 color=1 线没有连接到顶点 2，但 igraph 似乎忽略了这一点。我做错了什么还是igraph中的错误？我将 python-igraph 0.6.5 与 Python 2.6.5 一起使用

编辑：我认为这里可以忽略颜色。我的问题是，在图 A 中，存在从第 0 个顶点到第一个顶点的链接，因此 B 不是子图，因为这需要（在图 A 中）第 0 个顶点直接连接到第二个顶点。

Edit2：我怀疑我真正想要的是“诱导子图同构”。

4

2 回答 2

2

Recall the definition of a subgraph:

A graph G' whose graph vertices and graph edges form subsets of the graph vertices and graph edges of a given graph G.

What appears to be happening here is that your directed multigraph is not being recognized with igraph (I don't know igraph well-enough to know whether directed multigraphs are supported). It appears that your second edge on graph B from (0,1, color=2) is just a reassigned color from (0,1, color=1).

igraph api - get_subisomorphisms_vf2

If this is true, then your output t makes total sense. Those are two subgraph isomorphisms indeed. Isomorphism here doesn't respect edge colorings unless you do so explicitly. If you want it to, you'll have to update your code to add edge_color1 and edge_color2 when you call get_subisomorphisms_vf2.

What are your requirements? What problem(s) are you trying to solve?

于 2014-06-20T17:40:59.407 回答
0

谢谢大家的意见。似乎 igraph 忽略了多个边缘，但这里描述了一种解决方法http://lists.nongnu.org/archive/html/igraph-help/2013-08/msg00038.html。

于 2014-06-23T09:32:17.597 回答