A simple (?) graph algorithm

Hi
I have a directed graph described as a set of edges:
edge(v1,v2).
edge(v2,v3).
edge(v2,v4).
edge(v4,v5).
(for example)
I've created a predicate connected(X,Y) which is true when there is a
path from X to Y:
connected(X,Y):-edge(X,Y).
connected(X,Y):-edge(X,Z),connected(Z,Y).

What I need is a predicate like allconnected(X,List) that would give
me a list of all vertices that are connected to X:
allconnected(v3,List). would give List=[v1,v2];
allconnected(v5,List). would give List=[v1,v2,v4].

How can I use the "connected" predicate to make "allconnected"
predicate? Or maybe there is a simpler way of doing this?
Please help

Best regards
Pimko

pimko <profesorpimko@wp.pl> wrote:
> Hi
> I have a directed graph described as a set of edges:
> edge(v1,v2).
> edge(v2,v3).
> edge(v2,v4).
> edge(v4,v5).
> (for example)
> I've created a predicate connected(X,Y) which is true when there is a
> path from X to Y:
> connected(X,Y):-edge(X,Y).
> connected(X,Y):-edge(X,Z),connected(Z,Y).

> What I need is a predicate like allconnected(X,List) that would give
> me a list of all vertices that are connected to X:
> allconnected(v3,List). would give List=[v1,v2];
> allconnected(v5,List). would give List=[v1,v2,v4].

> How can I use the "connected" predicate to make "allconnected"
> predicate? Or maybe there is a simpler way of doing this?
> Please help

look in your manual or Prolog book for findall, bagof or setof

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

profesorpimko@wp.pl (pimko) wrote in
news:659e1cbf.0404182341.1d1eabd3@posting.google.c om:

> Hi
> I have a directed graph described as a set of edges:
> edge(v1,v2).
> edge(v2,v3).
> edge(v2,v4).
> edge(v4,v5).
> (for example)
> I've created a predicate connected(X,Y) which is true when there is a
> path from X to Y:
> connected(X,Y):-edge(X,Y).
> connected(X,Y):-edge(X,Z),connected(Z,Y).
>
> What I need is a predicate like allconnected(X,List) that would give
> me a list of all vertices that are connected to X:
> allconnected(v3,List). would give List=[v1,v2];
> allconnected(v5,List). would give List=[v1,v2,v4].

You could use findall/3 for that. Check your manual for more information.

--
Pento

De wereld was soep, en het denken meestal een vork,
tot smakelijk eten leidde dat zelden. - H. Mulisch

pimko wrote:

> Hi
> I have a directed graph described as a set of edges:
> edge(v1,v2).
> edge(v2,v3).
> edge(v2,v4).
> edge(v4,v5).

Is this graph known to be free from cycles? I.e. is
no node connected to itself (directly or indirectly)?

Can there be more than one path from some X to some Y?

> (for example)
> I've created a predicate connected(X,Y) which is true when there is a
> path from X to Y:
> connected(X,Y):-edge(X,Y).
> connected(X,Y):-edge(X,Z),connected(Z,Y).

In some ways, your predicate connected/2 is another
directed graph, but depending on your answers to the
previous questions, in some ways maybe it ain't.

> What I need is a predicate like allconnected(X,List) that would give
> me a list of all vertices that are connected to X:
> allconnected(v3,List). would give List=[v1,v2];
> allconnected(v5,List). would give List=[v1,v2,v4].
>
> How can I use the "connected" predicate to make "allconnected"
> predicate? Or maybe there is a simpler way of doing this?
> Please help

Others have pointed you to setof, bagof and findall.
It's worthwhile (maybe necessary) to understand how
they differ.

Paul Singleton

Hi again
Thank you very much for your help.

However I forgot to write a few things.
The graph has no cycles but there can be more than one (even a few)
path from one node to another, the path can be direct (only one) or
indirect (many).
I have used setof-it gives the proper list, without duplicates but
there is one very important thing I forgot to write: the list must be
in a proper sequence. If I take an algorithm and for every step I
assign a node then I have such a graph. Some tasks must be completed
to do another one and in the list they must come before any task that
requires them.
For example for a graph like:
e(v1,v2).
e(v2,v3).
e(v2,v4).
e(v1,v3).
e(v3,v5).
e(v2,v4).
e(v4,v5).
allconnected(v2,List). returns List=[v1]
allconnected(v3,List). returns List=[v1,v2]
allconnected(v4,List). returns List=[v1,v2]
allconnected(v5,List). returns List=[v1,v2,v3,v4]

if I add e(v4,v3) then allconnected(v5,List). returns
List=[v1,v2,v4,v3]
I hope it's now well described.
Is it known how findall, bagof or setof are implemented? Maybe I could
use something from that.
Maybe usage of "connected" predicate is not a good idea?

Best regards
Pimko

In article <659e1cbf.0404182341.1d1eabd3@posting.google.com >,
profesorpimko@wp.pl (pimko) wrote:

>I have a directed graph ...
....
>What I need is a predicate like allconnected(X,List) that would give
>me a list of all vertices that are connected to X:

You need to be careful in defining exactly what "connected to" means in a
directed graph:

One answer is given by Tarjan's strongly connected components (SCC) algorithm:
http://www1.ics.uci.edu/~eppstein/161/960220.html#sca
Adapted to computing FIRST:
http://compilers.iecc.com/comparch/article/01-04-079
In this definition, vertex x connected to vertex y means that there is a
path from x to and one from y to x. This then defines an equivalence
relation, and its equivalence classes are called the SCC's of the directed
graph.

Hans Aberg

Hi

My "connected(X,Y)" means that there is a path from X to Y and there
is not a path from Y to X (there are no cycles).
But I'm not sure if the predicate is really required, perhaps there is
another way (maybe easier) for doing it.
However I still haven't found a solution. The returned List may be
with duplicates but in a good sequence and that is my main problem.

if(anyone_has_an_idea)
{
please help... ;-)
}

Best regards
pimko

pimko escreveu:
>
> if(anyone_has_an_idea)
> {
> please help... ;-)
> }

In a more prolog syntax:

please_help :- anyone_has_an_idea. % ;-D

profesorpimko@wp.pl (pimko) wrote in message news:<659e1cbf.0404280556.5e731d2a@posting.google. com>...

>
> if(anyone_has_an_idea)
> {
> please help... ;-)
> }
>
> Best regards
> pimko

Hi,

could you show us your code with setof.
I have similar problem so maybe we'll solve it together.

best regard

ajam

Hi
Sorry it's so late but I've been very busy recently. It goes like this:

connected(X,Y):-e(X,Y).
connected(X,Y):-e(X,Z),connected(Z,Y).

allconnected(X,[X]):- \+ connected(_,X).
allconnected(X,List):- setof(Y,connected(Y,X),List1),append(List1,[X],List).

Hope it's right

Best regards
pimko