查找网络图中的所有对

Question

我正在解决一个问题。我有一个 pandas DataFrame，其中包含 Source、Target 和 Freq 列。

假设我对节点 1 感兴趣。节点 1 可以link按以下方式编辑。

Source Target
5 1
3 5
2 3
6 2

5 是源，1 是目标，3 是源，5 是目标，link 继续。我本质上是在尝试创建一个网络图，它将 b 6-2-3-5-1.

有没有什么方法可以通过编程方式找到最终会出现在我选择的 Target 中的所有源-目标组合？

编辑：已编辑以提供更多说明。

Answer 1

Is there any way to programmatically find the all source-target combinations

是的，这被称为 Shortest path problem，给定一个由 nodes/vertices V[=32 构造的图 G =] 由边 E 连接找到源节点和目标节点之间的最短路径。您指定的是一个边列表，其中每个边将某个节点 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]

find the all source-target combinations

NetworkX 提供 many algorithms 您应该与您要解决的特定用例相匹配。要找到给定源节点和目标节点的所有可能路径，

# 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]]

all source-target combinations (...) that would eventually end up in a target of my choice

我们想要找到所有可能的源节点和最终以我们选择的目标结束的路径，而不指定源节点：

# 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]]