COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
03/19/04 23:16:05 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@306
Message:

updating

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/prim.h

    r173 r211  
    11// -*- C++ -*-
    2 
    3 //kell hogy tree_edge invalid elekbol alljon, Szep
    4 //lenne ha az elejen a konstrualas ilyet adna, de
    5 //ugy fest nem igy lesz, ekkor invalidalni kell
    6 
    72/*
    8  *template <Graph, T, Heap=FibHeap>
     3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
    94 *
    105 *Constructor:
    116 *
    12  *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
     7 *Prim(Graph G, LengthMap weight)
    138 *
    149 *
    1510 *Methods:
    1611 *
    17  *void run()
     12 *void run() : Runs the Prim-algorithm from a random node
    1813 *
    19  *  The followings functions should be used after run() was already run.
     14 *void run(Node r) : Runs the Prim-algorithm from node s
    2015 *
    21  *T weight() : returns the minimum weight of a spanning tree of the
    22  *   component of the root.
     16 *T weight() : After run(r) was run, it returns the minimum
     17 *   weight of a spanning tree of the component of the root.
    2318 *
    24  *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
    25  *   to the root. Returns an invalid iterator if v=s or v is
    26  *   not reachable from 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.
    2722 *
    28  *bool conn() : true iff G is connected
     23 *bool conn() : After run(r) was run, it is true iff G is connected
    2924 *
    30  *bool reach(NodeIt v) : true iff v is in the same component as the root
     25 *bool reached(Node v) : After run(r) was run, it is true
     26 *   iff v is in the same component as the root
    3127 *
    32  *NodeIt root() : returns the root
     28 *Node root() : returns the root
    3329 *
    3430 */
    3531
    36 #ifndef PRIM_H
    37 #define PRIM_H
     32#ifndef HUGO_PRIM_H
     33#define HUGO_PRIM_H
    3834
    3935#include <fib_heap.h>
    40 
    41 #include <iostream>
     36#include <invalid.h>
    4237
    4338namespace hugo {
    4439
    4540  template <typename Graph, typename T,
    46     typename Heap=FibHeap<typename Graph::NodeIt, T,
    47     typename Graph::NodeMap<int> > >
     41    typename Heap=FibHeap<typename Graph::Node, T,
     42    typename Graph::NodeMap<int> >,
     43    typename LengthMap=typename Graph::EdgeMap<T> >
    4844    class Prim{
     45      typedef typename Graph::Node Node;
    4946      typedef typename Graph::NodeIt NodeIt;
    50       typedef typename Graph::EachNodeIt EachNodeIt;
    51       typedef typename Graph::EdgeIt EdgeIt;
     47      typedef typename Graph::Edge Edge;
    5248      typedef typename Graph::OutEdgeIt OutEdgeIt;
    5349      typedef typename Graph::InEdgeIt InEdgeIt; 
    5450
    55       Graph& G;
    56       NodeIt r;
    57       typename Graph::NodeMap<EdgeIt> tree_edge;
     51      const Graph& G;
     52      const LengthMap& edge_weight;
     53      typename Graph::NodeMap<Edge> tree_edge;
    5854      typename Graph::NodeMap<T> min_weight;
    59       typename Graph::EdgeMap<T>& edge_weight;
    60       typename Graph::NodeMap<bool> reached;
     55      typename Graph::NodeMap<bool> reach;
    6156         
    6257  public :
    6358
    64       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight,
    65            NodeIt const _r) :
    66       G(_G), r(_r), tree_edge(G), min_weight(G),
    67       edge_weight(_edge_weight), reached(G, false) { }
     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) { }
    6862
    69       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) :
    70       G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
    71       {
    72         EachNodeIt _r;     //FIXME
    73         G.getFirst(_r);
    74         r=_r;
     63
     64      void run() {
     65        NodeIt _r;     
     66        G.first(_r);
     67        run(_r);
    7568      }
    7669
    7770
    78       void run() {
     71      void run(Node r) {
     72
     73        NodeIt u;
     74        for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
     75          tree_edge.set(u,INVALID);
     76          min_weight.set(u,0);
     77          reach.set(u,false);
     78        }
     79
    7980
    8081        typename Graph::NodeMap<bool> scanned(G, false);
     
    8485
    8586        heap.push(r,0);
    86         reached.set(r, true);
     87        reach.set(r, true);
    8788
    8889        while ( !heap.empty() ) {
    8990
    90           NodeIt v=heap.top();
     91          Node v=heap.top();
    9192          min_weight.set(v, heap.get(v));
    9293          heap.pop();
     
    9495
    9596          OutEdgeIt e;
    96           for( G.getFirst(e,v); G.valid(e); G.next(e)) {
    97             NodeIt w=G.head(e);
     97          for( G.first(e,v); G.valid(e); G.next(e)) {
     98            Node w=G.head(e);
    9899           
    99             if ( !scanned.get(w) ) {
    100               if ( !reached.get(w) ) {
    101                 reached.set(w,true);
    102                 heap.push(w, edge_weight.get(e));
     100            if ( !scanned[w] ) {
     101              if ( !reach[w] ) {
     102                reach.set(w,true);
     103                heap.push(w, edge_weight[e]);
    103104                tree_edge.set(w,e);
    104               } else if ( edge_weight.get(e) < heap.get(w) ) {
     105              } else if ( edge_weight[e] < heap.get(w) ) {
    105106                tree_edge.set(w,e);
    106                 heap.decrease(w, edge_weight.get(e));
     107                heap.decrease(w, edge_weight[e]);
    107108              }
    108109            }
     
    110111
    111112          InEdgeIt f;
    112           for( G.getFirst(f,v); G.valid(f); G.next(f)) {
    113             NodeIt w=G.tail(f);
     113          for( G.first(f,v); G.valid(f); G.next(f)) {
     114            Node w=G.tail(f);
    114115           
    115             if ( !scanned.get(w) ) {
    116               if ( !reached.get(w) ) {
    117                 reached.set(w,true);
    118                 heap.push(w, edge_weight.get(f));
     116            if ( !scanned[w] ) {
     117              if ( !reach[w] ) {
     118                reach.set(w,true);
     119                heap.push(w, edge_weight[f]);
    119120                tree_edge.set(w,f);
    120               } else if ( edge_weight.get(f) < heap.get(w) ) {
     121              } else if ( edge_weight[f] < heap.get(w) ) {
    121122                tree_edge.set(w,f);
    122                 heap.decrease(w, edge_weight.get(f));
     123                heap.decrease(w, edge_weight[f]);
    123124              }
    124125            }
     
    130131      T weight() {
    131132        T w=0;
    132         EachNodeIt u;
    133         for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
     133        NodeIt u;
     134        for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
    134135        return w;
    135136      }
    136137     
    137138
    138       EdgeIt tree(NodeIt v) {
    139         return tree_edge.get(v);
     139      Edge tree(Node v) {
     140        return tree_edge[v];
    140141      }
    141142
     
    143144      bool conn() {
    144145        bool c=true;
    145         EachNodeIt u;
    146         for ( G.getFirst(u) ; G.valid(u) ; G.next(u) )
    147           if ( !reached.get(u) ) {
     146        NodeIt u;
     147        for ( G.first(u) ; G.valid(u) ; G.next(u) )
     148          if ( !reached[u] ) {
    148149            c=false;
    149150            break;
     
    153154
    154155
    155       bool reach(NodeIt v) {
    156         return reached.get(v);
     156      bool reached(Node v) {
     157        return reached[v];
    157158      }
    158159
    159160
    160       NodeIt root() {
     161      Node root() {
    161162        return r;
    162163      }
Note: See TracChangeset for help on using the changeset viewer.