Finding Closed Loops in Prolog
Author Message
Finding Closed Loops in Prolog

: Hi,
: I have the following problem

: e.g.,
:                      G                    H
:                       A  ------------------------------------------- D

:               |       |                     |            |
:               |       |---------------------|            |
:               |    E                       F          |
:               |                                         |
:               |                                         |
:               |                                         |
:                      B   ------------------------------------------- C

: I want to be able to detect closed loops.  Using a depth first search
: I am able to detect all the loops but I want to be able to filter all
: the super loops.

: e.g.,
: I want to detect the following
: ABCDHFEGA
: GEFHG
: but want to exclude the superloops
: i.e., ABCD.

: I only want to detect the deepest of loops.  If anyone has the logic

Hi,
This sort of problem can be tackled very efficiently in a
constraint logic programming language like IF/Prolog. I recently
tacked a similar problem for a reason I wont go into. Basically
by encoding a link from A-B as an integer C = A * 1000 + B and
then making a domain from the list of all links. It is then possible
to write a simple recurrsive algorithm that will find all cycles in
the domain - and it is very very fast.
Here is some code.

cycle(Domain,CycleLength,Cycle) :-
CycleLength > 2,
NewCycleLength is CycleLength - 1,
all_distinct(Cycle),
label(Cycle).

NewCycleLength is CycleLength - 1,

encode(From, To, Value) :-
Value ?= To * 1000 + From.

CycleLength is the initial max-length of the cycle, for efficiency reasons
in the other application is was not worth considering cycles more than 10
in length - we also had some 5000 links in a net. By setting cycle length
as the length of the domain it will find all possible cycles.
A

Domain is [1003, 3004, 4003, 5003 ....]

I don't know of a neater way to tackle this problem.

Andrew

Prolog Hotline Support,

marketing: Annette Kolb
technical: Dr. Andrew Verden

tel. : +49 89 7936 0037                            IF Computer GmbH
fax. : +49 89 7936 0039                            Ludwig Thoma Weg 11a

Tue, 14 Apr 1998 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages