title: Prolog ways to compare variables
body: <p>I was trying to implement some graph algorithms in Prolog. I came up with an idea to use unification to build a tree from the graph structure:</p>
  
  <p>The graph would be defined as follows:</p>
  
  <ul>
  <li><p>A list of <code>Vertex-Variable</code> pairs where <code>Vertex</code> is a constant representing the vertex and <code>Variable</code> is a corresponding variable, that would be used as a "reference" to the vertex. e.g.:</p>
  
  <p><code>[a-A, b-B, c-C, d-D]</code></p></li>
  <li><p>A list of <code>VertexVar-NeighboursList</code> pairs, where the <code>VertexVar</code> and the individual neighbours in the <code>NeighboursList</code> are the "reference variables". e.g.:</p>
  
  <p><code>[A-[B, C, D], B-[A, C], C-[A, B], D-[A]]</code> meaning <code>b</code>, <code>c</code>, <code>d</code> are neighbours of <code>a</code> etc.</p></li>
  </ul>
  
  <p>Then before some graph algorithm (like searching for components, or simple DFS/BFS etc.) that could use some kind of tree built from the original graph, one could use some predicate like <code>unify_neighbours</code> that unifies the <code>VertexVar-NeighbourList</code> pairs as <code>VertexVar = NeighboursList</code>. After that, the vertex variables may be interpreted as lists of its neighbours, where each neighbour is again a list of its neighbours.</p>
  
  <p>So this would result in a good performance when traversing the graph, as there is no need in linear search for some vertex and its neighbours for every vertex in the graph.</p>
  
  <p>But my problem is: How to compare those vertex variables? (To check if they're the same.) I tried to use <code>A == B</code>, but there are some conflicts. For the example above, (with the <code>unify_neighbours</code> predicate) Prolog interprets the graph internally as:</p>
  
  <pre><code>[a-[S_1, S_2, S_3], b-S_1, c-S_2, d-S_3]
  </code></pre>
  
  <p>where:</p>
  
  <pre><code>S_1 = [[S_1, S_2, S_3], S_2]
  S_2 = [[S_1, S_2, S_3], S_1]
  S_3 = [[S_1, S_2, S_3]]
  </code></pre>
  
  <p>The problem is with <code>S_1</code> and <code>S_2</code> (aka <code>b</code> and <code>c</code>) as <code>X = [something, Y], Y = [something, X], X == Y</code> is <code>true</code>. The same problem would be with vertices, that share the same neighbours. e.g. <code>U-[A, B]</code> and <code>V-[A, B]</code>.</p>
  
  <p>So my question is: Is there any other way to compare variables, that could help me with this? Something that compares "the variables themselves", not the content, like comparing addresses in procedural programming languages? Or would that be too procedural and break the declarative idea of Prolog?</p>
  
  <h2>Example</h2>
  
  <pre><code>graph_component(Vertices, Neighbours, C) :-
      % Vertices and Neighbours as explained above.
      % C is some component found in the graph.
      vertices_refs(Vertices, Refs),
      % Refs are only the variables from the pairs.
      unify_neighbours(Neighbours), % As explained above.
      rec_(Vertices, Refs, [], C).
  
  rec_(Vertices, Refs, Found, RFound) :-
      % Vertices as before.
      % Refs is a stack of the vertex variables to search.
      % Found are the vertices found so far.
      % RFound is the resulting component found.
      [Ref|RRest] = Refs,
      vertices_pair(Vertices, Vertex-Ref),
      % Vertex is the corresponding Vertex for the Ref variable
      not(member(Vertex, Found)),
      % Go deep:
      rec_(Vertices, Ref, [Vertex|Found], DFound),
      list_revpush_result([Vertex|Found], DFound, Found1),
      % Go wide:
      rec_(Vertices, RRest, Found1, RFound).
  
  rec_(Vertices, Refs, Found, []) :-
      % End of reccursion.
      [Ref|_] = Refs,
      vertices_pair(Vertices, Vertex-Ref),
      member(Vertex, Found).
  </code></pre>
  
  <p>This example doesn't really work, but it's the idea. (Also, checking whether the vertices were found is done linearly, so the performance is still not good, but it's just for demonstration.) Now the predicate, that finds the corresponding vertex for the variable is implemented as:</p>
  
  <pre><code>vertices_pair([Vertex-Ref|_], Vertex-Ref).
  vertices_pair([_-OtherRef|Rest], Vertex-Ref) :-
      Ref \== OtherRef,
      vertices_pair(Rest, Vertex-Ref).
  </code></pre>
  
  <p>where the <code>\==</code> operator is not really what I want and it creates those conflicts.</p>