Re: CLP(FD) Prolog: help needed with a simple problem

From: Bart Demoen (bmd_at_cs.kuleuven.ac.be)
Date: 03/29/05 

Date: Tue, 29 Mar 2005 12:42:54 +0200

Chema wrote:

> I got the point, but the problem is: I've to impose this kind of
> condition for each subgraph. Consider an undirected graph G=(V,E)
> with E = (a,b), (b,c), (c,d), (d,h), (e,h), (a,e), (b,e), (b,h),
> (c,h), (e,f), (f,h), (h,g), (d,g), (f,g)
> You see, I should include at least two constrains for each cycle.
> This is an NP hard problem, and this constrains grow in an
> esponential way... I can't do that "manually".

Let's first get things straight: you are trying to solve the problem
"given a graph, find a spanning tree"
That problem is not NP hard. The algorithms of Kruskal and Prim give
you a minimal spanning tree in a weighted graph in polynomial
time. You can use these algorithms with weight 1 for each edge. Those
algorithms avoid cycles, but not by trying to represent each of
them explicitly.

You want to solve CLP for solving that problem - fine. Don't set up
constraints for cycles. There is some simple piece of graph theory that
says: for a connected graph with n nodes, the spanning tree contains
(n-1) edges and of course also the n nodes.
So the following will work: give a distinct variable name to every edge,
say Ei, and keep track for each node Vi on which edges it lies;
now generate the constraints

        all Ei in [0,1]
        the sum of all Ei equals n-1
        for every Vi there is some Ej (which Vi lies on) which is 1

That's the generalisation of what I wrote for the very simple example.
The structure of your program could be something like:

        st(Edges) :-
                all_edges(Edges),
                all_nodes_on_edges(Edges,NodesOnEdges),
                length(NodesOnEdges,N),
                Edges in 0..1,
                sum(Edges,N-1),
                foreach(Node-ItsEdges,member(Node-ItsEdges,NodesOnEdges),(sum(ItsEdges,M),M>0)),
                label(Edges).

Code not tested. You still need to keep track of the association between
the edge variables and the actual edges (I ignored that completely above).

Cheers

Bart Demoen

Relevant Pages

  • Re: How come Ada isnt more popular?
    ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
    (comp.lang.ada)
  • Elecsol batteries (again)
    ... Look at the graph at the bottom. ... D.O.D. means Depth of Discharge. ... cycles for various D.O.D.s between 50% and 100%. ... sense in that the deeper the discharge, the less life cycles each ...
    (uk.rec.waterways)
  • Re: Graph to regions algorithm
    ... > My problem is that I need an algorithm witch will construct all regions ... The graph is convex and convex. ... To find cycles in a graph, you compute the "minimum spanning tree". ...
    (comp.graphics.algorithms)
  • Re: Finding simple cycles approximating target distance
    ... >best solve the following problem relating graph theory. ... I expect result cycles will consist of about 10 ... Assuming the weights are all positive and you want the total weight ... in the interval, you can do a depth-first search using the ...
    (sci.math)