COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/prim.h @ 438:a0a2709cf178

Last change on this file since 438:a0a2709cf178 was 211:9222a9b8b323, checked in by jacint, 18 years ago

updating

File size: 3.3 KB
RevLine 
[173]1// -*- C++ -*-
2/*
[211]3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
[173]4 *
5 *Constructor:
6 *
[211]7 *Prim(Graph G, LengthMap weight)
[173]8 *
9 *
10 *Methods:
11 *
[211]12 *void run() : Runs the Prim-algorithm from a random node
[173]13 *
[211]14 *void run(Node r) : Runs the Prim-algorithm from node s
[173]15 *
[211]16 *T weight() : After run(r) was run, it returns the minimum
17 *   weight of a spanning tree of the component of the root.
[173]18 *
[211]19 *Edge tree(Node v) : After run(r) was run, it returns the
20 *   first edge in the path from v to the root. Returns
21 *   INVALID if v=r or v is not reachable from the root.
[173]22 *
[211]23 *bool conn() : After run(r) was run, it is true iff G is connected
[173]24 *
[211]25 *bool reached(Node v) : After run(r) was run, it is true
26 *   iff v is in the same component as the root
[173]27 *
[211]28 *Node root() : returns the root
[173]29 *
30 */
31
[211]32#ifndef HUGO_PRIM_H
33#define HUGO_PRIM_H
[173]34
35#include <fib_heap.h>
[211]36#include <invalid.h>
[173]37
38namespace hugo {
39
40  template <typename Graph, typename T,
[211]41    typename Heap=FibHeap<typename Graph::Node, T,
42    typename Graph::NodeMap<int> >,
43    typename LengthMap=typename Graph::EdgeMap<T> >
[173]44    class Prim{
[211]45      typedef typename Graph::Node Node;
[173]46      typedef typename Graph::NodeIt NodeIt;
[211]47      typedef typename Graph::Edge Edge;
[173]48      typedef typename Graph::OutEdgeIt OutEdgeIt;
49      typedef typename Graph::InEdgeIt InEdgeIt; 
50
[211]51      const Graph& G;
52      const LengthMap& edge_weight;
53      typename Graph::NodeMap<Edge> tree_edge;
[173]54      typename Graph::NodeMap<T> min_weight;
[211]55      typename Graph::NodeMap<bool> reach;
[173]56         
57  public :
58
[211]59      Prim(Graph& _G, LengthMap& _edge_weight) :
60        G(_G), edge_weight(_edge_weight),
61        tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
[173]62
[211]63
64      void run() {
65        NodeIt _r;     
66        G.first(_r);
67        run(_r);
[173]68      }
69
70
[211]71      void run(Node r) {
72
73        NodeIt u;
74        for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
75          tree_edge.set(u,INVALID);
76          min_weight.set(u,0);
77          reach.set(u,false);
78        }
79
[173]80
81        typename Graph::NodeMap<bool> scanned(G, false);
82        typename Graph::NodeMap<int> heap_map(G,-1);
83       
84        Heap heap(heap_map);
85
86        heap.push(r,0);
[211]87        reach.set(r, true);
[173]88
89        while ( !heap.empty() ) {
90
[211]91          Node v=heap.top();
[173]92          min_weight.set(v, heap.get(v));
93          heap.pop();
94          scanned.set(v,true);
95
96          OutEdgeIt e;
[211]97          for( G.first(e,v); G.valid(e); G.next(e)) {
98            Node w=G.head(e);
[173]99           
[211]100            if ( !scanned[w] ) {
101              if ( !reach[w] ) {
102                reach.set(w,true);
103                heap.push(w, edge_weight[e]);
[173]104                tree_edge.set(w,e);
[211]105              } else if ( edge_weight[e] < heap.get(w) ) {
[173]106                tree_edge.set(w,e);
[211]107                heap.decrease(w, edge_weight[e]);
[173]108              }
109            }
110          }
111
112          InEdgeIt f;
[211]113          for( G.first(f,v); G.valid(f); G.next(f)) {
114            Node w=G.tail(f);
[173]115           
[211]116            if ( !scanned[w] ) {
117              if ( !reach[w] ) {
118                reach.set(w,true);
119                heap.push(w, edge_weight[f]);
[173]120                tree_edge.set(w,f);
[211]121              } else if ( edge_weight[f] < heap.get(w) ) {
[173]122                tree_edge.set(w,f);
[211]123                heap.decrease(w, edge_weight[f]);
[173]124              }
125            }
126          }
127        }
128      }
129 
130
131      T weight() {
132        T w=0;
[211]133        NodeIt u;
134        for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
[173]135        return w;
136      }
137     
138
[211]139      Edge tree(Node v) {
140        return tree_edge[v];
[173]141      }
142
143
144      bool conn() {
145        bool c=true;
[211]146        NodeIt u;
147        for ( G.first(u) ; G.valid(u) ; G.next(u) )
148          if ( !reached[u] ) {
[173]149            c=false;
150            break;
151          }
152        return c;
153      }
154
155
[211]156      bool reached(Node v) {
157        return reached[v];
[173]158      }
159
160
[211]161      Node root() {
[173]162        return r;
163      }
164
165    };
166
167}
168
169#endif
170
171
Note: See TracBrowser for help on using the repository browser.