1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/athos/dijkstra_at.h Fri Mar 26 14:59:18 2004 +0000
1.3 @@ -0,0 +1,123 @@
1.4 +/*
1.5 +Egy pontból összes többibe vezető legrövidebb utak irányított gráfban
1.6 +
1.7 +Preconditions:
1.8 +A gráf típus tud:
1.9 +- pontból kimenő éleket sorban visszaadni
1.10 +A T számtípus, ami tud összehasonlítást, összedást
1.11 +A bemenetre:
1.12 +weight nemnegatív
1.13 +
1.14 +*/
1.15 +#ifndef DIJKSTRA_AT_H
1.16 +#define DIJKSTRA_AT_H
1.17 +
1.18 +
1.19 +
1.20 +//#include <algorithm>
1.21 +//#include <deque>
1.22 +//#include <vector>
1.23 +//#include "pf_hiba.hh"
1.24 +//#include <marci_list_graph.hh>
1.25 +//#include <marci_graph_traits.hh>
1.26 +
1.27 +
1.28 +using namespace std;
1.29 +
1.30 +namespace hugo {
1.31 +
1.32 + template <typename graph_type, typename T>
1.33 + class dijkstra_at {
1.34 +
1.35 + //Hasznos typedef-ek
1.36 + typedef typename graph_type::NodeIt NodeIt;
1.37 + typedef typename graph_type::EdgeIt EdgeIt;
1.38 + typedef typename graph_type::EachNodeIt EachNodeIt;
1.39 + typedef typename graph_type::EachEdgeIt EachEdgeIt;
1.40 + typedef typename graph_type::OutEdgeIt OutEdgeIt;
1.41 + typedef typename graph_type::InEdgeIt InEdgeIt;
1.42 + typedef typename graph_type::SymEdgeIt SymEdgeIt;
1.43 +
1.44 +
1.45 +
1.46 + //---------------------------------------------
1.47 + //Parameters of the algorithm
1.48 + //---------------------------------------------
1.49 +
1.50 + //---------------------------------------------
1.51 + //Parameters of the algorithm
1.52 + //---------------------------------------------
1.53 +
1.54 + private:
1.55 + //input
1.56 + graph_type& G;
1.57 + NodeIt s;
1.58 + typename graph_type::EdgeMap<T> &weight;
1.59 + //typename graph_type::EdgeMap<T> &capacity;
1.60 + //output
1.61 + //typename graph_type::EdgeMap<T>
1.62 + // typename graph_type::EdgeMap<T> preflow;
1.63 +
1.64 + //auxiliary variables for computation
1.65 + deque<NodeIt> next_to_reach;
1.66 +
1.67 +
1.68 + typename graph_type::NodeMap<bool> reached;
1.69 +
1.70 + //Variables holding output
1.71 + //Predessors in the shortest paths arborescence
1.72 + typename graph_type::NodeMap<NodeIt> pred;
1.73 +
1.74 +
1.75 + public:
1.76 +
1.77 +
1.78 + dijkstra_at(
1.79 + graph_type& _G,
1.80 + NodeIt _s,
1.81 + typename graph_type::EdgeMap<T> & _weight)
1.82 + : G(_G), s(_s),
1.83 + weight(_weight),
1.84 + next_to_reach(),
1.85 + reached(_G),
1.86 + pred(G)
1.87 +
1.88 + {
1.89 + }
1.90 + /*By Misi.*/
1.91 + struct Node_dist_comp
1.92 + {
1.93 + NodeMap<graph_type, T> &d;
1.94 + Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {}
1.95 +
1.96 + bool operator()(const NodeIt& u, const NodeIt& v) const
1.97 + { return d.get(u) < d.get(v); }
1.98 + };
1.99 +
1.100 +
1.101 +
1.102 + void run() {
1.103 +
1.104 + NodeMap<graph_type, bool> scanned(G, false);
1.105 + std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp>
1.106 + heap(( Node_dist_comp(distance) ));
1.107 +
1.108 + heap.push(s);
1.109 + reached.set(s, true);
1.110 +
1.111 + }
1.112 +
1.113 +
1.114 + };
1.115 +
1.116 +
1.117 +
1.118 +
1.119 +
1.120 +
1.121 + }; //class dijkstra_at
1.122 +
1.123 +
1.124 +}//namespace hugo
1.125 +
1.126 +#endif //DIJKSTRA_AT
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/athos/dijkstra_demo.cc Fri Mar 26 14:59:18 2004 +0000
2.3 @@ -0,0 +1,160 @@
2.4 +#include <iostream>
2.5 +#include <string>
2.6 +
2.7 +#include "list_graph.hh"
2.8 +//#include "marci_property_vector.hh"
2.9 +#include <dijkstra_at.h>
2.10 +
2.11 +using namespace hugo;
2.12 +
2.13 +
2.14 +int main (int, char*[])
2.15 +{
2.16 +
2.17 +
2.18 + typedef ListGraph::NodeIt NodeIt;
2.19 + typedef ListGraph::EdgeIt EdgeIt;
2.20 + /*
2.21 + typedef ListGraph::EachNodeIt EachNodeIt;
2.22 + typedef ListGraph::EachEdgeIt EachEdgeIt;
2.23 + typedef ListGraph::OutEdgeIt OutEdgeIt;
2.24 + typedef ListGraph::InEdgeIt InEdgeIt;
2.25 + typedef ListGraph::SymEdgeIt SymEdgeIt;
2.26 + */
2.27 + ListGraph flowG;
2.28 +
2.29 + /*
2.30 + //Marci példája
2.31 +
2.32 +
2.33 + NodeIt s=flowG.addNode();
2.34 + NodeIt v1=flowG.addNode();
2.35 + NodeIt v2=flowG.addNode();
2.36 + NodeIt v3=flowG.addNode();
2.37 + NodeIt v4=flowG.addNode();
2.38 + NodeIt t=flowG.addNode();
2.39 +
2.40 +
2.41 + EdgeIt s_v1=flowG.addEdge(s, v1);
2.42 + EdgeIt s_v2=flowG.addEdge(s, v2);
2.43 + EdgeIt v1_v2=flowG.addEdge(v1, v2);
2.44 + EdgeIt v2_v1=flowG.addEdge(v2, v1);
2.45 + EdgeIt v1_v3=flowG.addEdge(v1, v3);
2.46 + EdgeIt v3_v2=flowG.addEdge(v3, v2);
2.47 + EdgeIt v2_v4=flowG.addEdge(v2, v4);
2.48 + EdgeIt v4_v3=flowG.addEdge(v4, v3);
2.49 + EdgeIt v3_t=flowG.addEdge(v3, t);
2.50 + EdgeIt v4_t=flowG.addEdge(v4, t);
2.51 +
2.52 + ListGraph::EdgeMap<int> cap(flowG);
2.53 +
2.54 + cap.set(s_v1, 16);
2.55 + cap.set(s_v2, 13);
2.56 + cap.set(v1_v2, 10);
2.57 + cap.set(v2_v1, 4);
2.58 + cap.set(v1_v3, 12);
2.59 + cap.set(v3_v2, 9);
2.60 + cap.set(v2_v4, 14);
2.61 + cap.set(v4_v3, 7);
2.62 + cap.set(v3_t, 20);
2.63 + cap.set(v4_t, 4);
2.64 + */
2.65 +
2.66 +
2.67 + //Ahuja könyv példája
2.68 +
2.69 + NodeIt s=flowG.addNode();
2.70 + NodeIt v2=flowG.addNode();
2.71 + NodeIt v3=flowG.addNode();
2.72 + NodeIt v4=flowG.addNode();
2.73 + NodeIt v5=flowG.addNode();
2.74 + NodeIt t=flowG.addNode();
2.75 +
2.76 + EdgeIt s_v2=flowG.addEdge(s, v2);
2.77 + EdgeIt s_v3=flowG.addEdge(s, v3);
2.78 + EdgeIt v2_v4=flowG.addEdge(v2, v4);
2.79 + EdgeIt v2_v5=flowG.addEdge(v2, v5);
2.80 + EdgeIt v3_v5=flowG.addEdge(v3, v5);
2.81 + EdgeIt v4_t=flowG.addEdge(v4, t);
2.82 + EdgeIt v5_t=flowG.addEdge(v5, t);
2.83 +
2.84 + //Kis modositas
2.85 + //edge_iterator v2_s=flowG.add_edge(v2, s);
2.86 +
2.87 + ListGraph::EdgeMap<int> cap(flowG);
2.88 +
2.89 + cap.set(s_v2, 10);
2.90 + cap.set(s_v3, 10);
2.91 + cap.set(v2_v4, 5);
2.92 + cap.set(v2_v5, 8);
2.93 + cap.set(v3_v5, 5);
2.94 + cap.set(v4_t, 8);
2.95 + cap.set(v5_t, 8);
2.96 +
2.97 + //Kis modositas
2.98 + //cap.put(v2_s, 100);
2.99 +
2.100 +
2.101 +
2.102 +
2.103 + /*Egyszerű példa
2.104 + NodeIt s=flow_test.add_node();
2.105 + NodeIt v1=flow_test.add_node();
2.106 + NodeIt v2=flow_test.add_node();
2.107 + NodeIt t=flow_test.add_node();
2.108 +
2.109 + node_property_vector<list_graph, std::string> node_name(flow_test);
2.110 + node_name.put(s, "s");
2.111 + node_name.put(v1, "v1");
2.112 + node_name.put(v2, "v2");
2.113 + node_name.put(t, "t");
2.114 +
2.115 + edge_iterator s_v1=flow_test.add_edge(s, v1);
2.116 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
2.117 + edge_iterator v2_t=flow_test.add_edge(v2, t);
2.118 +
2.119 + edge_property_vector<list_graph, int> cap(flow_test);
2.120 +
2.121 + cap.put(s_v1, 16);
2.122 + cap.put(v1_v2, 10);
2.123 + cap.put(v2_t, 4);
2.124 + */
2.125 +
2.126 + std::cout << "preflow-push algorithm test..." << std::endl;
2.127 +
2.128 + /*
2.129 + std::cout << "on directed graph graph" << std::endl; //<< flow_test;
2.130 + std::cout << "names and capacity values" << std::endl;
2.131 + for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
2.132 + std::cout << node_name.get(i) << ": ";
2.133 + std::cout << "out edges: ";
2.134 + for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
2.135 + std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
2.136 + std::cout << "in edges: ";
2.137 + for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
2.138 + std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
2.139 + std::cout << std::endl;
2.140 + }
2.141 + */
2.142 +
2.143 + //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
2.144 + // std::cout << i << " ";
2.145 + //}
2.146 +
2.147 + dijkstra_at<ListGraph, int> dijkstra_test(flowG, s, cap);
2.148 + //cout << preflow_push_test.run()<<endl;
2.149 +
2.150 + //cap.put(v5_t, 9);
2.151 + //cout << preflow_push_test.run()<<endl;
2.152 +
2.153 + return 0;
2.154 +}
2.155 +
2.156 +
2.157 +
2.158 +
2.159 +
2.160 +
2.161 +
2.162 +
2.163 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/athos/kruskal.h Fri Mar 26 14:59:18 2004 +0000
3.3 @@ -0,0 +1,61 @@
3.4 +/*
3.5 +Kruskal's algorithm to find a spanning tree of minimum weight
3.6 +If the graph is not connected, it gives a forest.
3.7 +*/
3.8 +#ifndef KRUSKAL_H
3.9 +#define KRUSKAL_H
3.10 +
3.11 +#include <union_find.h>
3.12 +
3.13 +namespace hugo {
3.14 +
3.15 + template <typename graph_type, typename T>
3.16 + class Kruskal {
3.17 +
3.18 +
3.19 + //Hasznos typedef-ek
3.20 + typedef typename graph_type::NodeIt NodeIt;
3.21 + typedef typename graph_type::EdgeIt EdgeIt;
3.22 + typedef typename graph_type::EachNodeIt EachNodeIt;
3.23 + typedef typename graph_type::EachEdgeIt EachEdgeIt;
3.24 + typedef typename graph_type::SymEdgeIt SymEdgeIt;
3.25 +
3.26 + //input
3.27 + graph_type& G;
3.28 + typename graph_type::EdgeMap<T> &weight;
3.29 +
3.30 + //Auxilliary variables
3.31 + typename graph_type::NodeMap<int> component(flowG);
3.32 +
3.33 + Kruskal(
3.34 + graph_type& _G,
3.35 + typename graph_type::EdgeMap<T> & _weight)
3.36 + : G(_G),
3.37 + weight(_weight),
3.38 + component(-1)
3.39 + {
3.40 + }
3.41 +
3.42 + /*Originally by Misi.*/
3.43 + struct Edge_comp
3.44 + {
3.45 + NodeMap<graph_type, T> &d;
3.46 + Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {}
3.47 +
3.48 + bool operator()(const NodeIt& u, const NodeIt& v) const
3.49 + { return d.get(u) < d.get(v); }
3.50 + };
3.51 +
3.52 +
3.53 + //Runs the algorithm
3.54 + void run() {
3.55 +
3.56 +
3.57 +
3.58 + }
3.59 +
3.60 + }
3.61 +
3.62 +}//namespacc hugo
3.63 +
3.64 +#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/athos/uf_demo.cc Fri Mar 26 14:59:18 2004 +0000
4.3 @@ -0,0 +1,48 @@
4.4 +//This is just a simple example program to test my union-find structure
4.5 +
4.6 +//#include <marciMap.hh>
4.7 +#include <union_find.h>
4.8 +#include <iostream>
4.9 +#include <list_graph.hh>
4.10 +using namespace hugo;
4.11 +using namespace std;
4.12 +
4.13 +int main (int, char*[])
4.14 +{
4.15 + typedef ListGraph::NodeIt NodeIt;
4.16 + typedef ListGraph::EachNodeIt EachNodeIt;
4.17 + typedef ListGraph::EdgeIt EdgeIt;
4.18 +
4.19 + ListGraph flowG;
4.20 +
4.21 +
4.22 + //Marci példája
4.23 +
4.24 +
4.25 +
4.26 + NodeIt s=flowG.addNode();
4.27 + NodeIt v1=flowG.addNode();
4.28 + NodeIt v2=flowG.addNode();
4.29 + NodeIt v3=flowG.addNode();
4.30 + NodeIt v4=flowG.addNode();
4.31 + NodeIt t=flowG.addNode();
4.32 +
4.33 + ListGraph::NodeMap<int> component(flowG);
4.34 +
4.35 + component.set(s, -1);
4.36 + component.set(v1, -1);
4.37 + component.set(v2, -1);
4.38 + component.set(v3, -1);
4.39 + component.set(v4, -1);
4.40 + component.set(t, -1);
4.41 +
4.42 + UnionFind< NodeIt, ListGraph::NodeMap<int> > uf(component);
4.43 + cout<<"Merge s and v1: "<<uf.findAndMerge(s,v1)<<endl;
4.44 + cout<<"Merge s and v1: "<<uf.findAndMerge(s,v1)<<endl;
4.45 + cout<<"Merge s and v2: "<<uf.findAndMerge(s,v3)<<endl;
4.46 + for(EachNodeIt i=flowG.template first<EachNodeIt>(); i.valid(); ++i) {
4.47 +
4.48 + cout<<"Az "<<flowG.id(i)<<". pont itt van: "<<uf.find(i)<<endl;
4.49 + //std::cout << node_name.get(i) << ": ";
4.50 + }
4.51 +}
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/athos/union_find.h Fri Mar 26 14:59:18 2004 +0000
5.3 @@ -0,0 +1,94 @@
5.4 +// -*- C++ -*- //
5.5 +/*
5.6 +Union-Find structure
5.7 +
5.8 +* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
5.9 +* minden szobajovo kulcs ertekre, -1 -es ertekkel!
5.10 +
5.11 +*/
5.12 +#ifndef UNION_FIND_H
5.13 +#define UNION_FIND_H
5.14 +
5.15 +#include <vector>
5.16 +//#include <map>
5.17 +
5.18 +
5.19 +namespace hugo {
5.20 +
5.21 + template <typename KeyType, typename KeyIntMap>
5.22 + class UnionFind {
5.23 + KeyIntMap& pointmap;
5.24 + struct VectorElementType {
5.25 + int boss;
5.26 + int count;
5.27 + VectorElementType(int _boss, int _count){
5.28 + boss = _boss;
5.29 + count = _count;
5.30 + }
5.31 + };
5.32 + std::vector<VectorElementType> container;
5.33 + public:
5.34 +
5.35 + UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){
5.36 +
5.37 + }
5.38 +
5.39 + //Give a component of one point to the structure
5.40 + int addPoint(KeyType u){
5.41 + int _index = container.size();
5.42 + VectorElementType buf(_index,1);
5.43 + container.push_back(buf);
5.44 + return _index;
5.45 + }
5.46 +
5.47 +
5.48 + //Finds the big boss of u
5.49 + int find(KeyType u){
5.50 + if (pointmap.get(u)==-1){
5.51 + int whoami = addPoint(u);
5.52 + pointmap.set(u, whoami);
5.53 + return whoami;
5.54 + }
5.55 + else{
5.56 + int emp = pointmap.get(u);
5.57 + int boss = container[emp].boss;
5.58 + while(emp != boss){
5.59 + emp = boss;
5.60 + boss = container[emp].boss;
5.61 + }
5.62 + return boss;
5.63 + }
5.64 + }
5.65 +
5.66 + //Finds u and v in the structures and merges the comopnents, if not equal
5.67 + bool findAndMerge(KeyType u,KeyType v){
5.68 + int bu = find(u);
5.69 + int bv = find(v);
5.70 + if (bu != bv){
5.71 + unio(bu,bv);
5.72 + return true;
5.73 + }
5.74 + else{
5.75 + return false;
5.76 + }
5.77 + }
5.78 +
5.79 + //Merges a into b
5.80 + void mergeInto(int a, int b){
5.81 + container[a].boss = b;
5.82 + container[b].count += container[a].count;
5.83 + }
5.84 +
5.85 + //Makes the union
5.86 + void unio(int b1, int b2){
5.87 + if (container[b1].count>container[b2].count){
5.88 + mergeInto(b2,b1);
5.89 + }
5.90 + else{
5.91 + mergeInto(b1,b2);
5.92 + }
5.93 + }//unio
5.94 + };
5.95 +
5.96 +}//namespace hugo
5.97 +#endif