1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci_bfs.hh Tue Dec 30 13:59:08 2003 +0000
1.3 @@ -0,0 +1,133 @@
1.4 +#ifndef MARCI_BFS_HH
1.5 +#define MARCI_BFS_HH
1.6 +
1.7 +#include <queue>
1.8 +
1.9 +#include <marci_graph_traits.hh>
1.10 +#include <marci_property_vector.hh>
1.11 +
1.12 +namespace marci {
1.13 +
1.14 + template <typename graph_type>
1.15 + struct bfs {
1.16 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.17 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.18 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.19 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.20 +
1.21 + graph_type& G;
1.22 + node_iterator s;
1.23 + node_property_vector<graph_type, bool> reached;
1.24 + node_property_vector<graph_type, edge_iterator> pred;
1.25 + node_property_vector<graph_type, int> dist;
1.26 + std::queue<node_iterator> bfs_queue;
1.27 + bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.28 + bfs_queue.push(s);
1.29 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
1.30 + reached.put(i, false);
1.31 + reached.put(s, true);
1.32 + dist.put(s, 0);
1.33 + }
1.34 +
1.35 + void run() {
1.36 + while (!bfs_queue.empty()) {
1.37 + node_iterator v=bfs_queue.front();
1.38 + out_edge_iterator e=G.first_out_edge(v);
1.39 + bfs_queue.pop();
1.40 + for( ; e.is_valid(); ++e) {
1.41 + node_iterator w=G.head(e);
1.42 + std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.43 + if (!reached.get(w)) {
1.44 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.45 + bfs_queue.push(w);
1.46 + dist.put(w, dist.get(v)+1);
1.47 + pred.put(w, e);
1.48 + reached.put(w, true);
1.49 + } else {
1.50 + std::cout << G.id(w) << " is already reached" << std::endl;
1.51 + }
1.52 + }
1.53 + }
1.54 + }
1.55 + };
1.56 +
1.57 + template <typename graph_type>
1.58 + struct bfs_visitor {
1.59 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.60 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.61 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.62 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.63 + graph_type& G;
1.64 + bfs_visitor(graph_type& _G) : G(_G) { }
1.65 + void at_previously_reached(out_edge_iterator& e) {
1.66 + //node_iterator v=G.tail(e);
1.67 + node_iterator w=G.head(e);
1.68 + std::cout << G.id(w) << " is already reached" << std::endl;
1.69 + }
1.70 + void at_newly_reached(out_edge_iterator& e) {
1.71 + //node_iterator v=G.tail(e);
1.72 + node_iterator w=G.head(e);
1.73 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.74 + }
1.75 + };
1.76 +
1.77 + template <typename graph_type, typename reached_type, typename visitor_type>
1.78 + struct bfs_iterator {
1.79 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.80 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.81 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.82 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.83 +
1.84 + graph_type& G;
1.85 + std::queue<out_edge_iterator>& bfs_queue;
1.86 + reached_type& reached;
1.87 + visitor_type& visitor;
1.88 + void process() {
1.89 + while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.90 + if (bfs_queue.empty()) return;
1.91 + out_edge_iterator e=bfs_queue.front();
1.92 + //node_iterator v=G.tail(e);
1.93 + node_iterator w=G.head(e);
1.94 + if (!reached.get(w)) {
1.95 + visitor.at_newly_reached(e);
1.96 + bfs_queue.push(G.first_out_edge(w));
1.97 + reached.put(w, true);
1.98 + } else {
1.99 + visitor.at_previously_reached(e);
1.100 + }
1.101 + }
1.102 + bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
1.103 + //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.104 + is_valid();
1.105 + }
1.106 + bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
1.107 + //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.108 + //if (bfs_queue.empty()) return *this;
1.109 + if (!is_valid()) return *this;
1.110 + ++(bfs_queue.front());
1.111 + //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.112 + is_valid();
1.113 + return *this;
1.114 + }
1.115 + //void next() {
1.116 + // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.117 + // if (bfs_queue.empty()) return;
1.118 + // ++(bfs_queue.front());
1.119 + // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.120 + //}
1.121 + bool is_valid() {
1.122 + while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.123 + if (bfs_queue.empty()) return false; else return true;
1.124 + }
1.125 + //bool finished() {
1.126 + // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.127 + // if (bfs_queue.empty()) return true; else return false;
1.128 + //}
1.129 + operator edge_iterator () { return bfs_queue.front(); }
1.130 +
1.131 + };
1.132 +
1.133 +
1.134 +} // namespace marci
1.135 +
1.136 +#endif //MARCI_BFS_HH
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci_graph_concept.txt Tue Dec 30 13:59:08 2003 +0000
2.3 @@ -0,0 +1,215 @@
2.4 +ETIK-OL-NOLIB-NEGRES graph concept-ek.
2.5 +
2.6 + Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok.
2.7 +A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
2.8 +operacio elegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
2.9 +ujakra van szukseg.
2.10 +
2.11 + Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat,
2.12 +az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet
2.13 +ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal
2.14 +ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly,
2.15 +a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere,
2.16 +a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen
2.17 +property_vector csak azokra a graf-objektumokra ervenyes, melyek
2.18 +letrehozasanak pillanataban a grafhoz tartoznak.
2.19 +
2.20 +marci_bfs.hh //bfs, tejesen kiserleti
2.21 +marci_graph_demo.cc //peldaprogi a lisas graf hasznalatahoz
2.22 +marci_graph_traits.hh //alapertelmezett graph_traits
2.23 +marci_list_graph.hh //list_graph megvalositas
2.24 +marci_max_flow.hh //folyam, kiserleti
2.25 +marci_property_vector.hh //property vector megvalosites indexelt grafokhoz
2.26 +graf es iterator tipusok:
2.27 +
2.28 +class list_graph
2.29 +
2.30 +class node_iterator
2.31 +trivialis node iterator, csak cimezni lehet vele, pl property vectort
2.32 +
2.33 +class each_node_iterator
2.34 +node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
2.35 +
2.36 +class edge_iterator
2.37 +trivialis edge iterator, csak cimezni lehet vele, pl property vectort
2.38 +
2.39 +class each_edge_iterator
2.40 +edge iterator a graf osszes elenek bejarasara
2.41 +
2.42 +class out_edge_iterator
2.43 +edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
2.44 +
2.45 +class in_edge_iterator
2.46 +edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
2.47 +
2.48 +class sym_edge_iterator
2.49 +edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
2.50 +
2.51 +default constructor:
2.52 +
2.53 +list_graph()
2.54 +
2.55 +A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
2.56 +Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
2.57 +ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
2.58 +iteratorok metodusait ne hasznaljuk. Miert? Azt szeretnenk, ha 1 ponthalmazon
2.59 +van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
2.60 +out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
2.61 +out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
2.62 +esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
2.63 +
2.64 +each_node_iterator first_node()
2.65 +each_edge_iterator first_edge()
2.66 +out_edge_iterator first_out_edge(const node_iterator&)
2.67 +in_edge_iterator first_in_edge(const node_iterator&)
2.68 +sym_edge_iterator first_sym_edge(const node_iterator&)
2.69 +
2.70 +node_iterator tail(const edge_iterator&)
2.71 +node_iterator head(const edge_iterator&)
2.72 +
2.73 +node_iterator a_node(const out_edge_iterator&)
2.74 +node_iterator a_node(const in_edge_iterator&)
2.75 +node_iterator a_node(const sym_edge_iterator&)
2.76 +//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
2.77 +
2.78 +node_iterator b_node(const out_edge_iterator&)
2.79 +node_iterator b_node(const in_edge_iterator&)
2.80 +node_iterator b_node(const sym_edge_iterator&)
2.81 +//az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
2.82 +
2.83 +node_iterator invalid_node()
2.84 +edge_iterator invalid_edge()
2.85 +out_edge_iterator invalid_out_edge()
2.86 +in_edge_iterator invalid_in_edge()
2.87 +sym_edge_iterator invalid_sym_edge()
2.88 +
2.89 +//az iteratorok ures konstruktorai meghatarozatlan
2.90 +tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
2.91 +lehet ervenytelent csinalni.
2.92 +Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
2.93 +
2.94 +Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
2.95 +
2.96 +void get_first(each_node_iterator&)
2.97 +void get_first(each_edge_iterator&)
2.98 +void get_first(out_edge_iterator&, const node_iterator&)
2.99 +void get_first(in_edge_iterator&, const node_iterator&)
2.100 +void get_first(sym_edge_iterator&, const node_iterator&)
2.101 +
2.102 +void get_tail(node_iterator&, const edge_iterator&)
2.103 +void get_head(node_iterator&, const edge_iterator&)
2.104 +
2.105 +void get_a_node(node_iterator&, const out_edge_iterator&)
2.106 +void get_a_node(node_iterator&, const in_edge_iterator&)
2.107 +void get_a_node(node_iterator&, const sym_edge_iterator&)
2.108 +
2.109 +void get_b_node(node_iterator&, const out_edge_iterator&)
2.110 +void get_b_node(node_iterator&, const in_edge_iterator&)
2.111 +void get_b_node(node_iterator&, const sym_edge_iterator&)
2.112 +
2.113 +void get_invalid(node_iterator&)
2.114 +void get_invalid(edge_iterator&)
2.115 +void get_invalid(out_edge_iterator&)
2.116 +void get_invalid(in_edge_iterator&)
2.117 +void get_invalid(sym_edge_iterator&)
2.118 +
2.119 +Pontok azonositasara de meginkabb property vectorokhoz:
2.120 +
2.121 +int id(const node_iterator&)
2.122 +int id(const edge_iterator&)
2.123 +
2.124 +Pontok es elek hozzaadasanak metodusai:
2.125 +
2.126 +node_iterator add_node()
2.127 +edge_iterator add_edge(const node_iterator&, const node_iterator&)
2.128 +
2.129 +Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
2.130 +ezek nem a list_graph metodusai
2.131 +
2.132 +friend std::ostream& operator<<(std::ostream&, const node_iterator&)
2.133 +friend std::ostream& operator<<(std::ostream&, const edge_iterator&)
2.134 +
2.135 +node_iterator metodusai:
2.136 +node_iterator()
2.137 +bool is_valid()
2.138 +ezek nem tagfuggvenyek:
2.139 +friend bool operator==(const node_iterator&, const node_iterator&)
2.140 +friend bool operator!=(const node_iterator& u, const node_iterator& v)
2.141 +
2.142 +each_node_iterator metodusai:
2.143 +ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
2.144 +each_node_iterator()
2.145 +each_node_iterator& operator++()
2.146 +
2.147 +edge_iterator metodusai:
2.148 +edge_iterator()
2.149 +bool is_valid()
2.150 +ezek nem tagfvek:
2.151 +friend bool operator==(const edge_iterator&, const edge_iterator&)
2.152 +friend bool operator!=(const edge_iterator&, const edge_iterator&)
2.153 +ujra tagfv-ek.
2.154 +//node_iterator tail_node() const nem javasolt
2.155 +//node_iterator head_node() const nem javasolt
2.156 +
2.157 +each_edge_iterator metodusai:
2.158 +edge_iterator-bol szarmazik
2.159 +each_edge_iterator()
2.160 +each_edge_iterator& operator++()
2.161 +
2.162 +out_edge_iterator metodusai:
2.163 +edge_iterator-bol szarmazik
2.164 +out_edge_iterator()
2.165 +//out_edge_iterator(const node_iterator&) nem javasolt
2.166 +out_edge_iterator& operator++()
2.167 +//node_iterator a_node() const nem javasolt
2.168 +//node_iterator b_node() const
2.169 +
2.170 +
2.171 +in_edge_iterator metodusai:
2.172 +edge_iterator-bol szarmazik
2.173 +in_edge_iterator()
2.174 +//in_edge_iterator(const node_iterator&) nem javasolt
2.175 +in_edge_iterator& operator++()
2.176 +//node_iterator a_node() const nem javasolt
2.177 +//node_iterator b_node() const
2.178 +
2.179 +
2.180 +sym_edge_iterator metodusai:
2.181 +edge_iterator-bol szarmazik
2.182 +sym_edge_iterator()
2.183 +//sym_edge_iterator(const node_iterator&) nem javasolt
2.184 +sym_edge_iterator& operator++()
2.185 +//node_iterator a_node() const nem javasolt
2.186 +//node_iterator b_node() const
2.187 +
2.188 +Node propery array-okrol:
2.189 +
2.190 +template <typename graph_type, typename T>
2.191 +class node_property_vector
2.192 +
2.193 +metodusok:
2.194 +
2.195 +node_property_vector(graph_type&)
2.196 +void put(graph_traits<graph_type>::node_iterator, const T&)
2.197 +T get(graph_traits<graph_type>::node_iterator)
2.198 +
2.199 +Ugyanez edge_property_array-okkal
2.200 +
2.201 +template <typename graph_type, typename T>
2.202 +class edge_property_vector
2.203 +
2.204 +edge_property_vector(graph_type&)
2.205 +void put(graph_traits<graph_type>::edge_iterator, const T&)
2.206 +get(graph_traits<graph_type>::edge_iterator)
2.207 +
2.208 + Ennyi nem javasolas utan, meg nehany szo.
2.209 + Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
2.210 +csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
2.211 +Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
2.212 +graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
2.213 +tobb grafot ugyanazon pont-iteratorokkal.
2.214 + Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
2.215 +at a propertyket az algoritmusoknak, algoritmus-objektumoknak.
2.216 +Errol majd kesobb.
2.217 +
2.218 +marci@cs.elte.hu
2.219 \ No newline at end of file
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci_graph_demo.cc Tue Dec 30 13:59:08 2003 +0000
3.3 @@ -0,0 +1,173 @@
3.4 +#include <iostream>
3.5 +#include <vector>
3.6 +#include <string>
3.7 +
3.8 +#include <marci_list_graph.hh>
3.9 +#include <marci_graph_traits.hh>
3.10 +#include <marci_property_vector.hh>
3.11 +#include <marci_bfs.hh>
3.12 +#include <marci_max_flow.hh>
3.13 +
3.14 +using namespace marci;
3.15 +
3.16 +int main (int, char*[])
3.17 +{
3.18 + typedef graph_traits<list_graph>::node_iterator node_iterator;
3.19 + typedef graph_traits<list_graph>::edge_iterator edge_iterator;
3.20 + typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
3.21 + typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
3.22 + typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
3.23 + typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
3.24 + typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
3.25 +
3.26 + list_graph G;
3.27 + std::vector<node_iterator> vector_of_node_iterators;
3.28 + for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
3.29 + for(int i=0; i!=8; ++i)
3.30 + for(int j=0; j!=8; ++j) {
3.31 + if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);
3.32 + }
3.33 +
3.34 + std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
3.35 + std::cout << "number of nodes: " << number_of<each_node_iterator>(G.first_node()) << std::endl;
3.36 +
3.37 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.38 + std::cout << "node " << G.id(i) << std::endl;
3.39 + std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
3.40 + for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
3.41 + std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
3.42 + }
3.43 + std::cout << std::endl;
3.44 + std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
3.45 + for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
3.46 + std::cout << j << " "; }
3.47 + std::cout << std::endl;
3.48 + std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
3.49 + for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
3.50 + std::cout << j << " "; }
3.51 + std::cout<<std::endl;
3.52 + }
3.53 +
3.54 + std::cout << "all edges: ";
3.55 + for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
3.56 + std::cout << i << " ";
3.57 + }
3.58 + std::cout << std::endl;
3.59 +
3.60 + std::cout << "node property array test" << std::endl;
3.61 + node_property_vector<list_graph, int> my_property_vector(G);
3.62 + each_node_iterator v;
3.63 + G.get_first(v);
3.64 + my_property_vector.put(v, 42);
3.65 + my_property_vector.put(++G.first_node(), 314);
3.66 + my_property_vector.put(++++G.first_node(), 1956);
3.67 + my_property_vector.put(vector_of_node_iterators[3], 1989);
3.68 + my_property_vector.put(vector_of_node_iterators[4], 2003);
3.69 + my_property_vector.put(vector_of_node_iterators[7], 1978);
3.70 + std::cout << "some node property values..." << std::endl;
3.71 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.72 + std::cout << my_property_vector.get(i) << std::endl;
3.73 + }
3.74 + int _i=1;
3.75 + int _ii=1;
3.76 + edge_property_vector<list_graph, int> my_edge_property(G);
3.77 + for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
3.78 + my_edge_property.put(i, _i);
3.79 + _i*=_ii; ++_ii;
3.80 + }
3.81 +
3.82 + std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
3.83 + for(each_edge_iterator j=G.first_edge(); j.is_valid(); ++j) {
3.84 + std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
3.85 + }
3.86 + std::cout << std::endl;
3.87 +
3.88 + //std::cout << "the same for inedges of the nodes..." << std::endl;
3.89 + //k=0;
3.90 + //for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.91 + // for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
3.92 + // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
3.93 + // }
3.94 + // std::cout << std::endl;
3.95 + //}
3.96 +
3.97 + std::cout << "bfs from the first node" << std::endl;
3.98 + bfs<list_graph> bfs_test(G, G.first_node());
3.99 + bfs_test.run();
3.100 + std::cout << "reached: ";
3.101 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.102 + std::cout << bfs_test.reached.get(i) << " ";
3.103 + }
3.104 + std::cout<<std::endl;
3.105 + std::cout << "dist: ";
3.106 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.107 + std::cout << bfs_test.dist.get(i) << " ";
3.108 + }
3.109 + std::cout<<std::endl;
3.110 +
3.111 +
3.112 + std::cout << "augmenting path flow algorithm test..." << std::endl;
3.113 + list_graph flow_test;
3.114 +
3.115 + node_iterator s=flow_test.add_node();
3.116 + node_iterator v1=flow_test.add_node();
3.117 + node_iterator v2=flow_test.add_node();
3.118 + node_iterator v3=flow_test.add_node();
3.119 + node_iterator v4=flow_test.add_node();
3.120 + node_iterator t=flow_test.add_node();
3.121 +
3.122 + node_property_vector<list_graph, std::string> node_name(flow_test);
3.123 + node_name.put(s, "s");
3.124 + node_name.put(v1, "v1");
3.125 + node_name.put(v2, "v2");
3.126 + node_name.put(v3, "v3");
3.127 + node_name.put(v4, "v4");
3.128 + node_name.put(t, "t");
3.129 +
3.130 + edge_iterator s_v1=flow_test.add_edge(s, v1);
3.131 + edge_iterator s_v2=flow_test.add_edge(s, v2);
3.132 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
3.133 + edge_iterator v2_v1=flow_test.add_edge(v2, v1);
3.134 + edge_iterator v1_v3=flow_test.add_edge(v1, v3);
3.135 + edge_iterator v3_v2=flow_test.add_edge(v3, v2);
3.136 + edge_iterator v2_v4=flow_test.add_edge(v2, v4);
3.137 + edge_iterator v4_v3=flow_test.add_edge(v4, v3);
3.138 + edge_iterator v3_t=flow_test.add_edge(v3, t);
3.139 + edge_iterator v4_t=flow_test.add_edge(v4, t);
3.140 +
3.141 + edge_property_vector<list_graph, int> cap(flow_test);
3.142 +
3.143 + cap.put(s_v1, 16);
3.144 + cap.put(s_v2, 13);
3.145 + cap.put(v1_v2, 10);
3.146 + cap.put(v2_v1, 4);
3.147 + cap.put(v1_v3, 12);
3.148 + cap.put(v3_v2, 9);
3.149 + cap.put(v2_v4, 14);
3.150 + cap.put(v4_v3, 7);
3.151 + cap.put(v3_t, 20);
3.152 + cap.put(v4_t, 4);
3.153 +
3.154 + std::cout << "on directed graph graph" << std::endl; //<< flow_test;
3.155 + std::cout << "names and capacity values" << std::endl;
3.156 + for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
3.157 + std::cout << node_name.get(i) << ": ";
3.158 + std::cout << "out edges: ";
3.159 + for(out_edge_iterator j=flow_test.first_out_edge(i); j.is_valid(); ++j)
3.160 + std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
3.161 + std::cout << "in edges: ";
3.162 + for(in_edge_iterator j=flow_test.first_in_edge(i); j.is_valid(); ++j)
3.163 + std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
3.164 + std::cout << std::endl;
3.165 + }
3.166 +
3.167 +
3.168 + //for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
3.169 + // std::cout << i << " ";
3.170 + //}
3.171 +
3.172 + max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);
3.173 + max_flow_test.run();
3.174 +
3.175 + return 0;
3.176 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/marci_graph_traits.hh Tue Dec 30 13:59:08 2003 +0000
4.3 @@ -0,0 +1,19 @@
4.4 +#ifndef MARCI_GRAPH_TRAITS_HH
4.5 +#define MARCI_GRAPH_TRAITS_HH
4.6 +
4.7 +namespace marci {
4.8 +
4.9 + template <typename graph_type>
4.10 + struct graph_traits {
4.11 + typedef typename graph_type::node_iterator node_iterator;
4.12 + typedef typename graph_type::edge_iterator edge_iterator;
4.13 + typedef typename graph_type::each_node_iterator each_node_iterator;
4.14 + typedef typename graph_type::each_edge_iterator each_edge_iterator;
4.15 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
4.16 + typedef typename graph_type::in_edge_iterator in_edge_iterator;
4.17 + typedef typename graph_type::sym_edge_iterator sym_edge_iterator;
4.18 + };
4.19 +
4.20 +} // namespace marci
4.21 +
4.22 +#endif //MARCI_GRAPH_TRAITS_HH
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/marci_list_graph.hh Tue Dec 30 13:59:08 2003 +0000
5.3 @@ -0,0 +1,334 @@
5.4 +#ifndef MARCI_LIST_GRAPH_HH
5.5 +#define MARCI_LIST_GRAPH_HH
5.6 +
5.7 +#include <iostream>
5.8 +
5.9 +namespace marci {
5.10 +
5.11 + class list_graph {
5.12 + class node_item;
5.13 + class edge_item;
5.14 + public:
5.15 + class node_iterator;
5.16 + class each_node_iterator;
5.17 + class edge_iterator;
5.18 + class each_edge_iterator;
5.19 + class out_edge_iterator;
5.20 + class in_edge_iterator;
5.21 + class sym_edge_iterator;
5.22 + private:
5.23 + int node_id;
5.24 + int edge_id;
5.25 +
5.26 + node_item* _first_node;
5.27 + node_item* _last_node;
5.28 +
5.29 + class node_item {
5.30 + friend class list_graph;
5.31 + friend class node_iterator;
5.32 + friend class each_node_iterator;
5.33 + friend class edge_iterator;
5.34 + friend class each_edge_iterator;
5.35 + friend class out_edge_iterator;
5.36 + friend class in_edge_iterator;
5.37 + friend class sym_edge_iterator;
5.38 + friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
5.39 + friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
5.40 + list_graph* G;
5.41 + int id;
5.42 + edge_item* _first_out_edge;
5.43 + edge_item* _last_out_edge;
5.44 + edge_item* _first_in_edge;
5.45 + edge_item* _last_in_edge;
5.46 + node_item* _next_node;
5.47 + node_item* _prev_node;
5.48 + public:
5.49 + node_item() { }
5.50 + };
5.51 +
5.52 + class edge_item {
5.53 + friend class list_graph;
5.54 + friend class node_iterator;
5.55 + friend class each_node_iterator;
5.56 + friend class edge_iterator;
5.57 + friend class each_edge_iterator;
5.58 + friend class out_edge_iterator;
5.59 + friend class in_edge_iterator;
5.60 + friend class sym_edge_iterator;
5.61 + friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
5.62 + list_graph* G;
5.63 + int id;
5.64 + node_item* _tail;
5.65 + node_item* _head;
5.66 + edge_item* _next_out;
5.67 + edge_item* _prev_out;
5.68 + edge_item* _next_in;
5.69 + edge_item* _prev_in;
5.70 + public:
5.71 + edge_item() { }
5.72 + };
5.73 +
5.74 + node_item* _add_node() {
5.75 + node_item* p=new node_item;
5.76 + p->id=node_id++;
5.77 + p->_first_out_edge=0;
5.78 + p->_last_out_edge=0;
5.79 + p->_first_in_edge=0;
5.80 + p->_last_in_edge=0;
5.81 + p->_prev_node=_last_node;
5.82 + p->_next_node=0;
5.83 + if (_last_node) _last_node->_next_node=p;
5.84 + _last_node=p;
5.85 + if (!_first_node) _first_node=p;
5.86 + return p;
5.87 + }
5.88 +
5.89 + edge_item* _add_edge(node_item* _tail, node_item* _head) {
5.90 + edge_item* e=new edge_item;
5.91 + e->id=edge_id++;
5.92 + e->_tail=_tail;
5.93 + e->_head=_head;
5.94 +
5.95 + e->_prev_out=_tail->_last_out_edge;
5.96 + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
5.97 + _tail->_last_out_edge=e;
5.98 + if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
5.99 +
5.100 + e->_prev_in=_head->_last_in_edge;
5.101 + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
5.102 + _head->_last_in_edge=e;
5.103 + if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
5.104 + return e;
5.105 + }
5.106 +
5.107 + public:
5.108 +
5.109 + /* default constructor */
5.110 +
5.111 + list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { }
5.112 +
5.113 + /* functions to construct iterators from the graph, or from each other */
5.114 +
5.115 + each_node_iterator first_node() { return each_node_iterator(_first_node); }
5.116 + each_edge_iterator first_edge() {
5.117 + node_item* v=_first_node;
5.118 + edge_item* edge=v->_first_out_edge;
5.119 + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
5.120 + return each_edge_iterator(v, edge);
5.121 + }
5.122 +
5.123 + out_edge_iterator first_out_edge(const node_iterator& v) {
5.124 + return out_edge_iterator(v);
5.125 + }
5.126 + in_edge_iterator first_in_edge(const node_iterator& v) {
5.127 + return in_edge_iterator(v);
5.128 + }
5.129 + sym_edge_iterator first_sym_edge(const node_iterator& v) {
5.130 + return sym_edge_iterator(v);
5.131 + }
5.132 + node_iterator tail(const edge_iterator& e) { return e.tail_node(); }
5.133 + node_iterator head(const edge_iterator& e) { return e.head_node(); }
5.134 +
5.135 + node_iterator a_node(const out_edge_iterator& e) { return e.a_node(); }
5.136 + node_iterator a_node(const in_edge_iterator& e) { return e.a_node(); }
5.137 + node_iterator a_node(const sym_edge_iterator& e) { return e.a_node(); }
5.138 +
5.139 + node_iterator b_node(const out_edge_iterator& e) { return e.b_node(); }
5.140 + node_iterator b_node(const in_edge_iterator& e) { return e.b_node(); }
5.141 + node_iterator b_node(const sym_edge_iterator& e) { return e.b_node(); }
5.142 +
5.143 + node_iterator invalid_node() { return node_iterator(); }
5.144 + edge_iterator invalid_edge() { return edge_iterator(); }
5.145 + out_edge_iterator invalid_out_edge() { return out_edge_iterator(); }
5.146 + in_edge_iterator invalid_in_edge() { return in_edge_iterator(); }
5.147 + sym_edge_iterator invalid_sym_edge() { return sym_edge_iterator(); }
5.148 +
5.149 + /* same methods in other style */
5.150 + /* for experimental purpose */
5.151 +
5.152 + void get_first(each_node_iterator& v) { v=each_node_iterator(_first_node); }
5.153 + void get_first(each_edge_iterator& e) { e=first_edge(); }
5.154 + void get_first(out_edge_iterator& e, const node_iterator& v) {
5.155 + e=out_edge_iterator(v);
5.156 + }
5.157 + void get_first(in_edge_iterator& e, const node_iterator& v) {
5.158 + e=in_edge_iterator(v);
5.159 + }
5.160 + void get_first(sym_edge_iterator& e, const node_iterator& v) {
5.161 + e=sym_edge_iterator(v);
5.162 + }
5.163 + void get_tail(node_iterator& n, const edge_iterator& e) { n=tail(e); }
5.164 + void get_head(node_iterator& n, const edge_iterator& e) { n=head(e); }
5.165 +
5.166 + void get_a_node(node_iterator& n, const out_edge_iterator& e) { n=e.a_node(); }
5.167 + void get_a_node(node_iterator& n, const in_edge_iterator& e) { n=e.a_node(); }
5.168 + void get_a_node(node_iterator& n, const sym_edge_iterator& e) { n=e.a_node(); }
5.169 + void get_b_node(node_iterator& n, const out_edge_iterator& e) { n=e.b_node(); }
5.170 + void get_b_node(node_iterator& n, const in_edge_iterator& e) { n=e.b_node(); }
5.171 + void get_b_node(node_iterator& n, const sym_edge_iterator& e) { n=e.b_node(); }
5.172 + void get_invalid(node_iterator& n) { n=node_iterator(); }
5.173 + void get_invalid(edge_iterator& e) { e=edge_iterator(); }
5.174 + void get_invalid(out_edge_iterator& e) { e=out_edge_iterator(); }
5.175 + void get_invalid(in_edge_iterator& e) { e=in_edge_iterator(); }
5.176 + void get_invalid(sym_edge_iterator& e) { e=sym_edge_iterator(); }
5.177 +
5.178 +
5.179 + /* for getting id's of graph objects */
5.180 + /* these are important for the implementation of property vectors */
5.181 +
5.182 + int id(const node_iterator& v) { return v.node->id; }
5.183 + int id(const edge_iterator& e) { return e.edge->id; }
5.184 +
5.185 + /* adding nodes and edges */
5.186 +
5.187 + node_iterator add_node() { return node_iterator(_add_node()); }
5.188 + edge_iterator add_edge(const node_iterator& u, const node_iterator& v) {
5.189 + return edge_iterator(_add_edge(u.node, v.node));
5.190 + }
5.191 +
5.192 + /* stream operations, for testing purpose */
5.193 +
5.194 + friend std::ostream& operator<<(std::ostream& os, const node_iterator& i) {
5.195 + os << i.node->id; return os;
5.196 + }
5.197 + friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i) {
5.198 + os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
5.199 + return os;
5.200 + }
5.201 +
5.202 + class node_iterator {
5.203 + friend class list_graph;
5.204 +
5.205 + friend class edge_iterator;
5.206 + friend class out_edge_iterator;
5.207 + friend class in_edge_iterator;
5.208 + friend class sym_edge_iterator;
5.209 + protected:
5.210 + node_item* node;
5.211 + friend int list_graph::id(const node_iterator& v);
5.212 + public:
5.213 + node_iterator() : node(0) { }
5.214 + node_iterator(node_item* _node) : node(_node) { }
5.215 + bool is_valid() { return (node!=0); }
5.216 + friend bool operator==(const node_iterator& u, const node_iterator& v) {
5.217 + return v.node==u.node;
5.218 + }
5.219 + friend bool operator!=(const node_iterator& u, const node_iterator& v) {
5.220 + return v.node!=u.node;
5.221 + }
5.222 + friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
5.223 + };
5.224 +
5.225 + class each_node_iterator : public node_iterator {
5.226 + friend class list_graph;
5.227 + public:
5.228 + each_node_iterator() : node_iterator() { }
5.229 + each_node_iterator(node_item* v) : node_iterator(v) { }
5.230 + each_node_iterator& operator++() { node=node->_next_node; return *this; }
5.231 + };
5.232 +
5.233 + class edge_iterator {
5.234 + friend class list_graph;
5.235 +
5.236 + friend class node_iterator;
5.237 + friend class each_node_iterator;
5.238 + protected:
5.239 + edge_item* edge;
5.240 + friend int list_graph::id(const edge_iterator& e);
5.241 + public:
5.242 + edge_iterator() : edge(0) { }
5.243 + edge_iterator(edge_item* _edge) : edge(_edge) { }
5.244 + bool is_valid() { return (edge!=0); }
5.245 + friend bool operator==(const edge_iterator& u, const edge_iterator& v) {
5.246 + return v.edge==u.edge;
5.247 + }
5.248 + friend bool operator!=(const edge_iterator& u, const edge_iterator& v) {
5.249 + return v.edge!=u.edge;
5.250 + }
5.251 + protected:
5.252 + node_iterator tail_node() const { return node_iterator(edge->_tail); }
5.253 + node_iterator head_node() const { return node_iterator(edge->_head); }
5.254 + public:
5.255 + friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
5.256 + };
5.257 +
5.258 + class each_edge_iterator : public edge_iterator {
5.259 + friend class list_graph;
5.260 + node_item* v;
5.261 + public:
5.262 + each_edge_iterator() : edge_iterator(), v(0) { }
5.263 + each_edge_iterator(node_item* _v, edge_item* _e) : edge_iterator(_e), v(_v) { }
5.264 + each_edge_iterator& operator++() {
5.265 + edge=edge->_next_out;
5.266 + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
5.267 + return *this;
5.268 + }
5.269 + };
5.270 +
5.271 + class out_edge_iterator : public edge_iterator {
5.272 + friend class list_graph;
5.273 + node_item* v;
5.274 + public:
5.275 + out_edge_iterator() : edge_iterator(), v(0) { }
5.276 + protected:
5.277 + out_edge_iterator(const node_iterator& _v) : v(_v.node) { edge=v->_first_out_edge; }
5.278 + public:
5.279 + out_edge_iterator& operator++() { edge=edge->_next_out; return *this; }
5.280 + protected:
5.281 + node_iterator a_node() const { return node_iterator(v); }
5.282 + node_iterator b_node() const {
5.283 + return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(v); }
5.284 + };
5.285 +
5.286 + class in_edge_iterator : public edge_iterator {
5.287 + friend class list_graph;
5.288 + node_item* v;
5.289 + public:
5.290 + in_edge_iterator() : edge_iterator(), v(0) { }
5.291 + protected:
5.292 + in_edge_iterator(const node_iterator& _v) : v(_v.node) {
5.293 + edge=v->_first_in_edge;
5.294 + }
5.295 + public:
5.296 + in_edge_iterator& operator++() { edge=edge->_next_in; return *this; }
5.297 + protected:
5.298 + node_iterator a_node() const { return node_iterator(v); }
5.299 + node_iterator b_node() const {
5.300 + return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(v); }
5.301 + };
5.302 +
5.303 + class sym_edge_iterator : public edge_iterator {
5.304 + friend class list_graph;
5.305 + bool out_or_in; //1 iff out, 0 iff in
5.306 + node_item* v;
5.307 + public:
5.308 + sym_edge_iterator() : edge_iterator(), v(0) { }
5.309 + protected:
5.310 + sym_edge_iterator(const node_iterator& _v) : v(_v.node) {
5.311 + out_or_in=1;
5.312 + edge=v->_first_out_edge;
5.313 + if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
5.314 + }
5.315 + public:
5.316 + sym_edge_iterator& operator++() {
5.317 + if (out_or_in) {
5.318 + edge=edge->_next_out;
5.319 + if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
5.320 + } else {
5.321 + edge=edge->_next_in;
5.322 + }
5.323 + return *this;
5.324 + }
5.325 + protected:
5.326 + node_iterator a_node() const { return node_iterator(v); }
5.327 + node_iterator b_node() const {
5.328 + return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(v); }
5.329 + };
5.330 +
5.331 + };
5.332 +
5.333 +
5.334 +
5.335 +} //namespace marci
5.336 +
5.337 +#endif //MARCI_LIST_GRAPH_HH
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/work/marci_makefile Tue Dec 30 13:59:08 2003 +0000
6.3 @@ -0,0 +1,5 @@
6.4 +CCFLAGS = -Wall -ansi
6.5 +CC = /opt/experimental/bin/g++
6.6 +
6.7 +marci_graph_demo: marci_graph_demo.cc marci_graph_traits.hh marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh
6.8 + $(CC) $(CCFLAGS) -I. marci_graph_demo.cc -o marci_graph_demo
6.9 \ No newline at end of file
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/work/marci_max_flow.hh Tue Dec 30 13:59:08 2003 +0000
7.3 @@ -0,0 +1,230 @@
7.4 +#ifndef MARCI_MAX_FLOW_HH
7.5 +#define MARCI_MAX_FLOW_HH
7.6 +
7.7 +#include <algorithm>
7.8 +
7.9 +#include <marci_graph_traits.hh>
7.10 +#include <marci_property_vector.hh>
7.11 +#include <marci_bfs.hh>
7.12 +
7.13 +namespace marci {
7.14 +
7.15 + template<typename graph_type, typename T>
7.16 + class res_graph_type {
7.17 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
7.18 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
7.19 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
7.20 + typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
7.21 +
7.22 + graph_type& G;
7.23 + edge_property_vector<graph_type, T>& flow;
7.24 + edge_property_vector<graph_type, T>& capacity;
7.25 + public:
7.26 + res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { }
7.27 +
7.28 + class res_edge_it {
7.29 + friend class res_graph_type<graph_type, T>;
7.30 + protected:
7.31 + res_graph_type<graph_type, T>* resG;
7.32 + sym_edge_iterator sym;
7.33 + public:
7.34 + res_edge_it() { }
7.35 + //bool is_free() {
7.36 + //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
7.37 + // return (resG->flow.get(sym)<resG->capacity.get(sym));
7.38 + //} else {
7.39 + // return (resG->flow.get(sym)>0);
7.40 + //}
7.41 + //}
7.42 + T free() {
7.43 + if (resG->G.a_node(sym)==resG->G.tail(sym)) {
7.44 + return (resG->capacity.get(sym)-resG->flow.get(sym));
7.45 + } else {
7.46 + return (resG->flow.get(sym));
7.47 + }
7.48 + }
7.49 + bool is_valid() { return sym.is_valid(); }
7.50 + void augment(T a) {
7.51 + if (resG->G.a_node(sym)==resG->G.tail(sym)) {
7.52 + resG->flow.put(sym, resG->flow.get(sym)+a);
7.53 + } else {
7.54 + resG->flow.put(sym, resG->flow.get(sym)-a);
7.55 + }
7.56 + }
7.57 + };
7.58 +
7.59 + class res_out_edge_it : public res_edge_it {
7.60 + public:
7.61 + res_out_edge_it() { }
7.62 + res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
7.63 + resG=&_resG;
7.64 + sym=resG->G.first_sym_edge(v);
7.65 + while( sym.is_valid() && !(free()>0) ) { ++sym; }
7.66 + }
7.67 + res_out_edge_it& operator++() {
7.68 + ++sym;
7.69 + while( sym.is_valid() && !(free()>0) ) { ++sym; }
7.70 + return *this;
7.71 + }
7.72 + };
7.73 +
7.74 + res_out_edge_it first_out_edge(const node_iterator& v) {
7.75 + return res_out_edge_it(*this, v);
7.76 + }
7.77 +
7.78 + each_node_iterator first_node() {
7.79 + return G.first_node();
7.80 + }
7.81 +
7.82 + node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
7.83 + node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
7.84 +
7.85 + int id(const node_iterator& v) { return G.id(v); }
7.86 +
7.87 + node_iterator invalid_node() { return G.invalid_node(); }
7.88 + res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
7.89 +
7.90 + };
7.91 +
7.92 + template <typename graph_type, typename T>
7.93 + struct graph_traits< res_graph_type<graph_type, T> > {
7.94 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
7.95 + typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
7.96 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
7.97 + typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
7.98 + };
7.99 +
7.100 + template <typename graph_type, typename pred_type, typename free_type>
7.101 + struct flow_visitor {
7.102 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
7.103 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
7.104 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
7.105 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
7.106 + graph_type& G;
7.107 + pred_type& pred;
7.108 + free_type& free;
7.109 + flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
7.110 + void at_previously_reached(out_edge_iterator& e) {
7.111 + //node_iterator v=G.tail(e);
7.112 + //node_iterator w=G.head(e);
7.113 + //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
7.114 + //std::cout<<std::endl;
7.115 + }
7.116 + void at_newly_reached(out_edge_iterator& e) {
7.117 + node_iterator v=G.tail(e);
7.118 + node_iterator w=G.head(e);
7.119 + //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
7.120 + pred.put(w, e);
7.121 + if (pred.get(v).is_valid()) {
7.122 + free.put(w, std::min(free.get(v), e.free()));
7.123 + //std::cout <<" nem elso csucs: ";
7.124 + //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
7.125 + } else {
7.126 + free.put(w, e.free());
7.127 + //std::cout <<" elso csucs: ";
7.128 + //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
7.129 + }
7.130 + //std::cout<<std::endl;
7.131 + }
7.132 + };
7.133 +
7.134 + template <typename graph_type, typename T>
7.135 + struct max_flow_type {
7.136 +
7.137 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
7.138 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
7.139 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
7.140 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
7.141 + typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
7.142 +
7.143 + graph_type& G;
7.144 + node_iterator s;
7.145 + node_iterator t;
7.146 + edge_property_vector<graph_type, T> flow;
7.147 + edge_property_vector<graph_type, T>& capacity;
7.148 +
7.149 + max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) {
7.150 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
7.151 + for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
7.152 + flow.put(j, 0);
7.153 + }
7.154 + void run() {
7.155 + typedef res_graph_type<graph_type, T> aug_graph_type;
7.156 + aug_graph_type res_graph(G, flow, capacity);
7.157 +
7.158 + typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
7.159 + bfs_queue_type bfs_queue;
7.160 + //bfs_queue.push(res_graph.first_out_edge(s));
7.161 +
7.162 + typedef node_property_vector<aug_graph_type, bool> reached_type;
7.163 + //reached_type reached(res_graph, false);
7.164 + reached_type reached(res_graph);
7.165 + //reached.put(s, true);
7.166 +
7.167 + typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
7.168 + pred_type pred(res_graph);
7.169 + pred.put(s, res_graph.invalid_edge());
7.170 +
7.171 + typedef node_property_vector<aug_graph_type, int> free_type;
7.172 + free_type free(res_graph);
7.173 +
7.174 + typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
7.175 + visitor_type vis(res_graph, pred, free);
7.176 +
7.177 + bfs_iterator< aug_graph_type, reached_type, visitor_type >
7.178 + res_bfs(res_graph, bfs_queue, reached, vis);
7.179 +
7.180 + //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) {
7.181 + //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
7.182 + // std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
7.183 + //}
7.184 + //}
7.185 + //std::cout<<std::endl;
7.186 +
7.187 + //char c;
7.188 + bool augment;
7.189 + do {
7.190 + augment=false;
7.191 +
7.192 + while (!bfs_queue.empty()) { bfs_queue.pop(); }
7.193 + bfs_queue.push(res_graph.first_out_edge(s));
7.194 +
7.195 + for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
7.196 + reached.put(s, true);
7.197 +
7.198 + //searching for augmenting path
7.199 + while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) {
7.200 + res_bfs.process();
7.201 + //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
7.202 + if (res_graph.head(res_bfs)==t) break;
7.203 + //res_bfs.next();
7.204 + ++res_bfs;
7.205 + }
7.206 + //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); }
7.207 + if (reached.get(t)) {
7.208 + augment=true;
7.209 + node_iterator n=t;
7.210 + T augment_value=free.get(t);
7.211 + std::cout<<"augmentation: ";
7.212 + while (pred.get(n).is_valid()) {
7.213 + graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
7.214 + e.augment(augment_value);
7.215 + std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
7.216 + n=res_graph.tail(e);
7.217 + }
7.218 + std::cout<<std::endl;
7.219 + }
7.220 +
7.221 + std::cout << "max flow:"<< std::endl;
7.222 + for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
7.223 + std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
7.224 + }
7.225 + std::cout<<std::endl;
7.226 +
7.227 + } while (augment);
7.228 + }
7.229 + };
7.230 +
7.231 +} // namespace marci
7.232 +
7.233 +#endif //MARCI_MAX_FLOW_HH
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/work/marci_property_vector.hh Tue Dec 30 13:59:08 2003 +0000
8.3 @@ -0,0 +1,59 @@
8.4 +#ifndef MARCI_PROPERTY_VECTOR_HH
8.5 +#define MARCI_PROPERTY_VECTOR_HH
8.6 +
8.7 +#include <vector>
8.8 +
8.9 +#include <marci_graph_traits.hh>
8.10 +
8.11 +namespace marci {
8.12 +
8.13 + template <typename iterator>
8.14 + int number_of(iterator _it) {
8.15 + int i=0;
8.16 + for( ; _it.is_valid(); ++_it) { ++i; }
8.17 + return i;
8.18 + }
8.19 +
8.20 + template <typename graph_type, typename T>
8.21 + class node_property_vector {
8.22 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
8.23 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
8.24 + graph_type& G;
8.25 + std::vector<T> container;
8.26 + public:
8.27 + node_property_vector(graph_type& _G) : G(_G) {
8.28 + int i=0;
8.29 + for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) ++i;
8.30 + container.resize(i);
8.31 + }
8.32 + node_property_vector(graph_type& _G, T a) : G(_G) {
8.33 + for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) { container.push_back(a); }
8.34 + }
8.35 + void put(node_iterator nit, const T& a) { container[G.id(nit)]=a; }
8.36 + T get(node_iterator nit) { return container[G.id(nit)]; }
8.37 + };
8.38 +
8.39 + template <typename graph_type, typename T>
8.40 + class edge_property_vector {
8.41 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
8.42 + typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
8.43 + graph_type& G;
8.44 + std::vector<T> container;
8.45 + public:
8.46 + edge_property_vector(graph_type& _G) : G(_G) {
8.47 + int i=0;
8.48 + for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) ++i;
8.49 + container.resize(i);
8.50 + }
8.51 + edge_property_vector(graph_type& _G, T a) : G(_G) {
8.52 + for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) {
8.53 + container.push_back(a);
8.54 + }
8.55 + }
8.56 + void put(edge_iterator eit, const T& a) { container[G.id(eit)]=a; }
8.57 + T get(edge_iterator eit) { return container[G.id(eit)]; }
8.58 + };
8.59 +
8.60 +} // namespace marci
8.61 +
8.62 +#endif //MARCI_PROPERTY_VECTOR_HH