0

以下 Python 代码：

import networkx as nx
g = nx.DiGraph()
g.add_nodes_from([0, 1])
g.add_edges_from([(0,0), (0,1), (1,0), (1,1)])
nx.write_dot(g, 'g.dot')
gl = nx.line_graph(g)
nx.write_dot(gl, 'gl.dot')

创建以下点格式图：

--- g.dot ---

digraph  {
    0 -> 0;
    0 -> 1;
    1 -> 0;
    1 -> 1;
}

--- gl.dot ---

strict digraph  {
    "(0, 1)" -> "(1, 1)";
    "(1, 0)" -> "(0, 0)";
    "(0, 0)" -> "(0, 1)";
    "(1, 1)" -> "(1, 0)";
}

边缘应该：

"(1, 0)" -> "(0, 1)";
"(0, 1)" -> "(1, 0)";
"(0, 0)" -> "(1, 1)";
"(1, 1)" -> "(0, 0)";

在折线图构造中？

http://en.wikipedia.org/wiki/Line_graph#Line_digraph

4

2 回答 2

1

nx.line_graph创建一个严格的有向图。严格意味着没有循环和重复的边缘。"(0, 1)" -> "(1, 0)"是一个循环，所以不包括在内。换句话说，“当 v = w和 u != x时，表示 G 中从 u 到 v 和从 w 到 x 的有向边的两个顶点通过严格线有向图中从 uv 到 wx 的边连接起来”。（来自维基百科的引述——我的插入是粗体的）。

于 2013-08-13T16:54:20.203 回答
0

NetworkX 线图代码不会为自环添加隔离，也不允许在折线图中创建自环（原始图中长度为 2 的环）。

这可能是错误或功能。如果有人能指出这些情况下线图的定义，也许我们至少可以澄清文档或更新代码。

请注意，在这种情况下，点文件关键字“strict”基本上是正确的，但这只是一个令人高兴的巧合，即编写点文件的代码检查自循环和多边，如果没有找到，则使用“严格”。

同时，这里是一种生成允许两种循环的有向线图的方法：

import networkx as nx
def directed_line_graph(G):
    L = nx.DiGraph()
    for u, adj in G.adjacency_iter():
        for v in adj:
            L.add_node((u,v))  # add self loops and single edges as nodes
            for w in G[v]: # neighbors of v
                if not (u == v and v == w):
                    L.add_edge((u,v),(v,w))
    return L

g = nx.DiGraph()
g.add_edges_from([(0,0), (0,1), (1,0), (1,1)])
gl = directed_line_graph(g)
for e in gl.edges():
    print e
# ((0, 1), (1, 0))
# ((0, 1), (1, 1))
# ((1, 0), (0, 1))
# ((1, 0), (0, 0))
# ((0, 0), (0, 1))
# ((1, 1), (1, 0))
于 2013-08-14T23:57:07.770 回答