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 [1]. 
 
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