Cómo representar el gráfico cíclico dirigido en Prolog con acceso directo a las verticías vecinas

cyclic-graph

Question

Necesito construir un gráfico dirigido (en tiempo de ejecución) con ciclos en Prolog y no estoy seguro de cómo representarlo. Mi requisito es que necesito llegar de un vértice a su vecindario en un tiempo constante.

¿Es posible representarlo como un árbol, por ejemplo:

t(left_son,V,right_son)

pero, ¿cómo resolver los ciclos?

Puedo hacer una lista de bordes:

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

O solo

[a->[b],b->[c],c->[a,d],d->[]] pero ¿cómo evitar llamar a la función ''miembro'' en la lista mientras busca vecinos, que cuestan tiempo lineal? Gracias por tu ayuda

Answer 1

Además de la representación que @chac sugiere, también puede considerar el uso de variables atribuidas (si su sistema Prolog lo admite), especialmente si necesita adjuntar más atributos a vértices o bordes durante sus cálculos. En esta representación, usaría una variable única para cada vértice, adjuntará (con put_attr / 3) un atributo como "nombre" si es necesario, y adjuntará un atributo adicional como "bordes" que puede ser, por ejemplo, una lista de vértices , o una lista de términos edge (E, Vertex), donde E es nuevamente una variable a la que puede adjuntar más atributos si necesita realizar un seguimiento de la información que afecta a los bordes.

Answer 2

Hay library(ugraphs) en muchos sistemas Prolog como YAP , SWI , SICStus , Ciao . (¡Por favor, siéntase libre de agregar más referencias aquí!) Allí, los gráficos se representan como una lista de pares Vertex-Neighbours . A primera vista, puede tener la impresión de que esta no es una representación muy eficiente. Después de todo, el acceso a un solo vértice es proporcional a la longitud de la lista. Sin embargo, el acceso directo a un vértice rara vez es de interés. La mayoría de las veces, un gráfico se procesará de una sola vez, lo que a menudo amortiza los costos de acceso.

Answer 3

Si su gráfico tiene menos vértices que el máximo permitido por su Prolog (por ejemplo, SWI-Prolog tiene arity ilimitado), puede representar los bordes como índices de argumentos:

podría ser

G = graph(a-[2],b-[3],c-[1,4],d-[2]).

luego use arg (Edge, G, Vert-Edges) para acceder a los vecinos.

Por supuesto, cualquier Prolog te permitirá describir el gráfico usando hechos. Esta es también la forma preferida para gráficos muy grandes.

:- dynamic edge/2.

edge(a,b).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).

editar La representación relacional edge / 2 también obtiene los beneficios (potencialmente grandes) de la indexación automática.

más editar Olvidé por completo RDF y Web Semántica . Realmente poderoso, vamos hacia eso.