在网络图中找到所有的配对。

Question

我正在尝试解决一个问题。我有一个带有“来源”、“目标”和“频率”列的pandas DataFrame。

假设我对节点1感兴趣。节点1可以以下面的方式链接。

Source Target
5 1
3 5
2 3
6 2

当1是目标时，5是源头；当5是目标时，3是源头，链接继续。我基本上想创建一个网络图，它将是6-2-3-5-1。

有没有办法通过编程找到所有的源-目标组合，最终会到达我选择的目标？

- Samira Kumar

Answer 1

有没有办法以编程方式找到所有的源-目标组合

是的，这被称为最短路径问题，即给定由节点/顶点V连接的边E构成的图G，找到源节点和目标节点之间的最短路径。您需要指定一系列边，其中每个边将某个节点v（i）连接到另一个节点v（j）。

有几种算法可以实现解决方案。您可以使用类似于NetworkX的库，因此无需自己实现算法。例如，

# let's create the data frame as per your example
import pandas as pd
df = pd.DataFrame([
        (5, 1),
        (3, 5),
        (2, 3),
        (6, 2),
    ], columns=['source', 'target'])

# import networkx and build the graph
import networkx as nx
G = nx.Graph()
G.add_edges_from(df.values)

# import the shortest_paths generic algorithm
nx.shortest_path(G, source=6, target=1)
=> 
[6, 2, 3, 5, 1]

找到所有的源-目标组合

NetworkX提供许多算法，您应该将其与您试图解决的特定用例匹配。要查找给定源节点和目标节点的所有可能路径，

# assume we have added another edge source=6 target=1 
list(nx.all_simple_paths(G, source=6, target=1))
=> 
[[6, 1], [6, 2, 3, 5, 1]]

我们希望找到所有可能的源节点和路径，最终到达我们选择的目标，而不指定源节点。

# find all start/end nodes
import networkx as nx
# -- we need a directed graph
dG = nx.DiGraph()
dG.add_edges_from(df.values)
# -- find possible source nodes
source_nodes = [x for x in G.nodes_iter() if dG.out_degree(x) >= 1]
# -- for every source node find the shortest path to target
paths = [nx.shortest_path(G, source=source, target=1) for source in source_nodes]
paths
=>
[[2, 3, 5, 1], [3, 5, 1], [5, 1], [6, 2, 3, 5, 1]]

- miraculixx

---

你好。感谢提供的解决方案。在Networkx 2.0中有一个更新，即G.nodes_iter()已被移除。他们在网站上的评论是：“一个示例是G.nodes（或G.nodes()），它现在返回类似于字典的NodeView，而G.nodes_iter()已被移除。” 谢谢。 - Samira Kumar