Обнаружение отдельных графиков в пределах объекта графа в NetworkX

У меня есть огромный набор данных графа - скажем, это так, но на гораздо большем уровне:Обнаружение отдельных графиков в пределах объекта графа в NetworkX

1 -> 2 
3 -> 4

1,2,3,4 являются узлами и стрелки - направленные ребра. Допустим, что все они находятся в одном объекте графа:

import networkx as nx 
G = nx.DiGraph() 
G.add_nodes_from([1,2,3,4]) 
G.add_edge(1,2) 
G.add_edge(3,4)

Учитывая такой объект, как это, у которого есть две мини-графики в пределах графика, как мы можем вытащить каждый мини-граф? Я чувствую, что для этого должно быть какое-то слово? Мой конечный результат будет выглядеть следующим образом:

for mini_graph in G: 
    print mini_graph.nodes() 

... 
[1,2] 
[3,4]

источник

2014-02-12 LittleBobbyTables

Я думаю, вы можете использовать [ 'weakly_connected_component_subgraphs'] (http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.components.weakly_connected.weakly_connected_component_subgraphs.html#networkx.algorithms.components. weakly_connected.weakly_connected_component_subgraphs), и если это так, то это дубликат: http://stackoverflow.com/questions/18643789/how-to-find-subgraphs-in-a-directed-graph-without-converting-to-undirected- graph – EdChum

Связано также: http://stackoverflow.com/questions/13914920/networkx-extract-the-smallest-connected-subgraph. Это зависит от того, как вы определяете подграфы здесь – EdChum

Если части графа действительно не пересекаются (в соответствии с малого, например), а затем рассмотреть извлекая подграфов с connected_component_subgraphs().

Это работает только на неориентированном графике, поэтому, если вы используете ориентированный граф, вам нужно сначала преобразовать в ненаправленный.

import networkx as nx 
G = nx.DiGraph() 
G.add_nodes_from([1,2,3,4]) 
G.add_edge(1,2) 
G.add_edge(3,4) 

# make an undirected copy of the digraph 
UG = G.to_undirected() 

# extract subgraphs 
sub_graphs = nx.connected_component_subgraphs(UG) 

for i, sg in enumerate(sub_graphs): 
    print "subgraph {} has {} nodes".format(i, sg.number_of_nodes()) 
    print "\tNodes:", sg.nodes(data=True) 
    print "\tEdges:", sg.edges()

, который дает:

subgraph 1 has 2 nodes 
    Nodes: [(1, {}), (2, {})] 
    Edges: [(1, 2)] 
subgraph 1 has 2 nodes 
    Nodes: [(3, {}), (4, {})] 
    Edges: [(3, 4)]

, и вы можете использовать подграф узел метки для работы на данных в исходном графе,

sg.nodes()[0] in G 
>>> True

Чтение ответ, связанный с помощью EdChum, он что weakly_connected_component_subgraphs() работает на ориентированном графике, но рассматривает его как ненаправленную, поэтому сохранение копии может иметь решающее значение. Тем не менее, документы по этому вопросу и связанная с ним функция weakly_connected_components() немного тонкие.

источник

2014-02-13 10:30:53 Bonlenfum

Обнаружение отдельных графиков в пределах объекта графа в NetworkX

ответ

Смежные вопросы