Поиск Подключенных Компонентов Networkx

Мне нужно найти связанные узлы в неориентированном и взвешенном графе. Я действительно искал здесь некоторые предложения, но никто не ответил, что связано с моей проблемой. Эти пары узлов, которые также соединяются с соседями, и каждая пара при соединении тратит некоторое время в секундах на соединение.Я пытаюсь найти связанные компоненты и количество времени, в течение которого те же комментарии соединяются, и как долго (время) они соединяются.

Например: 

Node  Node time
A      B    34
A      B    56
A      C    09
A      D    5464
A      C    456
C      B    36
C      A    345
B      C    346

Так что над всеми A B C связаны два времени 

Nodes   connected  time
[A B C]    1       34+09+36 = 79
[A B C]    1       56+345+346 = 747

Ожидаемый результат - 

Nodes  connected  time 
[A B C]    2       826

And

Node  connected  time
[A B]   2         90
[B C]   2         382
[A C]   2         354

Код: 

import networkx as nx
import numpy as np
from collections import defaultdict

count = defaultdict(int)
time = defaultdict(float)

data = np.loadtxt('USC_Test.txt')

for line in data:
    edge_list = [(line[0], line[1])]
    G= nx.Graph()
    G.add_edges_from(edge_list)
    components = nx.connected_components(G)
    count['components'] += 1
    time['components'] += float(line[2])

print components, count['components'], time['components']

Вход: 

5454 5070 2755.0
5070 4391 2935.0
1158 305  1.0
5045 3140 48767.0
4921 3140 58405.0
5372 2684 460.0
1885 1158 351.0
1349 1174 6375.0
1980 1174 650.0
1980 1349 650.0
4821 2684 469.0
4821 937  459.0
2684 937  318.0
1980 606  390.0
1349 606  750.0
1174 606  750.0
5045 3545 8133.0
4921 3545 8133.0
3545 3140 8133.0
5045 4243 14863.0
4921 4243 14863.0
4243 3545 8013.0
4243 3140 14863.0
4821 4376 5471.0
4376 937  136.0
2613 968  435.0
5372 937  83.0

Неправильный Вывод

Вывод, который я получаю, неверен 

Last_node_pair  total_count_of_line  total_time  of Entire input data

Куда как я должен попасть 

[5045 3140 4921]  [number_of_times_same_components_connected]   [total_time_components_connected]
1 4
python networkx

1 ответ:

Здесь есть несколько вопросов:

  1. вы воссоздаете график на каждой итерации, поэтому у вас всегда есть только одно ребро в вашем графике.
  2. вы используете литеральную строку "components" вместо переменной components в качестве индекса, поэтому вы только сохраняете и отображаете это единственное значение в ваших словарях результатов.
  3. вы печатаете результат только один раз, в конце. Там переменная components оказывается последней компонентой в графике (это последняя вещь, назначенная этой переменной цикла), и вы распечатываете общее количество компонентов и время, которое является общим количеством компонентов и временем для всех компонентов из-за проблемы № 2.

Вот что должно сработать. Из лени я дважды просматриваю данные.

import networkx as nx
import numpy as np
from collections import defaultdict

count = defaultdict(int)
time = defaultdict(float)

data = np.loadtxt('USC_Test.txt')
G = nx.Graph()
for line in data:
    a,b,time = line
    G.add_edge(a, b)

results = defaultdict(lambda: list([0, 0.0]))
components = nx.connected_components(G)
component_map = { } 
component_stats = defaultdict(lambda: list([0,0.0]))
edge_stats = defaultdict(lambda: list([0,0.0]))
for nodes in components:
    for node in nodes:
        component_map[int(node)] = tuple(nodes)

for a,b,time in data:
    component_stats[component_map[a]][0] += 1
    component_stats[component_map[a]][1] += time

    if len(component_map[a]) > 2:
        edge_stats[(a,b)][0] += 1
        edge_stats[(a,b)][1] += time

for nodes,(count,time) in component_stats.iteritems():
    print sorted([ int(n) for n in nodes ]), count, time

print

for nodes,(count,time) in edge_stats.iteritems():
    print sorted([ int(n) for n in nodes ]), count, time

С вашим входом это приводит к следующему выходу: 

[606, 1174, 1349, 1980] 6 9565.0
[305, 1158, 1885] 2 352.0
[968, 2613] 1 435.0
[937, 2684, 4376, 4821, 5372] 7 7396.0
[4391, 5070, 5454] 2 5690.0
[3140, 3545, 4243, 4921, 5045] 9 184173.0

[1349, 1980] 1 650.0
[937, 4376] 1 136.0
[606, 1980] 1 390.0
[3140, 4921] 1 58405.0
[937, 5372] 1 83.0
[606, 1349] 1 750.0
[4391, 5070] 1 2935.0
[3545, 4921] 1 8133.0
[1158, 1885] 1 351.0
[3140, 3545] 1 8133.0
[2684, 4821] 1 469.0
[2684, 5372] 1 460.0
[937, 2684] 1 318.0
[1174, 1980] 1 650.0
[3140, 5045] 1 48767.0
[5070, 5454] 1 2755.0
[4376, 4821] 1 5471.0
[606, 1174] 1 750.0
[3545, 5045] 1 8133.0
[4243, 4921] 1 14863.0
[3140, 4243] 1 14863.0
[4243, 5045] 1 14863.0
[937, 4821] 1 459.0
[3545, 4243] 1 8013.0
[1174, 1349] 1 6375.0
[305, 1158] 1 1.0

Надеюсь, это поможет!

2