Найти все пары в диаграмме сети - PullRequest
Новая
       9

Найти все пары в диаграмме сети

0 голосов
/ 01 ноября 2018

Я пытаюсь решить проблему. У меня есть панды DataFrame с колонками Source, Target и Freq.

Предположим, я заинтересован в Узле 1. Узел 1 может быть связан ниже. 

Source Target
5 1
3 5
2 3
6 2

5 является источником, когда 1 является целью, а 3 является источником, когда 5 является целью, и связь продолжается. По сути, я пытаюсь создать сетевой график, который бы b 6-2-3-5-1 .

Есть ли какой-нибудь способ программно найти все комбинации источника и цели, которые в конечном итоге окажутся в Target по моему выбору?

Редактировать : отредактировано для уточнения.

1 Ответ

0 голосов
/ 01 ноября 2018

Есть ли способ программно найти все комбинации источника и цели

Да, это известно как проблема кратчайшего пути , для которой задан граф G , построенный из узлов / вершин V , соединенных ребрами 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]

найти все комбинации источник-цель

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