1.1 --- a/src/work/jacint/prim.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,171 +0,0 @@
1.4 -// -*- C++ -*-
1.5 -/*
1.6 - *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
1.7 - *
1.8 - *Constructor:
1.9 - *
1.10 - *Prim(Graph G, LengthMap weight)
1.11 - *
1.12 - *
1.13 - *Methods:
1.14 - *
1.15 - *void run() : Runs the Prim-algorithm from a random node
1.16 - *
1.17 - *void run(Node r) : Runs the Prim-algorithm from node s
1.18 - *
1.19 - *T weight() : After run(r) was run, it returns the minimum
1.20 - * weight of a spanning tree of the component of the root.
1.21 - *
1.22 - *Edge tree(Node v) : After run(r) was run, it returns the
1.23 - * first edge in the path from v to the root. Returns
1.24 - * INVALID if v=r or v is not reachable from the root.
1.25 - *
1.26 - *bool conn() : After run(r) was run, it is true iff G is connected
1.27 - *
1.28 - *bool reached(Node v) : After run(r) was run, it is true
1.29 - * iff v is in the same component as the root
1.30 - *
1.31 - *Node root() : returns the root
1.32 - *
1.33 - */
1.34 -
1.35 -#ifndef LEMON_PRIM_H
1.36 -#define LEMON_PRIM_H
1.37 -
1.38 -#include <fib_heap.h>
1.39 -#include <invalid.h>
1.40 -
1.41 -namespace lemon {
1.42 -
1.43 - template <typename Graph, typename T,
1.44 - typename Heap=FibHeap<typename Graph::Node, T,
1.45 - typename Graph::NodeMap<int> >,
1.46 - typename LengthMap=typename Graph::EdgeMap<T> >
1.47 - class Prim{
1.48 - typedef typename Graph::Node Node;
1.49 - typedef typename Graph::NodeIt NodeIt;
1.50 - typedef typename Graph::Edge Edge;
1.51 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.52 - typedef typename Graph::InEdgeIt InEdgeIt;
1.53 -
1.54 - const Graph& G;
1.55 - const LengthMap& edge_weight;
1.56 - typename Graph::NodeMap<Edge> tree_edge;
1.57 - typename Graph::NodeMap<T> min_weight;
1.58 - typename Graph::NodeMap<bool> reach;
1.59 -
1.60 - public :
1.61 -
1.62 - Prim(Graph& _G, LengthMap& _edge_weight) :
1.63 - G(_G), edge_weight(_edge_weight),
1.64 - tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
1.65 -
1.66 -
1.67 - void run() {
1.68 - NodeIt _r;
1.69 - G.first(_r);
1.70 - run(_r);
1.71 - }
1.72 -
1.73 -
1.74 - void run(Node r) {
1.75 -
1.76 - NodeIt u;
1.77 - for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.78 - tree_edge.set(u,INVALID);
1.79 - min_weight.set(u,0);
1.80 - reach.set(u,false);
1.81 - }
1.82 -
1.83 -
1.84 - typename Graph::NodeMap<bool> scanned(G, false);
1.85 - typename Graph::NodeMap<int> heap_map(G,-1);
1.86 -
1.87 - Heap heap(heap_map);
1.88 -
1.89 - heap.push(r,0);
1.90 - reach.set(r, true);
1.91 -
1.92 - while ( !heap.empty() ) {
1.93 -
1.94 - Node v=heap.top();
1.95 - min_weight.set(v, heap.get(v));
1.96 - heap.pop();
1.97 - scanned.set(v,true);
1.98 -
1.99 - OutEdgeIt e;
1.100 - for( G.first(e,v); G.valid(e); G.next(e)) {
1.101 - Node w=G.target(e);
1.102 -
1.103 - if ( !scanned[w] ) {
1.104 - if ( !reach[w] ) {
1.105 - reach.set(w,true);
1.106 - heap.push(w, edge_weight[e]);
1.107 - tree_edge.set(w,e);
1.108 - } else if ( edge_weight[e] < heap.get(w) ) {
1.109 - tree_edge.set(w,e);
1.110 - heap.decrease(w, edge_weight[e]);
1.111 - }
1.112 - }
1.113 - }
1.114 -
1.115 - InEdgeIt f;
1.116 - for( G.first(f,v); G.valid(f); G.next(f)) {
1.117 - Node w=G.source(f);
1.118 -
1.119 - if ( !scanned[w] ) {
1.120 - if ( !reach[w] ) {
1.121 - reach.set(w,true);
1.122 - heap.push(w, edge_weight[f]);
1.123 - tree_edge.set(w,f);
1.124 - } else if ( edge_weight[f] < heap.get(w) ) {
1.125 - tree_edge.set(w,f);
1.126 - heap.decrease(w, edge_weight[f]);
1.127 - }
1.128 - }
1.129 - }
1.130 - }
1.131 - }
1.132 -
1.133 -
1.134 - T weight() {
1.135 - T w=0;
1.136 - NodeIt u;
1.137 - for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
1.138 - return w;
1.139 - }
1.140 -
1.141 -
1.142 - Edge tree(Node v) {
1.143 - return tree_edge[v];
1.144 - }
1.145 -
1.146 -
1.147 - bool conn() {
1.148 - bool c=true;
1.149 - NodeIt u;
1.150 - for ( G.first(u) ; G.valid(u) ; G.next(u) )
1.151 - if ( !reached[u] ) {
1.152 - c=false;
1.153 - break;
1.154 - }
1.155 - return c;
1.156 - }
1.157 -
1.158 -
1.159 - bool reached(Node v) {
1.160 - return reached[v];
1.161 - }
1.162 -
1.163 -
1.164 - Node root() {
1.165 - return r;
1.166 - }
1.167 -
1.168 - };
1.169 -
1.170 -}
1.171 -
1.172 -#endif
1.173 -
1.174 -