COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/prim.h @ 173:de9849252e78

Last change on this file since 173:de9849252e78 was 173:de9849252e78, checked in by jacint, 16 years ago

* empty log message *

File size: 3.5 KB
Line 
1// -*- 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
7/*
8 *template <Graph, T, Heap=FibHeap>
9 *
10 *Constructor:
11 *
12 *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
13 *
14 *
15 *Methods:
16 *
17 *void run()
18 *
19 *  The followings functions should be used after run() was already run.
20 *
21 *T weight() : returns the minimum weight of a spanning tree of the
22 *   component of the root.
23 *
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.
27 *
28 *bool conn() : true iff G is connected
29 *
30 *bool reach(NodeIt v) : true iff v is in the same component as the root
31 *
32 *NodeIt root() : returns the root
33 *
34 */
35
36#ifndef PRIM_H
37#define PRIM_H
38
39#include <fib_heap.h>
40
41#include <iostream>
42
43namespace hugo {
44
45  template <typename Graph, typename T,
46    typename Heap=FibHeap<typename Graph::NodeIt, T,
47    typename Graph::NodeMap<int> > >
48    class Prim{
49      typedef typename Graph::NodeIt NodeIt;
50      typedef typename Graph::EachNodeIt EachNodeIt;
51      typedef typename Graph::EdgeIt EdgeIt;
52      typedef typename Graph::OutEdgeIt OutEdgeIt;
53      typedef typename Graph::InEdgeIt InEdgeIt; 
54
55      Graph& G;
56      NodeIt r;
57      typename Graph::NodeMap<EdgeIt> tree_edge;
58      typename Graph::NodeMap<T> min_weight;
59      typename Graph::EdgeMap<T>& edge_weight;
60      typename Graph::NodeMap<bool> reached;
61         
62  public :
63
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) { }
68
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;
75      }
76
77
78      void run() {
79
80        typename Graph::NodeMap<bool> scanned(G, false);
81        typename Graph::NodeMap<int> heap_map(G,-1);
82       
83        Heap heap(heap_map);
84
85        heap.push(r,0);
86        reached.set(r, true);
87
88        while ( !heap.empty() ) {
89
90          NodeIt v=heap.top();
91          min_weight.set(v, heap.get(v));
92          heap.pop();
93          scanned.set(v,true);
94
95          OutEdgeIt e;
96          for( G.getFirst(e,v); G.valid(e); G.next(e)) {
97            NodeIt w=G.head(e);
98           
99            if ( !scanned.get(w) ) {
100              if ( !reached.get(w) ) {
101                reached.set(w,true);
102                heap.push(w, edge_weight.get(e));
103                tree_edge.set(w,e);
104              } else if ( edge_weight.get(e) < heap.get(w) ) {
105                tree_edge.set(w,e);
106                heap.decrease(w, edge_weight.get(e));
107              }
108            }
109          }
110
111          InEdgeIt f;
112          for( G.getFirst(f,v); G.valid(f); G.next(f)) {
113            NodeIt w=G.tail(f);
114           
115            if ( !scanned.get(w) ) {
116              if ( !reached.get(w) ) {
117                reached.set(w,true);
118                heap.push(w, edge_weight.get(f));
119                tree_edge.set(w,f);
120              } else if ( edge_weight.get(f) < heap.get(w) ) {
121                tree_edge.set(w,f);
122                heap.decrease(w, edge_weight.get(f));
123              }
124            }
125          }
126        }
127      }
128 
129
130      T weight() {
131        T w=0;
132        EachNodeIt u;
133        for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
134        return w;
135      }
136     
137
138      EdgeIt tree(NodeIt v) {
139        return tree_edge.get(v);
140      }
141
142
143      bool conn() {
144        bool c=true;
145        EachNodeIt u;
146        for ( G.getFirst(u) ; G.valid(u) ; G.next(u) )
147          if ( !reached.get(u) ) {
148            c=false;
149            break;
150          }
151        return c;
152      }
153
154
155      bool reach(NodeIt v) {
156        return reached.get(v);
157      }
158
159
160      NodeIt root() {
161        return r;
162      }
163
164    };
165
166}
167
168#endif
169
170
Note: See TracBrowser for help on using the repository browser.