Hierarchical undirected graph representation

Question

I need to represent the graph like this:

Graph = graph([Object1,Object2,Object3,Object4],
              [arc(Object1,Object2,connected),
               arc(Object2,Object4,connected),
               arc(Object3,Object4,connected),
               arc(Object1,Object3,connected),
               arc(Object2,Object3,parallel),
               arc(Object1,Object4,parallel),
               arc(Object2,Object3,similar_size),
               arc(Object1,Object4,similar_size)])

I have no restriction for code, however I'd stick to this representation as it fits all the other structures I've already coded.

What I mean is the undirected graph in which vertices are some objects and edges representing undirected relations between them. To give you more background in this particular example I'm trying to represent a rectangle, so objects are its four edges(segments). Those segments are represented in the same way with use of vertices and so on. The point is to build the hierarchy of graphs which would represent constraints between objects on the same level.

The problem lays in the representation of edges. The most obvious way to represent an arc (a,b) would be to put both (a,b) and (b,a) in the program. This however floods my program with redundant data exponentialy. For example if I have vertices a,b,c,d. I can build segments (a,b),(a,c),(a,d),(b,c),(b,d),(c,d). But I get also (b,a),(c,a), and so on. At this points its not a problem. But later I build a rectangle. It can be build of segments (a,b),(b,c),(c,d),(a,d). And I'd like to get the answer - there's one rectangle. You can calculate however how many combination of this one rectangle I get. It also take too much time to calculate and obviously I don't want to finish at the rectangle level.

I thought about sorting the elements. I can sort vertices in a segment. But if I want to sort segments in a rectangle the constraints are no longer valid. The graph becomes directed. For example taking into consideration the first two relations let's say we have arcs (a,b) and (a,c). If arcs are not sorted the program answers as I want it to: arc(b,a,connected),arc(a,c,connected) with match: Object1=b,Object2=a,Object4=c. If I sort elements it's no longer valid as I cannot have arc(b,a,connected) and arc(a,b,connected) tried out. Only the second one. I'd stick with the sorting but I have no idea how to solve this last issue.

Hopefully I stated all of this quite clearly. I'd prefer to stay as close to the representation and ideas I already have. But completely new ones are also very welcome. I don't expect any exact answer, rather poitning me in the right direction or suggesting something specific to read as I'm quite new to Prolog and maybe this problem is not as uncommon as I think.

I'm trying to solve this since yesterday and couldn't come up with any easy answer. I looked at some discrete math and common undirected graphs representation like adjacency list. Let me know if anything is unclear - I'll try to provide more details.

Answer 1

Interesting question although a bit broad since it is not stated what you actually want to do with the arcs, rectangles etc; a representation may be efficient (time/space/elegance) only with certain uses. In any case, here are some ideas:

Sorting
the obvious issue is the one you mentioned; you can solve it by introducing a clause that succeeds if the sorted pair exists:

arc(X,Y):-
    arc_data(X,Y)
  ; arc_data(Y,X).

note that you should not do something like:

arc(a,b).
arc(b,c).
arc(X,Y):-
   arc(Y,X)

since this will result in a infinite loop if the arc does not exist. you could however only check if the first arg is larger than the second:

arc(a,b).
arc(b,c).
arc(X,Y):-
   compare(>,X,Y),
   arc(Y,X)

This approach will not resolve the multiple solutions that may arise due to having an arc represented in two ways. The easy fix would be to only check for one solution where only one solution is expected using once/1:

3 ?- arc(X,Y).
X = a,
Y = b ;
X = b,
Y = a.

4 ?- once(arc(X,Y)).
X = a,
Y = b.

Of course you cannot do this when there could be multiple solutions.

Another approach would be to enforce further abstraction: at the moment, when you have two points (a, b) you can create the arc (arc(a,b) or arc(b,a)) after checking if those points are connected. Instead of that, you should create the arc through a predicate (that could also check if the points are connected). The benefit is that you no longer get involved in the representation of the arc directly and can thus enforce sorting (yes, it's basically object orientation):

cv_arc(X,Y,Arc):-
      ( arc(X,Y),
        Arc = arc(X,Y))
    ; ( arc(Y,X),
        Arc = arc(Y,X)).

(assuming as a database arc(a,b)):

    6 ?- cv_arc(a,b,A).
    A = arc(a, b).

    7 ?- cv_arc(b,a,A).
    A = arc(a, b).

    8 ?- cv_arc(b,c,A).
    false.

Of course you would need to follow a similar principle for the rest of the objects; I assume that you are doing something like this to find a rectangle:

rectangle(A,B,C,D):-
    arc(A,B),
    arc(B,C),
    arc(C,D),
    arc(D,A).

besides the duplicates due to the arc (which are resolved) this would recognise ABCD, DABC etc as different rectangles:

28 ?- rectangle(A,B,C,D).
A = a,
B = b,
C = c,
D = d ;
A = b,
B = c,
C = d,
D = a ;
A = c,
B = d,
C = a,
D = b ;
A = d,
B = a,
C = b,
D = c.

We will do the same again:

rectangle(rectangle(A,B,C,D)):-
    cv_arc(A,B,AB),
    cv_arc(B,C,BC),
    compare(<,AB,BC),
    cv_arc(C,D,CD),
    compare(<,BC,CD),
    cv_arc(D,A,DA),
    compare(<,CD,DA).

and running with arc(a,b). arc(b,c). arc(c,d). arc(a,d).:

27 ?- rectangle(R).
R = rectangle(a, b, c, d) ;
false.

Note that we did not re-order the rectangle if the arcs were in the wrong order; we simply failed it. This way we avoided duplicate solutions (if we ordered them and accepted it as a valid rectangle we would have the same rectangle four times) but the time spent to find the rectangle increases. We reduced the overhead by stopping the search at the first arc that is out of order instead of creating the whole rectangle. Also, the overhead would also be reduced if the arcs are ordered (since the first match would be ordered). On the other hand, if we consider the complexity of searching for all rectangles this way, the overhead is not that significant. Also, it only applies if we want just the first rectangle; should we want to get more solutions or ensure that there are no other solutions, prolog will search the whole tree, whether it reports the solutions or not.