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.

Може ли някой да ми покаже как да направя това? Би било хубаво, ако получената графика също е диграф


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