tutorial - ¿Cómo remodelar un gráfico networkx en Python?

networkx tutorial

Question

Así que creé una manera realmente ingenua (probablemente ineficiente) de generar diagramas hasse.

Pregunta:

Tengo 4 dimensiones ... p q r s .

Quiero mostrarlo de manera uniforme (tesseract) pero no tengo idea de cómo remodelarlo. ¿Cómo se puede remodelar un gráfico networkx en Python?

He visto algunos ejemplos de personas que usan spring_layout() y draw_circular() pero no se draw_circular() a la forma que estoy buscando porque no son uniformes.

¿Hay alguna forma de remodelar mi gráfica y uniformarla? (es decir, remodelar mi diagrama hasse en una forma de tesseract (preferiblemente usando nx.draw() )

Así es como se ve la mía actualmente:

Aquí está mi código para generar el diagrama hasse de N dimensiones

#!/usr/bin/python

import networkx as nx
import matplotlib.pyplot as plt
import itertools

H = nx.DiGraph()

axis_labels = [''p'',''q'',''r'',''s'']

D_len_node = {}

#Iterate through axis labels
for i in xrange(0,len(axis_labels)+1):
    #Create edge from empty set
    if i == 0:
        for ax in axis_labels:
            H.add_edge(''O'',ax)
    else:
        #Create all non-overlapping combinations
        combinations = [c for c in itertools.combinations(axis_labels,i)]
        D_len_node[i] = combinations
    #Create edge from len(i-1) to len(i) #eg. pq >>> pqr, pq >>> pqs
    if i > 1:
        for node in D_len_node[i]:
            for p_node in D_len_node[i-1]:
                #if set.intersection(set(p_node),set(node)): Oops
                if all(p in node for p in p_node) == True: #should be this!
                    H.add_edge(''''.join(p_node),''''.join(node))

#Show Plot
nx.draw(H,with_labels = True,node_shape = ''o'')
plt.show() 

Quiero remodelarlo así:

Si alguien sabe de una manera más fácil de hacer diagramas Hasse, por favor comparta algo de sabiduría, pero ese no es el objetivo principal de esta publicación.

Answer 1

Esta es una respuesta pragmática, más que puramente matemática.

Creo que tienes dos problemas, uno con el diseño y otro con la red.

1. red

Tiene demasiados bordes en su red para que represente la unidad tesseract. Advertencia : no soy un experto en matemáticas aquí, solo llegué a esto desde el ángulo de trazado (etiqueta de matplotlib). Por favor explique si estoy equivocado.

La proyección deseada y, por ejemplo, la página wolfram mathworld para un diagrama de Hasse para n = 4 tiene solo 4 bordes conectados a todos los nodos, mientras que tiene 6 bordes para los bordes de 2 y 7 para los nodos de 3 bits. Su gráfico conecta completamente cada "nivel", es decir, los vectores 4-D con valores 0 1 se conectan a todos los vectores con valor 1 1 , que luego se conectan a todos los vectores con valores 2 1 y así sucesivamente. Esto es más obvio en la proyección basada en la respuesta de Wikipedia (2da imagen a continuación)

2. Proyección

No pude encontrar un algoritmo o biblioteca escrito previamente para proyectar automáticamente el tesseract 4D en un plano 2D, pero sí encontré un par de ejemplos, por ejemplo , Wikipedia . A partir de esto, puede elaborar un conjunto de coordenadas que le convenga y pasarlo a la llamada nx.draw() .

Aquí hay un ejemplo: he incluido dos conjuntos de coordenadas, uno que se parece a la proyección que se muestra arriba, uno que coincide con este de wikipedia .

import networkx as nx
import matplotlib.pyplot as plt
import itertools

H = nx.DiGraph()

axis_labels = [''p'',''q'',''r'',''s'']

D_len_node = {}

#Iterate through axis labels
for i in xrange(0,len(axis_labels)+1):
    #Create edge from empty set
    if i == 0:
        for ax in axis_labels:
            H.add_edge(''O'',ax)
    else:
        #Create all non-overlapping combinations
        combinations = [c for c in itertools.combinations(axis_labels,i)]
        D_len_node[i] = combinations
    #Create edge from len(i-1) to len(i) #eg. pq >>> pqr, pq >>> pqs
    if i > 1:
        for node in D_len_node[i]:
            for p_node in D_len_node[i-1]:
                if set.intersection(set(p_node),set(node)):
                    H.add_edge(''''.join(p_node),''''.join(node))

#This is manual two options to project tesseract onto 2D plane 
# - many projections are available!!
wikipedia_projection_coords = [(0.5,0),(0.85,0.25),(0.625,0.25),(0.375,0.25),
                                (0.15,0.25),(1,0.5),(0.8,0.5),(0.6,0.5),
                                (0.4,0.5),(0.2,0.5),(0,0.5),(0.85,0.75),
                                (0.625,0.75),(0.375,0.75),(0.15,0.75),(0.5,1)]

#Build the "two cubes" type example projection co-ordinates
half_coords = [(0,0.15),(0,0.6),(0.3,0.15),(0.15,0),
               (0.55,0.6),(0.3,0.6),(0.15,0.4),(0.55,1)]
#make the coords symmetric
example_projection_coords = half_coords + [(1-x,1-y) for (x,y) in half_coords][::-1]

print example_projection_coords


def powerset(s):
    ch = itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))
    return [''''.join(t) for t in ch]

pos={}
for i,label in enumerate(powerset(axis_labels)):
    if label == '''':
       label = ''O''
    pos[label]= example_projection_coords[i]

#Show Plot
nx.draw(H,pos,with_labels = True,node_shape = ''o'')
plt.show() 

Nota: a menos que cambie lo que he mencionado en 1. anterior, aún tienen su estructura de borde, por lo que no se verán exactamente como los ejemplos de la web. Esto es lo que parece con su código de generación de red existente: puede ver los bordes adicionales si lo compara con su ejemplo (p. Ej., No este pr debería estar conectado a pqs :

Proyección ''dos ​​cubos''

Ejemplo de proyección de Wikimedia.

Nota

Si quieres entrar en las matemáticas de hacer tus propias proyecciones (y construir una pos matemáticamente), puedes mirar este trabajo de investigación .

EDITAR:

La curiosidad me venció y tuve que buscar una forma matemática para hacer esto. Encontré este blog , cuyo resultado principal es la matriz de proyección:

Esto me llevó a desarrollar esta función para proyectar cada etiqueta, tomando la etiqueta que contiene ''p'' para indicar que el punto tiene valor 1 en el eje ''p'', es decir, estamos tratando con la unidad tesseract. Así:

def construct_projection(label):
    r1 = r2 = 0.5
    theta = math.pi / 6
    phi = math.pi / 3
    x = int( ''p'' in label) + r1 * math.cos(theta) * int(''r'' in label) - r2 * math.cos(phi) * int(''s'' in label)
    y = int( ''q'' in label) + r1 * math.sin(theta) * int(''r'' in label) + r2 * math.sin(phi) * int(''s'' in label)
    return (x,y)

Da una buena proyección en un octágono 2D regular con todos los puntos distintos.

Esto se ejecutará en el programa anterior, simplemente reemplazar

 pos[label] = example_projection_coords[i]

con

pos[label] = construct_projection(label)

Esto da el resultado:

juega con r1 , r2 , theta y phi al contenido de tu corazón :)