← Back to branch summary

~ubuntu-branches/ubuntu/natty/gecode/natty

« back to all changes in this revision

Viewing changes to contribs/graph/path/pathgraphs.icc

  • Committer: Bazaar Package Importer
  • Author(s): Kari Pahula
  • Date: 2005-12-24 07:51:25 UTC
  • Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
contribs/graph/path/pathgraphs.icc
 
1
 
 
2
/*
 
3
 *  Main authors:
 
4
 *     Gr�goire Dooms <dooms@info.ucl.ac.be>
 
5
 *
 
6
 *  Copyright:
 
7
 *     Gr�goire Dooms (Universit� catholique de Louvain), 2005
 
8
 *
 
9
 *  Last modified:
 
10
 *     $Date: 2005-11-29 10:57:21 +0100 (Tue, 29 Nov 2005) $
 
11
 *     $Revision: 271 $
 
12
 *
 
13
 *  This file is part of CP(Graph)
 
14
 *
 
15
 *  See the file "contribs/graph/LICENSE" for information on usage and
 
16
 *  redistribution of this file, and for a
 
17
 *     DISCLAIMER OF ALL WARRANTIES.
 
18
 *
 
19
 */
 
20
 
 
21
#include "graph.hh"
 
22
#include <list>
 
23
#include <vector>
 
24
#include <utility>
 
25
#include <boost/utility.hpp>
 
26
#include <boost/graph/strong_components.hpp>
 
27
#include <boost/graph/graphviz.hpp>
 
28
#include <boost/graph/graph_utility.hpp>
 
29
#include <boost/graph/topological_sort.hpp>
 
30
#include <boost/graph/depth_first_search.hpp>
 
31
#include <boost/graph/visitors.hpp>
 
32
#include <boost/property_map.hpp>
 
33
#include <boost/graph/reverse_graph.hpp>
 
34
#include <boost/graph/dijkstra_shortest_paths.hpp>
 
35
#include <boost/graph/iteration_macros.hpp>
 
36
#include <boost/tuple/tuple.hpp>
 
37
//using namespace boost;
 
38
//using namespace std;
 
39
 
 
40
namespace Gecode { namespace Graph {
 
41
 
 
42
/** \brief  BoundsGraphs datastructure for the path propagator 
 
43
 *
 
44
 * \relates PathPropag PathCostPropag*/
 
45
template <class GDV>
 
46
class PathBoundsGraphs : public BoundsGraphs<GDV> {
 
47
//TODO : Still missing the lower bound propagation
 
48
        using BoundsGraphs<GDV>::UB;
 
49
        using BoundsGraphs<GDV>::LB;
 
50
        using BoundsGraphs<GDV>::UB_v;
 
51
        using BoundsGraphs<GDV>::LB_v;
 
52
        using BoundsGraphs<GDV>::numNodes;
 
53
        using BoundsGraphs<GDV>::arcOut;
 
54
        using BoundsGraphs<GDV>::nodeOut;
 
55
      public:
 
56
        using BoundsGraphs<GDV>::resetVertexIndexUB;
 
57
        using BoundsGraphs<GDV>::resetEdgeIndexUB;
 
58
        PathBoundsGraphs(GDV &g);
 
59
        ExecStatus SCC_filtering(Space* home, int start, int end);
 
60
        boost::tuple<ExecStatus,int,int> cost_filtering(Space* home, int sourceID, int targetID, const map <pair<int,int>,int> &edgecosts ,int uppercost);
 
61
};
 
62
 
 
63
        /// Builds a PathBoundsGraphs from the current domain of a Graph View of type GDV
 
64
        template <class GDV>
 
65
        PathBoundsGraphs<GDV>::PathBoundsGraphs(GDV &g): BoundsGraphs<GDV>(g){}
 
66
 
 
67
/** \brief  Topological propagation for the path constraint
 
68
 * 
 
69
 *  Enforces the graph to be a simply connected component: 
 
70
 *  all nodes must be reachable from the source
 
71
 *
 
72
 *  Checks the nodes in LB are all in same CC of UB.
 
73
 *  Removes the other components of UB.
 
74
 *
 
75
 *  Checks the nodes in UB are part of a single SCC if a back edge is added 
 
76
 *  --> intersection of nodes reachable from source and nodes that can be reached from end
 
77
 *  
 
78
 *  Check no two LB nodes are in parallel branches of the condensed graph (== DAG)
 
79
 */
 
80
template <class GDV>
 
81
ExecStatus PathBoundsGraphs<GDV>::SCC_filtering(Space* home, int sourceID, int targetID){
 
82
        
 
83
 
 
84
        // std::map<Gecode::Graph::Graph::vertex_descriptor, default_color_type> color;
 
85
        Gecode::Graph::Graph::vertex_descriptor s = UB_v[sourceID];
 
86
        boost::dfs_visitor<boost::null_visitor> t;
 
87
        // YYY replace this map with a vector and use iterator_property_map with Node::index
 
88
        typedef std::map<Gecode::Graph::Graph::vertex_descriptor,boost::default_color_type> CMT;
 
89
        CMT v2c;
 
90
        boost::associative_property_map<CMT> cmap(v2c);
 
91
        Gecode::Graph::Graph::vertex_iterator vi,vi_end, next;
 
92
        boost::tie(vi,vi_end) = vertices(UB);
 
93
        for (;vi!=vi_end; ++vi){
 
94
                cmap[*vi]=boost::white_color;
 
95
        }
 
96
        boost::depth_first_visit(UB,s,t, cmap);
 
97
        boost::tie(vi,vi_end) = vertices(UB);
 
98
        TRACE(cout << "depth_first_done "<< num_vertices(UB) << " nodes in UB" << endl);
 
99
        int cnodes = 0;
 
100
        for (next = vi; vi != vi_end; vi = next) {
 
101
                ++next;
 
102
                ++cnodes;
 
103
                TRACE(cout << get(cmap,*vi) );
 
104
                if (get(cmap,*vi) == boost::white_color){
 
105
                        TRACE(cout <<"UB node "<< UB[*vi].id << " is still white"<<endl);
 
106
                        if (LB_v[UB[*vi].id]){
 
107
                                TRACE(cout << "It is also in LB"<<endl);
 
108
                        }
 
109
                        GECODE_ME_CHECK(nodeOut(home,UB[*vi].id));
 
110
 
 
111
                }
 
112
        }
 
113
        TRACE(cout << cnodes << "nodes processed, single_cc done proceeding with cambazard"<<endl);
 
114
        // cambazard :  
 
115
        // Step 1 add a back edge and prune everything out the SCC then remove back edge.
 
116
        // Step 2 Compute condensed graph CG. CG is a DAG. On CG, if a node is parallel to a 
 
117
        // kernel node remove it.
 
118
 
 
119
        // Step 1 
 
120
        Gecode::Graph::Graph::edge_descriptor e_tmp;
 
121
        bool b;
 
122
        boost::tie(e_tmp,b) = add_edge(UB_v[targetID], UB_v[sourceID], UB);
 
123
 
 
124
        // YYY replace this map with a vector and use iterator_property_map with Node::index
 
125
        typedef std::map<Gecode::Graph::Graph::vertex_descriptor,Gecode::Graph::Graph::vertices_size_type> CN;
 
126
        CN v2comp;
 
127
        boost::associative_property_map<CN> compmap(v2comp);
 
128
 
 
129
        resetVertexIndexUB();
 
130
        boost::strong_components(UB,compmap,vertex_index_map(get(&Node::index, UB)));
 
131
        Gecode::Graph::Graph::vertices_size_type good_comp = compmap[UB_v[sourceID]];
 
132
        boost::tie(vi,vi_end) = vertices(UB);
 
133
        for (next = vi; vi != vi_end; vi = next) {
 
134
                ++next;
 
135
                if (compmap[*vi] != good_comp){
 
136
                        TRACE(cout << "node "<< UB[*vi].id  << " is in comp "<< compmap[*vi] << " instead of comp " << good_comp << endl);
 
137
                        GECODE_ME_CHECK(nodeOut(home,UB[*vi].id));
 
138
                }
 
139
        }
 
140
        remove_edge(e_tmp,UB); 
 
141
        resetVertexIndexUB();
 
142
        v2comp.clear();
 
143
        int numcomp = boost::strong_components(UB,compmap,vertex_index_map(get(&Node::index, UB)));
 
144
 
 
145
        TRACE(cout << "numcomp = " << numcomp << endl);
 
146
        //Build the reduced graph using the info in compmap
 
147
        typedef boost::adjacency_list<boost::vecS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, std::size_t>, boost::no_property> RGraph;
 
148
        TRACE(cout << "indexes: ");
 
149
        RGraph RG(numcomp);
 
150
        vector<RGraph::vertex_descriptor> comp2Rv(numcomp);
 
151
        RGraph::vertex_iterator rvi,rvi_end;
 
152
        boost::tie(rvi,rvi_end) = vertices(RG);
 
153
        // rnode descr-> rnode id
 
154
        boost::property_map<RGraph, boost::vertex_index_t>::type rd2id = get(boost::vertex_index, RG);
 
155
        int i = 0;
 
156
        for (;rvi!=rvi_end; ++rvi, ++i){
 
157
                comp2Rv[i]=*rvi;
 
158
                rd2id[*rvi]=i;
 
159
                TRACE(cout << i << " ");
 
160
        }
 
161
        assert(rvi==rvi_end && i==numcomp);
 
162
        boost::tie(vi,vi_end) = vertices(UB);
 
163
        std::vector< std::list<int> > compnodes(numcomp); // rnode_id->list of component node UB id
 
164
        for (;vi!=vi_end; ++vi){
 
165
                compnodes[compmap[*vi]].push_back(UB[*vi].id); 
 
166
        }
 
167
 
 
168
 
 
169
        TRACE(cout << endl);
 
170
        //edges
 
171
        Gecode::Graph::Graph::edge_iterator ei,ei_end;
 
172
        boost::tie(ei,ei_end) = edges(UB);
 
173
        for (;ei!=ei_end; ++ei){
 
174
                if (compmap[source(*ei,UB)] != compmap[target(*ei,UB)]){
 
175
                        TRACE(cout << "add_Edge "<<compmap[source(*ei,UB)]<<" "<< compmap[target(*ei,UB)] << endl);
 
176
                        add_edge(comp2Rv[compmap[source(*ei,UB)]], 
 
177
                                        comp2Rv[compmap[target(*ei,UB)]], RG);
 
178
                }
 
179
        }
 
180
 
 
181
        //RG is built, now do a topological sort on it and remove the vertices
 
182
        typedef std::vector< RGraph::vertex_descriptor > TO_C;
 
183
        TO_C toporder; // vector with topol sorted rnode desc.
 
184
        toporder.reserve(numcomp);
 
185
        TRACE(cout << "reduced_graph top. order:" << endl);
 
186
        //TRACE(write_graphviz(cout,RG));
 
187
 
 
188
        boost::topological_sort(RG, std::back_inserter(toporder));
 
189
 
 
190
        std::vector<int> UBn_order(numNodes);// for each UBid  -> index in topol
 
191
        //compute the topological order of the nodes in UB
 
192
        //store the indice in the UBn_order vector
 
193
        TO_C::iterator rd_i=toporder.begin();
 
194
        for (int j=0; rd_i!=toporder.end(); ++rd_i, ++j){
 
195
                TRACE(cout << *rd_i << " -> ");
 
196
                TRACE(cout << rd2id[*rd_i] << "\n");
 
197
                for (list<int>::iterator n=compnodes[rd2id[*rd_i]].begin();
 
198
                                n!=compnodes[rd2id[*rd_i]].end(); ++n){
 
199
                        UBn_order[*n]=j;
 
200
                }
 
201
        }
 
202
        TRACE(cout << endl);
 
203
 
 
204
 
 
205
 
 
206
        int last_kernel_node_index=0, next_knid=0;
 
207
        //for all nodes in rgraph starting from the sink up to the source
 
208
        for (rd_i=toporder.begin(); rd_i!=toporder.end(); ++rd_i){ 
 
209
                // for all real UB node associated to the rnode
 
210
                bool chng_knid = false;
 
211
                for (list<int>::iterator UBid_i = compnodes[rd2id[*rd_i]].begin();
 
212
                                UBid_i!=compnodes[rd2id[*rd_i]].end(); ++UBid_i  ){
 
213
                        // list of edges to be removed (removing an edge invalidates all edge iterators)
 
214
                        std::list<std::pair<int,int> > remove;
 
215
 
 
216
                        Gecode::Graph::Graph::adjacency_iterator av,av_end,next;
 
217
                        boost::tie(av,av_end) = adjacent_vertices(UB_v[*UBid_i],UB);
 
218
 
 
219
                        // for all out neighbor of this node in UB.
 
220
                        for (next=av; av != av_end ; av=next){
 
221
                                ++next;
 
222
                                //If an edge jumps over the last encountered kern node, remove the edge.
 
223
                                if(UBn_order[UB[*av].id] < last_kernel_node_index){
 
224
                                        TRACE(cout<<"arc "<<*UBid_i<<" "<<UB[*av].id<<" jumps over last kern node"<<endl);
 
225
                                        remove.push_back(make_pair(*UBid_i,UB[*av].id));
 
226
                                }
 
227
                        }
 
228
                        for (list<pair<int,int> >::iterator r=remove.begin(); r!=remove.end(); ++r){
 
229
                                TRACE(cout << "removing edge " << r->first << " "<<r->second <<endl);
 
230
                                GECODE_ME_CHECK(arcOut(home,r->first,r->second));
 
231
                        }
 
232
 
 
233
                        // if the real node is a kernel node then update last_kernel_node_index.
 
234
                        if (LB_v[*UBid_i]){
 
235
                                TRACE(cout <<*UBid_i<< " is kernel of order "<<UBn_order[*UBid_i] << endl);
 
236
                                chng_knid = true;
 
237
                                next_knid = UBn_order[*UBid_i];
 
238
                        }
 
239
 
 
240
                }
 
241
                if (chng_knid) {
 
242
                        last_kernel_node_index = next_knid;
 
243
                }
 
244
        }
 
245
 
 
246
        TRACE(cout << endl);
 
247
        return ES_OK;
 
248
}
 
249
//#include <dijkstra_shortest_paths_old.hpp> // found a bug in boost.graph 1.33 this is 1.32 version/bugfree
 
250
 
 
251
 
 
252
/** \brief  Removes arcs from the upper bound according to cost information 
 
253
 * This is based on what is done in M. Sellmann thesis but here with a naive non-incremental way
 
254
 * returns a tuple with execstatus and 2 new bounds for the weight.
 
255
 * PRE: the weights are non-negative
 
256
 */
 
257
template <class GDV>
 
258
boost::tuple<ExecStatus,int,int> PathBoundsGraphs<GDV>::cost_filtering(Space* home, int sourceID, int targetID, const map <pair<int,int>,int> &edgecosts ,int uppercost){
 
259
 
 
260
        // perform a SSSP in forward direction from sourceID s
 
261
        // and a SSSP in reverse direction from targetID t
 
262
        // store the distances F(x) = D(s,x,G) and R(y) = D(t,y,G^-1)  in two maps or vectors
 
263
        // for each edge (i,j), check that it is possible by
 
264
        // F(i) + Cij + R(j) <= uppercost 
 
265
 
 
266
        TRACE(cout << this << endl);
 
267
        std::vector<int> e2w(num_edges(UB));
 
268
        BGL_FORALL_EDGES(e, UB, Gecode::Graph::Graph) {
 
269
                e2w[UB[e].index] =  edgecosts.find(make_pair(UB[source(e,UB)].id, UB[target(e,UB)].id ))->second ; // not using edgecosts[make_pair...] because operator[] inserts keys if missing
 
270
        }
 
271
 
 
272
        std::vector<int> dist(num_vertices(UB)) ;
 
273
        Gecode::Graph::Graph::vertex_descriptor s = UB_v[sourceID];
 
274
        // see http://www.boost.org/libs/graph/doc/bundles.html weight_map(get(&Highway::miles, map)) for distance_map and weight map
 
275
        dijkstra_shortest_paths(UB, s, distance_map(make_iterator_property_map(&dist[0], get(&Node::index, UB))).vertex_index_map(get(&Node::index, UB)).weight_map(make_iterator_property_map(&e2w[0], get(&Edge::index, UB))));//.distance_compare(std::less<int>()));
 
276
        std::vector<int> rdist(num_vertices(UB)) ;
 
277
        boost::reverse_graph<Gecode::Graph::Graph> R(UB);
 
278
        Gecode::Graph::Graph::vertex_descriptor t = UB_v[targetID];
 
279
        boost::dijkstra_shortest_paths(R, t, boost::distance_map(boost::make_iterator_property_map(&rdist[0], get(&Node::index, UB))).vertex_index_map(get(&Node::index, UB)).weight_map(make_iterator_property_map(&e2w[0], get(&Edge::index, UB))).distance_compare(std::less<int>()));
 
280
 
 
281
        vector<Gecode::Graph::Graph::edge_descriptor> removed; //temp for debug
 
282
        vector<Gecode::Graph::Graph::vertex_descriptor> removednodes; //temp for debug
 
283
        BGL_FORALL_VERTICES(v, UB, Gecode::Graph::Graph) {
 
284
                if (dist[UB[v].index] + rdist[UB[v].index] > uppercost ) {
 
285
                        removednodes.push_back(v);
 
286
                }
 
287
        }
 
288
        BGL_FORALL_EDGES(e, UB, Gecode::Graph::Graph) {
 
289
                if (dist[UB[source(e,UB)].index] + rdist[UB[target(e,UB)].index] + e2w[UB[e].index] > uppercost ) {
 
290
                        removed.push_back(e);
 
291
                }
 
292
        }
 
293
 
 
294
 
 
295
        TRACE(cout << "upper bound of cost : " << uppercost<<endl);
 
296
        TRACE(cout << "######################################################" << endl);
 
297
        TRACE(cout << "digraph { " << endl);
 
298
        BGL_FORALL_VERTICES(v, UB, Gecode::Graph::Graph) {
 
299
                TRACE(cout << UB[v].id << "[label='" << dist[UB[v].index] << "," << rdist[UB[v].index] << "']"<<endl );
 
300
        }
 
301
        BGL_FORALL_EDGES(e, UB, Gecode::Graph::Graph) {
 
302
                TRACE(cout << UB[source(e,UB)].id << "->" << UB[target(e,UB)].id << "[label='"<<e2w[UB[e].index]<< "'");
 
303
                if (find(removed.begin(), removed.end(), e) != removed.end()){
 
304
                        TRACE(cout << " color=red]");
 
305
                }
 
306
                else {
 
307
                        TRACE(cout << "]");
 
308
                }
 
309
                TRACE(cout << endl);
 
310
        }
 
311
        TRACE(cout << "}" << endl);
 
312
        TRACE(cout << "######################################################" << endl);
 
313
 
 
314
#define GECODE_ME_CHECK_3TUPLE(me) if (::Gecode::me_failed(me))\
 
315
        return ::boost::make_tuple(::Gecode::ES_FAILED,0,0);
 
316
 
 
317
        for (vector<Gecode::Graph::Graph::edge_descriptor>::iterator i = removed.begin(); i<removed.end(); ++i)
 
318
                GECODE_ME_CHECK_3TUPLE(arcOut(home,UB[source(*i,UB)].id, UB[target(*i,UB)].id));
 
319
        for (vector<Gecode::Graph::Graph::vertex_descriptor>::iterator i = removednodes.begin(); i<removednodes.end(); ++i)
 
320
                GECODE_ME_CHECK_3TUPLE(nodeOut(home,UB[*i].id));
 
321
 
 
322
        // PRE: all costs are positive 
 
323
        // TODO implement weight for the graph
 
324
 
 
325
        resetEdgeIndexUB();
 
326
        int weightUB = 0;
 
327
        BGL_FORALL_EDGES(e, UB, Gecode::Graph::Graph) {
 
328
                // not using edgecosts[make_pair...] because operator[] inserts keys if missing
 
329
                weightUB += edgecosts.find(make_pair(UB[source(e,UB)].id, UB[target(e,UB)].id ))->second ; 
 
330
        }
 
331
        int weightLB = 0;
 
332
        BGL_FORALL_EDGES(e, LB, Gecode::Graph::Graph) {
 
333
                weightLB += edgecosts.find(make_pair(LB[source(e,LB)].id, LB[target(e,LB)].id ))->second ;
 
334
        }
 
335
 
 
336
        return boost::make_tuple(ES_OK,weightLB,weightUB);
 
337
}
 
338
 
 
339
} }
 
340
 
 
341