Solución:
Según tengo entendido, los criterios de creación del subgráfico dependen de los nodos accesibles desde el nodo de entrada. Entonces, la siguiente función recursiva debería ser suficiente para realizar el trabajo.
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)
Copié su código para crear el gráfico, inicialicé un gráfico Dirigido vacío y llamé a la función de la siguiente manera:
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)
El Dígrafo resultante se muestra en la figura.
El uso de algoritmos transversales integrados puede obtener un mejor rendimiento, admitir la opción bidireccional y evitar la limitación de profundidad recursiva.
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)
O la versión concisa para unidirección:
def create_subgraph(G, node):
nodes = nx.single_source_shortest_path(G,node).keys()
return G.subgraph(nodes)
La versión incorporada es 3 veces más rápida que la recursiva en mi caso. Subgrafia 3000 de 5000 nodos:
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
El resultado de create_subgraph (G, 3) se muestra en la figura:
Para ampliar el comentario críptico de @vaettchen sobre cómo extraer un subgráfico de un archivo de puntos
-
agarra un
gvpr
archivo de comando,reduce.g
de https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g -
correr
gvpr
sobrereduce.g
:
gvpr -f reduce.g -a '"3" 10' mygraph.dot > myreduced.graph.dot
dónde -a
son los parámetros de la reduce.g
programa, es decir, nodo de destino = 3 y saltos a seguir. Si te saltas -a
te lo dirá.
This script takes exactly two parameter. 1: name of node, 2: number of hops
Ahora, tal como está reduce.g
parece modificar bastante el gráfico: cambié de orientación horizontal a vertical.
Por cierto, ya que la alimentación de parámetros en bash
El script me dejó un poco perplejo con las citas, estoy agregando lo que funciona.
gvpr -f reduce.g -a " "$node_to_select" 10" mygraph.dot