He estado jugando con esto los últimos días.
Primero intenté hacer que cada nodo mantuviera un conjunto de refs en los bordes, y cada borde mantuviera un conjunto de refs en los nodos. Los configuré iguales en un tipo de operación (dosync... (ref-set...)). No me gustó porque cambiar un nodo requiere una gran cantidad de actualizaciones, e imprimir el gráfico fue un poco complicado. Tuve que anular el multimétodo print-method para que la réplica no se superpusiera. Además, cada vez que quería agregar una ventaja a un nodo existente, primero tenía que extraer el nodo real del gráfico, luego hacer todo tipo de actualizaciones de bordes y ese tipo de cosas para asegurarme de que todos se aferraran a la versión más reciente. de la otra cosa. Además, como las cosas estaban en una referencia, determinar si algo estaba conectado a otra cosa era una operación en tiempo lineal, que parecía poco elegante.No llegué muy lejos antes de determinar que realizar algún algoritmo útil con este método sería difícil.
Luego probé otro enfoque que es una variación de la matriz a la que se hace referencia en otro lugar. El gráfico es un mapa clojure, donde las claves son los nodos (no refs a los nodos) y los valores son otro mapa en el que las claves son los nodos vecinos y el valor individual de cada clave es el borde de ese nodo, representado como un valor numérico que indica la fuerza del borde o una estructura de borde que definí en otro lugar.
Parece que este, más o menos, por 1->2, 1->3, 2->5, 5->2
(def graph {node-1 {node-2 edge12, node-3 edge13},
node-2 {node-5 edge25},
node-3 nil ;;no edge leaves from node 3
node-5 {node-2 edge52}) ;; nodes 2 and 5 have an undirected edge
Para acceder a los vecinos del nodo-1 que vaya (keys (graph node-1)) o llamar a la función definida en otro lugar (neighbors graph node-1), o se puede decir ((graph node-1) node-2) a obtener la ventaja de 1->2.
varias ventajas:
- constante de tiempo de búsqueda de un nodo en el gráfico y de un nodo vecino, o de regreso nil si no existe.
- Definición de borde simple y flexible. Un borde dirigido existe implícitamente cuando agrega un vecino a una entrada de nodo en el mapa, y su valor (o una estructura para más información) se proporciona explícitamente, o nulo.
- No tiene que buscar el nodo existente para hacer algo al respecto. Es inmutable, por lo que puede definirlo una vez antes de agregarlo al gráfico y luego no tiene que perseguirlo para obtener la última versión cuando las cosas cambian. Si una conexión en el gráfico cambia, usted cambia la estructura del gráfico, no los nodos/bordes mismos.
- Esto combina las mejores características de una representación matricial (la topología del gráfico está en el mapa gráfico no codificado en los nodos y bordes, búsqueda de tiempo constante y nodos y bordes no mutantes) y la lista de adyacencia (cada el nodo "tiene" una lista de sus nodos vecinos, espacio eficiente ya que no tiene ningún "espacio en blanco" como una matriz dispersa canónica).
- Puede tener múltiples bordes entre los nodos, y si define accidentalmente un borde que ya existe exactamente, la estructura del mapa se encarga de asegurarse de no duplicarlo.
- Clojure mantiene la identidad del nodo y el borde. No tengo que inventar ningún tipo de esquema de indexación o punto de referencia común. Las claves y valores de los mapas son las cosas que representan, no una búsqueda en otra parte o ref. La estructura de su nodo puede ser nula y, siempre que sea única, se puede representar en el gráfico.
La única gran desventaja que veo es que para cualquier operación dada (agregar, eliminar, cualquier algoritmo), no se puede simplemente pasarle un nodo inicial. Debe pasar todo el mapa del gráfico y un nodo inicial, que probablemente sea un precio justo a pagar por la simplicidad de todo. Otra desventaja menor (o tal vez no) es que para un borde no dirigido debe definir el borde en cada dirección. Esto está realmente bien porque a veces un borde tiene un valor diferente para cada dirección y este esquema te permite hacer eso.
La única otra cosa que veo aquí es que debido a que un borde está implícito en la existencia de un par clave-valor en el mapa, no se puede definir un hiperenlace (es decir, uno que conecte más de 2 nodos). No creo que esto sea necesariamente un gran problema ya que la mayoría de los algoritmos de gráficos que he encontrado (¿todos?) Solo tratan con una ventaja que conecta 2 nodos.
¿En qué granularidad necesitas inmutabilidad?Si construyes tus gráficos cíclicos dentro de una función y la mutación necesaria de los nodos "nunca se ve", obtienes un gráfico cíclico inmutable devuelto por la función. Ver http://clojure.org/transients –
@Alex: esto suena como un enfoque realmente interesante. Estoy de acuerdo con que el gráfico sea mutable durante la construcción si es necesario. Principalmente quiero asegurarme de que sea inmutable después de la construcción, así puedo entregárselo a quienes llaman sin preocuparse. Sin embargo, no he podido descifrar cómo construir una estructura de datos cíclicos con 'transient'. ¿Tiene algún código de ejemplo que ilustre esta idea, incluso para algo tan simple como un vector consigo mismo como elemento? –