Bug fixes.
3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
7 *Prim(Graph G, LengthMap weight)
12 *void run() : Runs the Prim-algorithm from a random node
14 *void run(Node r) : Runs the Prim-algorithm from node s
16 *T weight() : After run(r) was run, it returns the minimum
17 * weight of a spanning tree of the component of the root.
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.
23 *bool conn() : After run(r) was run, it is true iff G is connected
25 *bool reached(Node v) : After run(r) was run, it is true
26 * iff v is in the same component as the root
28 *Node root() : returns the root
40 template <typename Graph, typename T,
41 typename Heap=FibHeap<typename Graph::Node, T,
42 typename Graph::NodeMap<int> >,
43 typename LengthMap=typename Graph::EdgeMap<T> >
45 typedef typename Graph::Node Node;
46 typedef typename Graph::NodeIt NodeIt;
47 typedef typename Graph::Edge Edge;
48 typedef typename Graph::OutEdgeIt OutEdgeIt;
49 typedef typename Graph::InEdgeIt InEdgeIt;
52 const LengthMap& edge_weight;
53 typename Graph::NodeMap<Edge> tree_edge;
54 typename Graph::NodeMap<T> min_weight;
55 typename Graph::NodeMap<bool> reach;
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) { }
74 for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
75 tree_edge.set(u,INVALID);
81 typename Graph::NodeMap<bool> scanned(G, false);
82 typename Graph::NodeMap<int> heap_map(G,-1);
89 while ( !heap.empty() ) {
92 min_weight.set(v, heap.get(v));
97 for( G.first(e,v); G.valid(e); G.next(e)) {
103 heap.push(w, edge_weight[e]);
105 } else if ( edge_weight[e] < heap.get(w) ) {
107 heap.decrease(w, edge_weight[e]);
113 for( G.first(f,v); G.valid(f); G.next(f)) {
119 heap.push(w, edge_weight[f]);
121 } else if ( edge_weight[f] < heap.get(w) ) {
123 heap.decrease(w, edge_weight[f]);
134 for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
147 for ( G.first(u) ; G.valid(u) ; G.next(u) )
156 bool reached(Node v) {