¿Qué estructura de datos podría usar para modelar una red de nodos y bordes?

7

Mi aplicación necesita modelar y realizar operaciones en una red con 40 a 50 nodos y, por lo general, menos de 6 bordes por nodo. Tanto los nodos como los bordes son objetos con alrededor de 1K de datos cada uno. Durante la ejecución, la asignación de la red se cambia con frecuencia: se agregan y eliminan nodos, se agregan y eliminan bordes, además de las propiedades de nodos y bordes individuales que se ajustan. Los objetos de nodo y los objetos de borde se asignan usando 'nuevo' con los punteros resultantes almacenados en un std::list para cada tipo de objeto.

He experimentado con dos enfoques diferentes para el mapeo:

  1. Coloque un contenedor en cada nodo para contener las ID de los bordes y 2 variables en cada borde para almacenar las ID de los nodos finales.

  2. Agregue un nuevo contenedor de nivel superior, separado del contenedor de bordes y contenedor de nodos, para almacenar la información de mapeo.

Las funciones en las clases de nodo y miembro serán más fáciles de implementar, si la información de mapeo se almacena en esas clases. Realizar cambios en la asignación de la red sería mucho más fácil si todos los datos de la asignación se almacenaran por separado. Pero si la asignación no se almacena en los nodos y bordes, entonces las funciones miembro en los nodos y bordes necesitan una forma de obtener información de asignación del objeto principal.

¿Existe una estructura de datos o una técnica conceptual que ofrezca lo mejor de ambos enfoques, sin duplicar datos ni romper la encapsulación? El rendimiento no es una preocupación importante, ya que no hay cálculos extremadamente costosos involucrados. La preocupación más importante es el código seguro, comprensible y mantenible.

    
pregunta Mark Taylor 10.02.2012 - 00:02

2 respuestas

5

Graphs se puede implementar de muchas maneras, y la que usted describió no está mal.

Para C ++, creo que debería echar un vistazo a las bibliotecas Boost C ++ (BGL) que también tienen una library específicamente para implementar gráficos . Si usa eso, también puede usar algoritmos implementados en BGL (búsquedas y recorridos) o incluso usar los visitantes _edge y _vertex directamente.

    
respondido por el Spoike 10.02.2012 - 08:30
1

He implementado operaciones de red en Python. Aquí está mi solución.

  • una clase Node que posee una lista de Port s
  • cada objeto Port tiene atributos destination , proper_direction y back_port
  • Node proporciona funciones de enlace y garantiza que para cada objeto Port en su lista tenga otro puerto back-port. Port se crea en el nodo de destino con el proper_direction negativo y también se hace referencia a este puerto trasero mediante back_port

De esta manera, los nodos se unen mediante un par de puertos en ambas direcciones con direcciones correctas. Haga los punteros C según corresponda: en Python no nos interesan los punteros ;-)

Para almacenar datos en cada nodo, derive una subclase que agrega una asignación. Si también quiero almacenar datos en cada enlace, emulo los enlaces por los objetos Node y básicamente los objetos y los enlaces (ambos nodos) por puertos.

Esta estructura de datos resultó ser realmente conveniente para la búsqueda y las operaciones de la red.

    
respondido por el Gerenuk 10.02.2012 - 09:24

Lea otras preguntas en las etiquetas