Re: Persistant graphs

From: Jan Wielemaker (jan_at_ct.xs4all.nl)
Date: 10/06/04

  • Next message: Martin Kant: "means-ends planner with priorities/costs" 
    Date: 06 Oct 2004 07:41:22 GMT

    In article <416338FE.316893AE@pacXbell.net>, Bill Spight wrote:
    > projectshave@yahoo.com wrote:
    >>
    >> I'd like to do some graph rewriting in Prolog, which will involve lots
    >> of addition/deletion of nodes and edges. If a rewrite "fails", it must
    >> backtrack to the original graph and attempt a different rewrite. A
    >> persistant, or functional, graph would work best in this case. Is
    >> there a library for persistant graphs available for Prolog somewhere?
    >> I'm hoping to avoid the assert/retract global space.
    >>
    >
    > Make the graphs terms and carry along the different versions of the
    > graph being rewritten as arguments. Do not use assert and retract. That
    > may take a lot of memory, but memory is cheap these days.
    >
    > For instance, you might represent the graph as a list of nodes
    > (vertices) along with their immediate successors. Like so:
    >
    > Graph = [Node - Successors | Nodes]
    >
    > Then you might have a predicate
    >
    > rewrite(Graph0, Graph) :- ....

    Using lists isn't ideal as the author wants to do lots of manipulations
    and each manipulation will make a copy of the list. This doesn't only
    cost memory, but also a lot of time. In addition you generally want
    the successors of a successor (etc). Each step takes linear time.

    It makes more sense to use (balanced) binary trees. Access or order
    log(N) and modification only modifies log(N) nodes. Many Prologs
    have library(assoc), implementing this.

    Of course you still have to do all the work yourself. There must be
    libraries out there doing some of it for you ...

            Cheers --- Jan

  • Next message: Martin Kant: "means-ends planner with priorities/costs"

    Relevant Pages

    • Re: Persistant graphs
      ... > I'd like to do some graph rewriting in Prolog, ... > backtrack to the original graph and attempt a different rewrite. ... may take a lot of memory, but memory is cheap these days. ...
      (comp.lang.prolog)
    • Re: Shortest path between two vertices in a graph
      ... implementation of basic algorithms in graphs. ... Three lines of Prolog solve this  really easy, ... same graph ... Prolog formulation, can be used to solve such ...
      (comp.lang.prolog)
    • Re: Topological Sort Help
      ... there are no vertexes with successors and that is the ... algorithm, thanks for all the, now i juts need to set up a looping ... consider how the graph is ...
      (comp.lang.ada)
    • Shortest path between two vertices in a graph
      ... But I tried not to have the list, only the edges definitions, and try ... Three lines of Prolog solve this really easy, ... same graph ... write('Maybe now it is an endless loop '), nl, ...
      (comp.lang.prolog)
    • Re: Floyd warshall
      ... Since this questions is suspiciously similar to someone asking for a homework: ... Do you know enough Prolog so you can represent the graph in Prolog terms? ...
      (comp.lang.prolog)