// -*- C++ -*- /* *template > * *Constructor: * *Prim(Graph G, LengthMap weight) * * *Methods: * *void run() : Runs the Prim-algorithm from a random node * *void run(Node r) : Runs the Prim-algorithm from node s * *T weight() : After run(r) was run, it returns the minimum * weight of a spanning tree of the component of the root. * *Edge tree(Node v) : After run(r) was run, it returns the * first edge in the path from v to the root. Returns * INVALID if v=r or v is not reachable from the root. * *bool conn() : After run(r) was run, it is true iff G is connected * *bool reached(Node v) : After run(r) was run, it is true * iff v is in the same component as the root * *Node root() : returns the root * */ #ifndef HUGO_PRIM_H #define HUGO_PRIM_H #include #include namespace hugo { template >, typename LengthMap=typename Graph::EdgeMap > class Prim{ typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt OutEdgeIt; typedef typename Graph::InEdgeIt InEdgeIt; const Graph& G; const LengthMap& edge_weight; typename Graph::NodeMap tree_edge; typename Graph::NodeMap min_weight; typename Graph::NodeMap reach; public : Prim(Graph& _G, LengthMap& _edge_weight) : G(_G), edge_weight(_edge_weight), tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { } void run() { NodeIt _r; G.first(_r); run(_r); } void run(Node r) { NodeIt u; for ( G.first(u) ; G.valid(u) ; G.next(u) ) { tree_edge.set(u,INVALID); min_weight.set(u,0); reach.set(u,false); } typename Graph::NodeMap scanned(G, false); typename Graph::NodeMap heap_map(G,-1); Heap heap(heap_map); heap.push(r,0); reach.set(r, true); while ( !heap.empty() ) { Node v=heap.top(); min_weight.set(v, heap.get(v)); heap.pop(); scanned.set(v,true); OutEdgeIt e; for( G.first(e,v); G.valid(e); G.next(e)) { Node w=G.head(e); if ( !scanned[w] ) { if ( !reach[w] ) { reach.set(w,true); heap.push(w, edge_weight[e]); tree_edge.set(w,e); } else if ( edge_weight[e] < heap.get(w) ) { tree_edge.set(w,e); heap.decrease(w, edge_weight[e]); } } } InEdgeIt f; for( G.first(f,v); G.valid(f); G.next(f)) { Node w=G.tail(f); if ( !scanned[w] ) { if ( !reach[w] ) { reach.set(w,true); heap.push(w, edge_weight[f]); tree_edge.set(w,f); } else if ( edge_weight[f] < heap.get(w) ) { tree_edge.set(w,f); heap.decrease(w, edge_weight[f]); } } } } } T weight() { T w=0; NodeIt u; for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u]; return w; } Edge tree(Node v) { return tree_edge[v]; } bool conn() { bool c=true; NodeIt u; for ( G.first(u) ; G.valid(u) ; G.next(u) ) if ( !reached[u] ) { c=false; break; } return c; } bool reached(Node v) { return reached[v]; } Node root() { return r; } }; } #endif