Saltar al contenido

NetworkX DiGraph crea subgrafo (DiGraph) por nodo

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

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

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

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

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

¡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 *