Saltar al contenido

NetworkX DiGraph crear subgrafo (DiGraph) por nodo

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.ingrese la descripción de la imagen aquí

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:
ingrese la descripción de la imagen aquí

Para profundizar en el comentario críptico de @vaettchen sobre cómo extraer un subgráfico de un archivo de puntos

  1. agarrar un gvpr archivo de comando, reduce.g de https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g

  2. correr gvpr en reduce.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.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *