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
: to this please help.  I think I have a mental block on this.

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,
        Cycle = [Out|Link],
        direct_link(FromPosn,ToPosn,Domain,Out),
        NewCycleLength is CycleLength - 1,
        link(NewCycleLength,ToPosn,FromPosn,Domain,Link),
        all_distinct(Cycle),
        label(Cycle).

link(1,FromPosn,ToPosn,Domain,[Link]) :- !,
        direct_link(FromPosn,ToPosn,Domain,Link).
link(CycleLength,FromPosn,ToPosn,Domain,[Link|LinkTail]) :-
        direct_link(FromPosn,MidPosn,Domain,Link),
        NewCycleLength is CycleLength - 1,
        link(NewCycleLength,MidPosn,ToPosn,Domain,LinkTail).

direct_link(FromPosn,ToPosn,Domain,Link) :-
        Link in Domain,
        encode(FromPosn,ToPosn,Link).

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

PS BUY IF/Prolog!

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

 Relevant Pages 

1. Clarion Close statement loops forever.

2. Close several while loops

3. Problems with a closed loop

4. memory leak with Visa Close in loop

5. Exit tk application on Close Window (Exit on infinite loop)

6. Record Not Found when Form closes

7. how can i find area under a closed curve

8. Finding Out if Socket Has Been Closed

9. tcl finds close braces when they are in commented lines

10. Antigen found JS.Loop (CA(Vet)) virus

11. Stopping loops, finding shortest paths

12. using loop macro to find argmax

 

 
Powered by phpBB® Forum Software