# generating maximal structures

From: Cornelius Hagen <cornelius.hagen_at_wiai.uni-bamberg.de>
Date: Thu 22 May 2003 04:12:02 PM GMT
Message-ID: <002001c3207c\$e190c2a0\$89020d8d@CHAGEN>
```Hello,

I have a problem like the following example:
There are given facts representing lines. My objective is to find all
polygons that are maximal such that there are no further lines that
could be added to the polygon. I treat a polygon as a list of lines,
more precisely their ids.
The following is a simplified version of the problem which consists of
finding a polygon of a maximal number of lines starting with a given
line.

Some facts
The first argument identifies a line, the others represent its (for
simplicity one-dimensional)  border points. Obviously, the maximal
polygon is [1,2,3,4] or [4,3,2,1].

line(1, 0,1).
line(2, 1,2).
line(3, 2,3).
line(4, 3,4).

This is a relation for testing. Its argument represents the id of the
given line the polygon shall start with.
pol( X ) :-
L = [X],
(polygon( X, L );
write( L )).

My flawed approach to produce a polygon
polygon( A, P ) :-
line( A, _, YA ), line( B, XB, _ ),
not( member( B, P ) ),
A =\= B,
YA =:= XB,
Pol = [B|P],
write( Pol ),
polygon( B, Pol).

The problem:
The relation produces the desired list, as the output of write(Pol)
shows.  But the polygon-predicate finally failes and therefore does not
return the list of interest: The write(L) term in the pol-predicate
produces instead of the disired [4,3,2,1] just the list .

Is there another approach that works?

Best wishes

Cornelius

```
Received on Thu May 22 17:48:31 2003

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:24 PM GMT GMT