NetworkX DiGraph создает подграф (DiGraph) по узлам

Я хотел бы получить подграф (красную область) по узлу: подграф состоит из всех узлов, доступных из входного узла.

подобно G.subgraph (3) возвращает новый DiGraph из красной области.

введите здесь описание изображения

Например, я создаю DiGraph следующим образом:

import networkx as nx
G = nx.DiGraph()

G.add_path([1,2,3,4])
G.add_path([3,'a','b'])

A = nx.to_agraph(G)
A.layout()
A.draw('graph.png')

Я просмотрел https://networkx.github.io/documentation/latest/reference/generated/networkx.Graph.subgraph.html и преобразовав его в однонаправленный. Я тестировал out_egdes, strong / weak_connected_component, но он никогда не работал. Я также посмотрел Как найти подграфы в ориентированном графе без преобразования в неориентированный граф? и Networkx: извлеките компонент связности, содержащий данный узел (ориентированный граф).

Я знаю, что Subgraph не работает в DiGraph.

Кто-нибудь может показать мне, как это сделать? Было бы неплохо, если бы результирующий Graph также был DiGraph


python networkx subgraph
person svenhornberg    schedule 04.10.2015    source источник
comment
Не могли бы вы прояснить, как вы хотите, чтобы подграф создавался. Это все узлы, до которых можно добраться из данного узла ввода?   -  person Abdallah Sobehy    schedule 06.10.2015
comment
да это то, что я искал. извините, я не разъяснил это. кстати отлично работает   -  person svenhornberg    schedule 06.10.2015

Ответы (3)


arrow_upward
5
arrow_downward

Насколько я понимаю, критерии создания подграфа зависят от узлов, доступных из входного узла. Тогда следующей рекурсивной функции должно быть достаточно для выполнения работы.

def create_subgraph(G,sub_G,start_node):
    for n in G.successors_iter(start_node):
        sub_G.add_path([start_node,n])
        create_subgraph(G,sub_G,n)

Я скопировал ваш код, чтобы создать график, инициализировал пустой направленный граф и вызвал функцию следующим образом:

G = nx.DiGraph()
G.add_path([1,2,3,4])
G.add_path([3,'a','b'])
sub_G = nx.DiGraph()
create_subgraph(G, sub_G,3)

Полученный диграф показан на рисунке. введите описание изображения здесь

person Abdallah Sobehy    schedule 06.10.2015

arrow_upward
4
arrow_downward

Чтобы подробнее рассказать о загадочном комментарии @ vaettchen к Как извлечь подграф из точечный файл

  1. возьмите gvpr командный файл, reduce.g из https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g

  2. запустить gvpr на reduce.g:

gvpr -f reduce.g -a '"3" 10' mygraph.dot > myreduced.graph.dot

где -a - параметры программы reduce.g, т. е. целевой узел = 3 и следующие переходы. Если вы пропустите -a, он расскажет вам об этом.

This script takes exactly two parameter. 1: name of node, 2: number of hops

Теперь, когда он стоит, reduce.g, похоже, немного изменил график - я переключился с горизонтальной на вертикальную ориентацию.

Кстати, поскольку ввод параметров в сценарий bash немного озадачил меня кавычками, я добавляю то, что действительно работает.

gvpr -f reduce.g -a " \"$node_to_select\" 10" mygraph.dot

person JL Peyret    schedule 13.06.2018

arrow_upward
3
arrow_downward

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

def create_subgraph(G, node):
    edges = nx.dfs_successors(G, node)
    nodes = []
    for k,v in edges.items():
        nodes.extend([k])
        nodes.extend(v)
    return G.subgraph(nodes)

Или краткий вариант для однонаправленного текста:

def create_subgraph(G, node):
    nodes = nx.single_source_shortest_path(G,node).keys()
    return G.subgraph(nodes)

В моем случае встроенная версия в 3 раза быстрее, чем рекурсивная. Это подграф 3000 из 5000 узлов:

In [1]: %timeit -n10 use_built_in('O_CONTRACT_PRODUCT') 
10 loops, best of 3: 102 ms per loop 

In [2]: %timeit -n10 use_recursive('O_CONTRACT_PRODUCT')
10 loops, best of 3: 341 ms per loop

Результат create_subgraph (G, 3) показан на рисунке: введите описание изображения здесь

person Jesse    schedule 14.08.2017