Changeset 211:9222a9b8b323 in lemon-0.x for src/work/jacint/prim.h

Timestamp:

03/19/04 23:16:05 (19 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@306

Message:

updating

File:

• src/work/jacint/prim.h (modified) (7 diffs)

src/work/jacint/prim.h

@@ -1 +1 @@
 // -*- C++ -*-
-
-//kell hogy tree_edge invalid elekbol alljon, Szep 
-//lenne ha az elejen a konstrualas ilyet adna, de
-//ugy fest nem igy lesz, ekkor invalidalni kell
-
 /* 
- *template <Graph, T, Heap=FibHeap>
+ *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
  *
  *Constructor: 
  *
- *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
+ *Prim(Graph G, LengthMap weight)
  *
  *
  *Methods:
  *
- *void run()
+ *void run() : Runs the Prim-algorithm from a random node
  *
- *  The followings functions should be used after run() was already run.
+ *void run(Node r) : Runs the Prim-algorithm from node s
  *
- *T weight() : returns the minimum weight of a spanning tree of the
- *   component of the root. 
+ *T weight() : After run(r) was run, it returns the minimum 
+ *   weight of a spanning tree of the component of the root. 
  *
- *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
- *   to the root. Returns an invalid iterator if v=s or v is 
- *   not reachable from 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() : true iff G is connected
+ *bool conn() : After run(r) was run, it is true iff G is connected
  *
- *bool reach(NodeIt v) : true iff v is in the same component as the root
+ *bool reached(Node v) : After run(r) was run, it is true 
+ *   iff v is in the same component as the root
  *
- *NodeIt root() : returns the root
+ *Node root() : returns the root
  *
  */
 
-#ifndef PRIM_H
-#define PRIM_H
+#ifndef HUGO_PRIM_H
+#define HUGO_PRIM_H
 
 #include <fib_heap.h>
-
-#include <iostream>
+#include <invalid.h>
 
 namespace hugo {
 
   template <typename Graph, typename T, 
-    typename Heap=FibHeap<typename Graph::NodeIt, T, 
-    typename Graph::NodeMap<int> > >
+    typename Heap=FibHeap<typename Graph::Node, T, 
+    typename Graph::NodeMap<int> >, 
+    typename LengthMap=typename Graph::EdgeMap<T> >
     class Prim{
+      typedef typename Graph::Node Node;
       typedef typename Graph::NodeIt NodeIt;
-      typedef typename Graph::EachNodeIt EachNodeIt;
-      typedef typename Graph::EdgeIt EdgeIt;
+      typedef typename Graph::Edge Edge;
       typedef typename Graph::OutEdgeIt OutEdgeIt;
       typedef typename Graph::InEdgeIt InEdgeIt;  
 
-      Graph& G;
-      NodeIt r;
-      typename Graph::NodeMap<EdgeIt> tree_edge;
+      const Graph& G;
+      const LengthMap& edge_weight;
+      typename Graph::NodeMap<Edge> tree_edge;
       typename Graph::NodeMap<T> min_weight;
-      typename Graph::EdgeMap<T>& edge_weight;
-      typename Graph::NodeMap<bool> reached;
+      typename Graph::NodeMap<bool> reach;
           
   public :
 
-      Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, 
-           NodeIt const _r) : 
-      G(_G), r(_r), tree_edge(G), min_weight(G), 
-      edge_weight(_edge_weight), reached(G, false) { }
+      Prim(Graph& _G, LengthMap& _edge_weight) : 
+        G(_G), edge_weight(_edge_weight), 
+        tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
 
-      Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : 
-      G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
-      { 
-        EachNodeIt _r;     //FIXME
-        G.getFirst(_r);
-        r=_r;
+
+      void run() {
+        NodeIt _r;      
+        G.first(_r);
+        run(_r);
       }
 
 
-      void run() {
+      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<bool> scanned(G, false);
@@ -84 +85 @@
 
         heap.push(r,0); 
-        reached.set(r, true);
+        reach.set(r, true);
 
         while ( !heap.empty() ) {
 
-          NodeIt v=heap.top(); 
+          Node v=heap.top(); 
           min_weight.set(v, heap.get(v));
           heap.pop();
@@ -94 +95 @@
 
           OutEdgeIt e;
-          for( G.getFirst(e,v); G.valid(e); G.next(e)) {
-            NodeIt w=G.head(e); 
+          for( G.first(e,v); G.valid(e); G.next(e)) {
+            Node w=G.head(e); 
             
-            if ( !scanned.get(w) ) {
-              if ( !reached.get(w) ) {
-                reached.set(w,true);
-                heap.push(w, edge_weight.get(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.get(e) < heap.get(w) ) {
+              } else if ( edge_weight[e] < heap.get(w) ) {
                 tree_edge.set(w,e);
-                heap.decrease(w, edge_weight.get(e)); 
+                heap.decrease(w, edge_weight[e]); 
               }
             }
@@ -110 +111 @@
 
           InEdgeIt f;
-          for( G.getFirst(f,v); G.valid(f); G.next(f)) {
-            NodeIt w=G.tail(f); 
+          for( G.first(f,v); G.valid(f); G.next(f)) {
+            Node w=G.tail(f); 
             
-            if ( !scanned.get(w) ) {
-              if ( !reached.get(w) ) {
-                reached.set(w,true);
-                heap.push(w, edge_weight.get(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.get(f) < heap.get(w) ) {
+              } else if ( edge_weight[f] < heap.get(w) ) {
                 tree_edge.set(w,f);
-                heap.decrease(w, edge_weight.get(f)); 
+                heap.decrease(w, edge_weight[f]); 
               }
             }
@@ -130 +131 @@
       T weight() {
         T w=0;
-        EachNodeIt u;
-        for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
+        NodeIt u;
+        for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
         return w;
       }
      
 
-      EdgeIt tree(NodeIt v) {
-        return tree_edge.get(v);
+      Edge tree(Node v) {
+        return tree_edge[v];
       } 
 
@@ -143 +144 @@
       bool conn() {
         bool c=true;
-        EachNodeIt u;
-        for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) 
-          if ( !reached.get(u) ) { 
+        NodeIt u;
+        for ( G.first(u) ; G.valid(u) ; G.next(u) ) 
+          if ( !reached[u] ) { 
             c=false;
             break;
@@ -153 +154 @@
 
 
-      bool reach(NodeIt v) {
-        return reached.get(v);
+      bool reached(Node v) {
+        return reached[v];
       }
 
 
-      NodeIt root() {
+      Node root() {
         return r;
       }