1.1 --- a/src/work/jacint/prim.h Fri Mar 19 21:15:14 2004 +0000
1.2 +++ b/src/work/jacint/prim.h Fri Mar 19 22:16:05 2004 +0000
1.3 @@ -1,81 +1,82 @@
1.4 // -*- C++ -*-
1.5 -
1.6 -//kell hogy tree_edge invalid elekbol alljon, Szep
1.7 -//lenne ha az elejen a konstrualas ilyet adna, de
1.8 -//ugy fest nem igy lesz, ekkor invalidalni kell
1.9 -
1.10 /*
1.11 - *template <Graph, T, Heap=FibHeap>
1.12 + *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
1.13 *
1.14 *Constructor:
1.15 *
1.16 - *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
1.17 + *Prim(Graph G, LengthMap weight)
1.18 *
1.19 *
1.20 *Methods:
1.21 *
1.22 - *void run()
1.23 + *void run() : Runs the Prim-algorithm from a random node
1.24 *
1.25 - * The followings functions should be used after run() was already run.
1.26 + *void run(Node r) : Runs the Prim-algorithm from node s
1.27 *
1.28 - *T weight() : returns the minimum weight of a spanning tree of the
1.29 - * component of the root.
1.30 + *T weight() : After run(r) was run, it returns the minimum
1.31 + * weight of a spanning tree of the component of the root.
1.32 *
1.33 - *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
1.34 - * to the root. Returns an invalid iterator if v=s or v is
1.35 - * not reachable from the root.
1.36 + *Edge tree(Node v) : After run(r) was run, it returns the
1.37 + * first edge in the path from v to the root. Returns
1.38 + * INVALID if v=r or v is not reachable from the root.
1.39 *
1.40 - *bool conn() : true iff G is connected
1.41 + *bool conn() : After run(r) was run, it is true iff G is connected
1.42 *
1.43 - *bool reach(NodeIt v) : true iff v is in the same component as the root
1.44 + *bool reached(Node v) : After run(r) was run, it is true
1.45 + * iff v is in the same component as the root
1.46 *
1.47 - *NodeIt root() : returns the root
1.48 + *Node root() : returns the root
1.49 *
1.50 */
1.51
1.52 -#ifndef PRIM_H
1.53 -#define PRIM_H
1.54 +#ifndef HUGO_PRIM_H
1.55 +#define HUGO_PRIM_H
1.56
1.57 #include <fib_heap.h>
1.58 -
1.59 -#include <iostream>
1.60 +#include <invalid.h>
1.61
1.62 namespace hugo {
1.63
1.64 template <typename Graph, typename T,
1.65 - typename Heap=FibHeap<typename Graph::NodeIt, T,
1.66 - typename Graph::NodeMap<int> > >
1.67 + typename Heap=FibHeap<typename Graph::Node, T,
1.68 + typename Graph::NodeMap<int> >,
1.69 + typename LengthMap=typename Graph::EdgeMap<T> >
1.70 class Prim{
1.71 + typedef typename Graph::Node Node;
1.72 typedef typename Graph::NodeIt NodeIt;
1.73 - typedef typename Graph::EachNodeIt EachNodeIt;
1.74 - typedef typename Graph::EdgeIt EdgeIt;
1.75 + typedef typename Graph::Edge Edge;
1.76 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.77 typedef typename Graph::InEdgeIt InEdgeIt;
1.78
1.79 - Graph& G;
1.80 - NodeIt r;
1.81 - typename Graph::NodeMap<EdgeIt> tree_edge;
1.82 + const Graph& G;
1.83 + const LengthMap& edge_weight;
1.84 + typename Graph::NodeMap<Edge> tree_edge;
1.85 typename Graph::NodeMap<T> min_weight;
1.86 - typename Graph::EdgeMap<T>& edge_weight;
1.87 - typename Graph::NodeMap<bool> reached;
1.88 + typename Graph::NodeMap<bool> reach;
1.89
1.90 public :
1.91
1.92 - Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight,
1.93 - NodeIt const _r) :
1.94 - G(_G), r(_r), tree_edge(G), min_weight(G),
1.95 - edge_weight(_edge_weight), reached(G, false) { }
1.96 + Prim(Graph& _G, LengthMap& _edge_weight) :
1.97 + G(_G), edge_weight(_edge_weight),
1.98 + tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
1.99
1.100 - Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) :
1.101 - G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
1.102 - {
1.103 - EachNodeIt _r; //FIXME
1.104 - G.getFirst(_r);
1.105 - r=_r;
1.106 +
1.107 + void run() {
1.108 + NodeIt _r;
1.109 + G.first(_r);
1.110 + run(_r);
1.111 }
1.112
1.113
1.114 - void run() {
1.115 + void run(Node r) {
1.116 +
1.117 + NodeIt u;
1.118 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.119 + tree_edge.set(u,INVALID);
1.120 + min_weight.set(u,0);
1.121 + reach.set(u,false);
1.122 + }
1.123 +
1.124
1.125 typename Graph::NodeMap<bool> scanned(G, false);
1.126 typename Graph::NodeMap<int> heap_map(G,-1);
1.127 @@ -83,43 +84,43 @@
1.128 Heap heap(heap_map);
1.129
1.130 heap.push(r,0);
1.131 - reached.set(r, true);
1.132 + reach.set(r, true);
1.133
1.134 while ( !heap.empty() ) {
1.135
1.136 - NodeIt v=heap.top();
1.137 + Node v=heap.top();
1.138 min_weight.set(v, heap.get(v));
1.139 heap.pop();
1.140 scanned.set(v,true);
1.141
1.142 OutEdgeIt e;
1.143 - for( G.getFirst(e,v); G.valid(e); G.next(e)) {
1.144 - NodeIt w=G.head(e);
1.145 + for( G.first(e,v); G.valid(e); G.next(e)) {
1.146 + Node w=G.head(e);
1.147
1.148 - if ( !scanned.get(w) ) {
1.149 - if ( !reached.get(w) ) {
1.150 - reached.set(w,true);
1.151 - heap.push(w, edge_weight.get(e));
1.152 + if ( !scanned[w] ) {
1.153 + if ( !reach[w] ) {
1.154 + reach.set(w,true);
1.155 + heap.push(w, edge_weight[e]);
1.156 tree_edge.set(w,e);
1.157 - } else if ( edge_weight.get(e) < heap.get(w) ) {
1.158 + } else if ( edge_weight[e] < heap.get(w) ) {
1.159 tree_edge.set(w,e);
1.160 - heap.decrease(w, edge_weight.get(e));
1.161 + heap.decrease(w, edge_weight[e]);
1.162 }
1.163 }
1.164 }
1.165
1.166 InEdgeIt f;
1.167 - for( G.getFirst(f,v); G.valid(f); G.next(f)) {
1.168 - NodeIt w=G.tail(f);
1.169 + for( G.first(f,v); G.valid(f); G.next(f)) {
1.170 + Node w=G.tail(f);
1.171
1.172 - if ( !scanned.get(w) ) {
1.173 - if ( !reached.get(w) ) {
1.174 - reached.set(w,true);
1.175 - heap.push(w, edge_weight.get(f));
1.176 + if ( !scanned[w] ) {
1.177 + if ( !reach[w] ) {
1.178 + reach.set(w,true);
1.179 + heap.push(w, edge_weight[f]);
1.180 tree_edge.set(w,f);
1.181 - } else if ( edge_weight.get(f) < heap.get(w) ) {
1.182 + } else if ( edge_weight[f] < heap.get(w) ) {
1.183 tree_edge.set(w,f);
1.184 - heap.decrease(w, edge_weight.get(f));
1.185 + heap.decrease(w, edge_weight[f]);
1.186 }
1.187 }
1.188 }
1.189 @@ -129,22 +130,22 @@
1.190
1.191 T weight() {
1.192 T w=0;
1.193 - EachNodeIt u;
1.194 - for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
1.195 + NodeIt u;
1.196 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
1.197 return w;
1.198 }
1.199
1.200
1.201 - EdgeIt tree(NodeIt v) {
1.202 - return tree_edge.get(v);
1.203 + Edge tree(Node v) {
1.204 + return tree_edge[v];
1.205 }
1.206
1.207
1.208 bool conn() {
1.209 bool c=true;
1.210 - EachNodeIt u;
1.211 - for ( G.getFirst(u) ; G.valid(u) ; G.next(u) )
1.212 - if ( !reached.get(u) ) {
1.213 + NodeIt u;
1.214 + for ( G.first(u) ; G.valid(u) ; G.next(u) )
1.215 + if ( !reached[u] ) {
1.216 c=false;
1.217 break;
1.218 }
1.219 @@ -152,12 +153,12 @@
1.220 }
1.221
1.222
1.223 - bool reach(NodeIt v) {
1.224 - return reached.get(v);
1.225 + bool reached(Node v) {
1.226 + return reached[v];
1.227 }
1.228
1.229
1.230 - NodeIt root() {
1.231 + Node root() {
1.232 return r;
1.233 }
1.234