如何使用 Python 中的 networkx 或 graphviz 为旅行商问题中的所有可能路径自动创建有向图？

Question

我想创建一个有向图，显示我想探索的四个城市的旅行商问题中的所有可能路径。

cities = ["Berlin","Hamburg","Dusseldorf","Munich"]

首先，我使用 graphviz 包创建了一个框架。节点是整数（但以字符串的形式）。代码如下所示：

import graphviz

nodes = np.arange(0, 21)

cities = ["Berlin","Dusseldorf","Hamburg","Munich"]


f = graphviz.Digraph()

#Stop 1
for i in range(1, 4):
    f.edge(str(0), str(i))
    
#Stop 2 add edges
for i in range(1,4):   
    for j in range(4,10):
        if j==i*2+2 or j == i*2+3:
            f.edge(str(i), str(j))
            
for i in range(4, 10):
    for j in range(10, 16):
        if j == i+6:
            f.edge(str(i), str(j))

for i in range(10, 16):
    for j in range(16, 22):
        if j == i+6:
            f.edge(str(i), str(j))
            
f

这返回了如下有向图：

代替节点，我想给出城市名称作为标签。假定旅行商问题中的路线起点和终点都在柏林。我在下面的代码中手动向节点提供了名称（标签）。

import graphviz

nodes = np.arange(0, 21)

cities = ["Berlin","Dusseldorf","Hamburg","Munich"]


f = graphviz.Digraph()

#Stop 1
for i in range(1, 4):
    f.edge(str(0), str(i))
    
#Stop 2 add edges
for i in range(1,4):   
    for j in range(4,10):
        if j==i*2+2 or j == i*2+3:
            f.edge(str(i), str(j))
            
for i in range(4, 10):
    for j in range(10, 16):
        if j == i+6:
            f.edge(str(i), str(j))

for i in range(10, 16):
    for j in range(16, 22):
        if j == i+6:
            f.edge(str(i), str(j))

#Root node
f.node("0","Berlin")

#Leaves
for i in range(16, 22):
    f.node(str(i), "Berlin")

#Stop 1
for i in range(1,4):
    f.node(str(i), cities[i])

#Stop 2 add nodes
f.node(str(4), "Hamburg")
f.node(str(9), "Hamburg")
f.node(str(11), "Hamburg")
f.node(str(14), "Hamburg")

f.node(str(5), "Munich")
f.node(str(7), "Munich")
f.node(str(10), "Munich")
f.node(str(12), "Munich")

f.node(str(6), "Dusseldorf")
f.node(str(8), "Dusseldorf")
f.node(str(13), "Dusseldorf")
f.node(str(15), "Dusseldorf")
            
f

结果图如图所示，其中包含从柏林开始到柏林结束的所有可能路径，访问所有其他城市一次：

我已经手动为每个节点提供了标签。但是有没有一个过程可以自动化它来为这种图的各个节点提供标签？是否可以使用 graphviz、NetworkX 或在 Python 中的 pandas 等任何其他软件包的帮助下完成此操作？

Answer 1

networkx 似乎对一切都有一个功能：

from itertools import permutations
import networkx as nx

def make_tsp_tree(cities):
    start, *rest = cities
    paths = [(start, *path, start) for path in permutations(rest)]
    G = nx.prefix_tree(paths)
    # remove synthetic root and leaf nodes
    G.remove_nodes_from([0, -1])
    return G

根节点为1，城市名称存储在节点属性source中。将其转换为 graphviz 或您需要的任何内容应该很简单。

快速使用示例：

pos = nx.nx_agraph.graphviz_layout(G, "dot", root=1)
nx.draw_networkx_nodes(G, pos, node_color="C1")
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos, labels=dict(G.nodes(data="source")))

如何使用 Python 中的 networkx 或 graphviz 为旅行商问题中的所有可能路径自动创建有向图？

How to automate creating directed graph using networkx or graphviz in Python for all possible paths in a travelling salesman problem?

python

python-3.x

graph

networkx

graphviz