¿Cómo se pueden crear estructuras de datos cíclicas(e inmutables) en Clojure sin indirección adicional?

immutability directed-graph (3)

Necesito representar gráficos dirigidos en Clojure. Me gustaría representar cada nodo en el gráfico como un objeto (probablemente un registro) que incluye un campo llamado :edges que es una colección de nodos directamente accesibles desde el nodo actual. Espero que sea evidente, pero me gustaría que estos gráficos sean inmutables.

Puedo construir gráficos acíclicos dirigidos con este enfoque siempre que haga un tipo topológico y construya cada gráfico "desde las hojas hacia arriba".

Sin embargo, este enfoque no funciona para gráficos cíclicos. La única solución que puedo pensar es tener una colección separada (probablemente un mapa o vector) de todos los bordes de un gráfico completo. El campo :edges en cada nodo tendría la clave (o índice) en la colección de bordes del gráfico. Agregar este nivel adicional de direccionamiento indirecto funciona porque puedo crear claves (o índices) antes de que las cosas a las que se refieren (existan) existan, pero se siente como un obstáculo. No solo necesito hacer una búsqueda extra cada vez que quiero visitar un nodo vecino, sino que también tengo que pasar por la colección de bordes global, que se siente muy torpe.

He oído que algunos Lisps tienen una forma de crear listas cíclicas sin recurrir a funciones de mutación. ¿Hay alguna manera de crear estructuras de datos cíclicos inmutables en Clojure?

Me encontré con este desafío antes y concluí que no es posible usar estructuras de datos realmente inmutables en Clojure en este momento.

Sin embargo, puede encontrar aceptable una o más de las siguientes opciones:

Use deftype con ": uns-synchronized-mutable" para crear un campo mutable: bordes en cada nodo que cambie solo una vez durante la construcción. Puede tratarlo como de solo lectura a partir de ese momento, sin sobrecarga indirecta adicional. Este enfoque probablemente tendrá el mejor rendimiento, pero es un poco complicado.
Usa un átomo para implementar: bordes. Hay un poco de indirección adicional, pero personalmente he encontrado que leer átomos es extremadamente eficiente.

Puede envolver cada nodo en una referencia para darle un asa estable a la que apuntar (y le permite modificar la referencia que puede comenzar como cero). Entonces es posible construir gráficos cíclicos de esa manera. Esto tiene indirección "extra" por supuesto.

Aunque no creo que esta sea una muy buena idea. Su segunda idea es una implementación más común. Creamos algo como esto para tener un gráfico RDF y es posible construirlo desde las estructuras de datos centrales y los índices de capas sobre la parte superior sin demasiado esfuerzo.

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 entre sí 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 print-method multimétodo para que la réplica no se desbordase. 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.

Se ve así, más o menos, para 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, vaya (keys (graph node-1)) o llame a la función definida en otro lugar (neighbors graph node-1) , o puede decir ((graph node-1) node-2) para obtener el borde de 1->2 .

Varias ventajas:

Búsqueda de tiempo constante de un nodo en el gráfico y de un nodo vecino, o retorno nulo 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 del gráfico en sí no codificado en los nodos y bordes, búsqueda de tiempo constante y nodos y bordes no mutantes), y la lista de adyacencia (cada nodo "tiene "una lista de sus nodos vecinos, espacio eficiente ya que no tiene ningún" espacios 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 otro lugar o ref. La estructura de su nodo puede ser nula y, siempre que sea única, se puede representar en el gráfico.

La única desventaja grande 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 de clave-valor en el mapa, no se puede definir un hyperedge (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.