Recuerda que en la informática un error suele tener diversas soluciones, por lo tanto nosotros mostraremos lo más óptimo y eficiente.
Solución:
Según tengo entendido, el criterio de creación del subgrafo depende 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 incorporados 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 unidireccional:
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. Se subgraph 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 profundizar en el comentario críptico de @vaettchen sobre cómo extraer un subgráfico de un archivo de puntos
-
agarrar un
gvpr
archivo de comando,reduce.g
de https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g -
correr
gvpr
enreduce.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 objetivo=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
script me dejó perplejo un poco con las comillas, estoy agregando lo que funciona.
gvpr -f reduce.g -a " "$node_to_select" 10" mygraph.dot
Comentarios y puntuaciones de la guía
Nos puedes proteger nuestra función escribiendo un comentario o dejando una puntuación te estamos agradecidos.