Algoritmo para crear estructuras de networking tipo tree

Estoy tratando de modelar proceduralmente estructuras de networking tipo tree con las siguientes properties:

  • Una raíz con número variable de nodos
  • Una profundidad variable de nodos
  • Cuando se presenta gráficamente, los bordes o nodos nunca deben cruzarse o superponerse

No tengo experiencia en matemáticas o progtwigción, por lo que no estoy seguro de estar usando la terminología correcta. Quizás una image explique mejor lo que busco:

enter image description here

Conozco bastante bien a Ruby, así que creo que debería poder implementar un algorithm básico que genere estos models. ¿Alguna sugerencia o sugerencia?

El dibujo gráfico es un poco más directamente relevante que todo el campo de la teoría de grafos.

En particular, soy un fanático del layout basado en la fuerza. Vea esta demostración de la biblioteca D3 para una introducción.

La idea básica es modelar los bordes del gráfico con resortes o repulsores, y usar un método de integración física para "resolver" las posiciones de todos los nodos. Puede hacerlo en time real como en la demostración anterior, lo cual es divertido pero también molesto, o puede realizar una serie de iteraciones de física antes de renderizar un layout estático final .

Esa biblioteca D3 tiene una gran cantidad de otros modos de layout para inspirarte, y estar basado en JavaScript es una gran manera de prototipar o experimentar con cualquier algorithm de layout que te interese.

Primero, para que su gráfico obedezca la propiedad crucial de any two edges do not cross , debe ser un gráfico plano .

Aquí se brinda un pequeño tutorial sobre el tema de dibujo de charts.

Usar layouts impulsados ​​por fuerza no puede garantizar la convergencia a un gráfico plano: (por ejemplo, si un vértice está dentro de una cara, aplique una fuerza de resorte elástica y empuje el vértice fuera de la cara utilizando el borde más cercano normal). Este enfoque sería interesante para animar, pero podría no converger (a less que se haya probado en algún lugar …).

Entonces, aunque no puedo reproducir aquí un algorithm para desennetworkingar un gráfico plano (o simplemente dibujarlo en su forma canónica), hay muchos resources que tratan el tema (algunos en time lineal):

NOTA : si su gráfico es un tree , entonces sugiero leer esto .

RELACIONADO : "Desennetworkingar" -Game AI

Podrías usar alguna forma de Colonización Espacial.

Ejemplos ProcWorld y Sea of ​​Memes muestran cada vez más 'treees reales', pero probablemente podrían adaptarse para estructuras arbóreas arbitrarias.

La colonización espacial asume que tienes un área limitada para ser llenada por una 'forma de vida' competitiva que crece en una o más iteraciones. Este aspecto competitivo puede no ajustarse a lo que usted desea hacer, si solo desea generar treees / charts aleatorios sin superposition.

EDITAR:

La colonización espacial tiene ciertas condiciones en el crecimiento que creo que garantizan que no se superpongan los bordes (y normalmente procesarías el tree de todos modos), pero solo te ayudará si aún no tienes un gráfico / tree.

Entonces, si ya tiene un gráfico, Space Colonization no lo ayudará: vea otras respuestas como el layout basado en la fuerza de @ Sean. Si está generando un gráfico mientras también necesita diseñarlo (o puede almacenar información de position para más adelante), esto podría ser lo que necesita.