Re: A simple (?) graph algorithm

From: Hans Aberg (haberg.not.this_at_matematik.su.se)
Date: 04/24/04

  • Next message: Pento: "Re: SWI prolog and the Nth-Queens problem." 
    Date: Sat, 24 Apr 2004 19:22:21 +0200

    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

  • Next message: Pento: "Re: SWI prolog and the Nth-Queens problem."

    Relevant Pages

    • Re: A simple (?) graph algorithm
      ... > I have a directed graph described as a set of edges: ... > What I need is a predicate like allconnectedthat would give ... De wereld was soep, en het denken meestal een vork, ...
      (comp.lang.prolog)
    • Re: A simple (?) graph algorithm
      ... pimko wrote: ... > I have a directed graph described as a set of edges: ... > I've created a predicate connectedwhich is true when there is a ... Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen ...
      (comp.lang.prolog)
    • Re: A simple (?) graph algorithm
      ... > I have a directed graph described as a set of edges: ... Is this graph known to be free from cycles? ... your predicate connected/2 is another ...
      (comp.lang.prolog)