Групповые связные графы в пандах Д. Ф. - PullRequest
Новая
       6

Групповые связные графы в пандах Д. Ф.

0 голосов
/ 01 декабря 2018

У меня есть DF pandas, где каждый столбец представляет собой узел, а два столбца - ребро, как показано ниже: 

 import pandas as pd
df = pd.DataFrame({'node1': ['2', '4','17', '17', '205', '208'],
               'node2': ['4', '13', '25', '38', '208', '300']})

Все узлы являются ненаправленными, т.е. вы можете переходить от одного к другому undirected_graph

Я хотел бы сгруппировать их во все связанные группы (Связность) следующим образом: 

df = pd.DataFrame({'node1': ['2', '4','17', '17', '205', '208'],
           'node2': ['4', '13', '25', '38', '208', '300']
            ,'desired_group': ['1', '1', '2', '2',  '3', '3']})

Например, причина, по которой первые двастроки были сгруппированы, потому что можно было добраться от узла 2 к узлу 13 (через 4).

Самый близкий вопрос, который мне удалось найти, это: pandas - преобразование кадра данных в список краев согласнок значениям столбцов , но, насколько я понимаю, это другой вопрос.

Любая помощь по этому вопросу будет большой, заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 01 декабря 2018

Если по какой-то причине вы не можете использовать внешнюю библиотеку, вы можете реализовать алгоритмы: 

import pandas as pd


def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited


def connected_components(G):
    seen = set()
    for v in G:
        if v not in seen:
            c = set(bfs(G, v))
            yield c
            seen.update(c)


def graph(edge_list):
    result = {}
    for source, target in edge_list:
        result.setdefault(source, set()).add(target)
        result.setdefault(target, set()).add(source)
    return result


df = pd.DataFrame({'node1': ['2', '4', '17', '17', '205', '208'],
                   'node2': ['4', '13', '25', '38', '208', '300']})

G = graph(df[['node1', 'node2']].values)
components = connected_components(G)
lookup = {i: component for i, component in enumerate(components, 1)}
df['group'] = [label for node in df.node1 for label, component in lookup.items() if node in component]
print(df)

Вывод 

  node1 node2  group
0     2     4      1
1     4    13      1
2    17    25      3
3    17    38      3
4   205   208      2
5   208   300      2
0 голосов
/ 01 декабря 2018

Использование networkx connected_components

import networkx as nx

G=nx.from_pandas_edgelist(df, 'node1', 'node2')

l=list(nx.connected_components(G))

L=[dict.fromkeys(y,x) for x, y in enumerate(l)]

d={k: v for d in L for k, v in d.items()}

#df['New']=df.node1.map(d)
df.node1.map(d)
0    0
1    0
2    1
3    1
4    2
5    2
Name: node1, dtype: int64
...