1.1 --- a/src/work/klao/Makefile	Sat Apr 17 01:50:23 2004 +0000
     1.2 +++ b/src/work/klao/Makefile	Sat Apr 17 01:57:48 2004 +0000
     1.3 @@ -1,4 +1,4 @@
     1.4 -BINARIES = path_test map_test minlengthpaths
     1.5 +BINARIES = path_test map_test iter_map_test
     1.6  INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos}
     1.7  include ../makefile
     1.8  

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/klao/iter_map.h	Sat Apr 17 01:57:48 2004 +0000
     2.3 @@ -0,0 +1,121 @@
     2.4 +// -*- c++ -*- //
     2.5 +
     2.6 +#ifndef HUGO_ITER_MAP
     2.7 +#define HUGO_ITER_MAP
     2.8 +
     2.9 +#include <vector>
    2.10 +#include <algorithm>
    2.11 +// for uint8_t
    2.12 +#include <stdint.h>
    2.13 +// for memset
    2.14 +#include <cstring>
    2.15 +
    2.16 +
    2.17 +namespace hugo {
    2.18 +
    2.19 +
    2.20 +  /// \todo Decide whether we need all the range checkings!!!
    2.21 +
    2.22 +  template<typename KeyIntMap, uint8_t N>
    2.23 +  class IterableMap {
    2.24 +  public:
    2.25 +
    2.26 +    typedef typename KeyIntMap::KeyType KeyType;
    2.27 +    typedef uint8_t ValueType;
    2.28 +
    2.29 +    typedef typename std::vector<KeyType>::const_iterator iterator;
    2.30 +
    2.31 +  protected:
    2.32 +    KeyIntMap &base;
    2.33 +    std::vector<KeyType> data;
    2.34 +    size_t bounds[N];
    2.35 +
    2.36 +    uint8_t find(size_t a) const {
    2.37 +      uint8_t n=0;
    2.38 +      for(; n<N && bounds[n]<=a; ++n);
    2.39 +      return n;
    2.40 +    }
    2.41 +
    2.42 +    void half_swap(size_t &a, size_t b) {
    2.43 +      if(a != b) {
    2.44 +	base.set(data[b],a);
    2.45 +	data[a] = data[b];
    2.46 +	a = b;
    2.47 +      }
    2.48 +    }
    2.49 +
    2.50 +    size_t move(size_t a, uint8_t m, uint8_t n) {
    2.51 +      if(m != n) {
    2.52 +	size_t orig_a = a;
    2.53 +	KeyType orig_key = data[a];
    2.54 +	while(m > n) {
    2.55 +	  --m;
    2.56 +	  half_swap(a, bounds[m]++);
    2.57 +	}
    2.58 +	while(m < n) {
    2.59 +	  half_swap(a, --bounds[m]);
    2.60 +	  ++m;
    2.61 +	}
    2.62 +	if(a != orig_a) {
    2.63 +	  base.set(orig_key, a);
    2.64 +	  data[a]=orig_key;
    2.65 +	}
    2.66 +      }
    2.67 +      return a;
    2.68 +    }
    2.69 +
    2.70 +  public:
    2.71 +    
    2.72 +    IterableMap(KeyIntMap &_base) : base(_base) {
    2.73 +      memset(bounds, 0, sizeof(bounds));
    2.74 +      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
    2.75 +    }
    2.76 +
    2.77 +    uint8_t operator[](const KeyType& k) const {
    2.78 +      return find(base[k]);
    2.79 +    }
    2.80 +
    2.81 +    void set(const KeyType& k, uint8_t n) {
    2.82 +      size_t a = base[k];
    2.83 +      if(a < bounds[N-1]) {
    2.84 +	base.set(k, move(a, find(a), n));
    2.85 +      }
    2.86 +    }
    2.87 +
    2.88 +    void insert(const KeyType& k, uint8_t n) {
    2.89 +      if(n<N) {
    2.90 +	data.push_back(k);
    2.91 +	base.set(k, move(bounds[N-1]++, N-1, n));
    2.92 +      }
    2.93 +    }
    2.94 +
    2.95 +    iterator begin(uint8_t n) const {
    2.96 +      if(n < N)
    2.97 +	return data.begin() + (n ? bounds[n-1] : 0);
    2.98 +      else
    2.99 +	return data.end();
   2.100 +    }
   2.101 +
   2.102 +    iterator end(uint8_t n) const {
   2.103 +      if(n < N)
   2.104 +	return data.begin() + bounds[n];
   2.105 +      else
   2.106 +	return data.end();
   2.107 +    }
   2.108 +
   2.109 +    size_t size(uint8_t n) const {
   2.110 +      if(n < N)
   2.111 +	return bounds[n] - (n ? bounds[n-1] : 0);
   2.112 +      else
   2.113 +	return 0;
   2.114 +    }
   2.115 +    
   2.116 +    size_t size() const {
   2.117 +      // assert(bounds[N-1] == data.size());
   2.118 +      return bounds[N-1];
   2.119 +    }
   2.120 +
   2.121 +  };
   2.122 +
   2.123 +}
   2.124 +#endif

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/work/klao/iter_map_test.cc	Sat Apr 17 01:57:48 2004 +0000
     3.3 @@ -0,0 +1,117 @@
     3.4 +#include <iter_map.h>
     3.5 +#include <maps.h>
     3.6 +
     3.7 +#include <iostream>
     3.8 +
     3.9 +using namespace hugo;
    3.10 +using namespace std;
    3.11 +
    3.12 +const int N = 3;
    3.13 +
    3.14 +typedef StdMap<int,int> BaseMap;
    3.15 +typedef IterableMap<BaseMap, N> TestMap;
    3.16 +
    3.17 +
    3.18 +void print(TestMap const& m) {
    3.19 +  cout << "Size of the map: " << m.size() << endl;
    3.20 +  for(int i=0; i<N; ++i) {
    3.21 +    cout << "  Class " << i << ". (size=" << m.size(i) << "): " << flush;
    3.22 +    cout << "    ";
    3.23 +    for(TestMap::iterator j = m.begin(i); j!=m.end(i); ++j) {
    3.24 +      cout << " " << *j;
    3.25 +    }
    3.26 +    cout << endl;
    3.27 +  }
    3.28 +}
    3.29 +
    3.30 +
    3.31 +
    3.32 +int main() {
    3.33 +
    3.34 +  BaseMap base(344);
    3.35 +  TestMap test(base);
    3.36 +
    3.37 +
    3.38 +  print(test);
    3.39 +
    3.40 +  cout << "Inserting 12 to class 2...\n";
    3.41 +  test.insert(12,2);
    3.42 +  print(test);
    3.43 +
    3.44 +
    3.45 +  cout << "Inserting 22 to class 2...\n";
    3.46 +  test.insert(22,2);
    3.47 +  print(test);
    3.48 +
    3.49 +  cout << "Testing some map values:\n";
    3.50 +  cout << " 12: " << int(test[12]) << endl;
    3.51 +
    3.52 +  cout << "Inserting 10 to class 0...\n";
    3.53 +  test.insert(10,0);
    3.54 +  print(test);
    3.55 +
    3.56 +  cout << "Testing some map values:\n";
    3.57 +  cout << " 12: " << int(test[12]) << endl;
    3.58 +
    3.59 +  cout << "Inserting 11 to class 1...\n";
    3.60 +  test.insert(11,1);
    3.61 +  print(test);
    3.62 +
    3.63 +  cout << "Testing some map values:\n";
    3.64 +  cout << " 12: " << int(test[12]) << endl;
    3.65 +  cout << " 22: " << int(test[22]) << endl;
    3.66 +  cout << " 10: " << int(test[10]) << endl;
    3.67 +  cout << " 11: " << int(test[11]) << endl;
    3.68 +  cout << " 42: " << int(test[42]) << endl;
    3.69 +
    3.70 +  cout << "Inserting 21 to class 1...\n";
    3.71 +  test.insert(21,1);
    3.72 +  print(test);
    3.73 +
    3.74 +  cout << "Inserting 20 to class 1...\n";
    3.75 +  test.insert(20,0);
    3.76 +  print(test);
    3.77 +
    3.78 +  cout << "Testing some map values:\n";
    3.79 +  cout << " 12: " << int(test[12]) << endl;
    3.80 +  cout << " 22: " << int(test[22]) << endl;
    3.81 +  cout << " 10: " << int(test[10]) << endl;
    3.82 +  cout << " 20: " << int(test[20]) << endl;
    3.83 +  cout << " 11: " << int(test[11]) << endl;
    3.84 +  cout << " 21: " << int(test[21]) << endl;
    3.85 +  cout << " 42: " << int(test[42]) << endl;
    3.86 +
    3.87 +  cout << "Setting 20 to class 2...\n";
    3.88 +  test.set(20,2);
    3.89 +  print(test);
    3.90 +  
    3.91 +  cout << "Setting 10 to class 1...\n";
    3.92 +  test.set(10,1);
    3.93 +  print(test);
    3.94 +  
    3.95 +  cout << "Setting 11 to class 1...\n";
    3.96 +  test.set(11,1);
    3.97 +  print(test);
    3.98 +  
    3.99 +  cout << "Setting 12 to class 1...\n";
   3.100 +  test.set(12,1);
   3.101 +  print(test);
   3.102 +  
   3.103 +  cout << "Setting 21 to class 2...\n";
   3.104 +  test.set(21,2);
   3.105 +  print(test);
   3.106 +  
   3.107 +  cout << "Setting 22 to class 2...\n";
   3.108 +  test.set(22,2);
   3.109 +  print(test);
   3.110 +  
   3.111 +  cout << "Testing some map values:\n";
   3.112 +  cout << " 12: " << int(test[12]) << endl;
   3.113 +  cout << " 22: " << int(test[22]) << endl;
   3.114 +  cout << " 10: " << int(test[10]) << endl;
   3.115 +  cout << " 20: " << int(test[20]) << endl;
   3.116 +  cout << " 11: " << int(test[11]) << endl;
   3.117 +  cout << " 21: " << int(test[21]) << endl;
   3.118 +  cout << " 42: " << int(test[42]) << endl;
   3.119 +
   3.120 +}

     4.1 --- a/src/work/klao/minlengthpaths.cc	Sat Apr 17 01:50:23 2004 +0000
     4.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.3 @@ -1,127 +0,0 @@
     4.4 -// -*- c++ -*-
     4.5 -//#include <iostream>
     4.6 -//#include <vector>
     4.7 -//#include <string>
     4.8 -
     4.9 -#include <list_graph.h>
    4.10 -#include <minlengthpaths.h>
    4.11 -
    4.12 -using namespace hugo;
    4.13 -
    4.14 -
    4.15 -int main()
    4.16 -{
    4.17 -
    4.18 -  
    4.19 -  typedef ListGraph::Node Node;
    4.20 -  typedef ListGraph::Edge Edge;
    4.21 -
    4.22 -  ListGraph graph;
    4.23 -
    4.24 -  /*
    4.25 -  //Marci példája
    4.26 -
    4.27 -
    4.28 -  NodeIt s=graph.addNode();
    4.29 -  NodeIt v1=graph.addNode();
    4.30 -  NodeIt v2=graph.addNode();
    4.31 -  NodeIt v3=graph.addNode();
    4.32 -  NodeIt v4=graph.addNode();
    4.33 -  NodeIt t=graph.addNode();
    4.34 -  
    4.35 -
    4.36 -  EdgeIt s_v1=graph.addEdge(s, v1);
    4.37 -  EdgeIt s_v2=graph.addEdge(s, v2);
    4.38 -  EdgeIt v1_v2=graph.addEdge(v1, v2);
    4.39 -  EdgeIt v2_v1=graph.addEdge(v2, v1);
    4.40 -  EdgeIt v1_v3=graph.addEdge(v1, v3);
    4.41 -  EdgeIt v3_v2=graph.addEdge(v3, v2);
    4.42 -  EdgeIt v2_v4=graph.addEdge(v2, v4);
    4.43 -  EdgeIt v4_v3=graph.addEdge(v4, v3);
    4.44 -  EdgeIt v3_t=graph.addEdge(v3, t);
    4.45 -  EdgeIt v4_t=graph.addEdge(v4, t);
    4.46 -
    4.47 -  ListGraph::EdgeMap<int> length(graph);
    4.48 -
    4.49 -  length.set(s_v1, 16);
    4.50 -  length.set(s_v2, 13);
    4.51 -  length.set(v1_v2, 10);
    4.52 -  length.set(v2_v1, 4);
    4.53 -  length.set(v1_v3, 12);
    4.54 -  length.set(v3_v2, 9);
    4.55 -  length.set(v2_v4, 14);
    4.56 -  length.set(v4_v3, 7);
    4.57 -  length.set(v3_t, 20);
    4.58 -  length.set(v4_t, 4);
    4.59 -  */
    4.60 -
    4.61 -
    4.62 -  //Ahuja könyv példája
    4.63 -
    4.64 -  Node s=graph.addNode();
    4.65 -  Node v2=graph.addNode();
    4.66 -  Node v3=graph.addNode();
    4.67 -  Node v4=graph.addNode();
    4.68 -  Node v5=graph.addNode();
    4.69 -  Node t=graph.addNode();
    4.70 -
    4.71 -  Edge s_v2=graph.addEdge(s, v2);
    4.72 -  Edge s_v3=graph.addEdge(s, v3);
    4.73 -  Edge v2_v4=graph.addEdge(v2, v4);
    4.74 -  Edge v2_v5=graph.addEdge(v2, v5);
    4.75 -  Edge v3_v5=graph.addEdge(v3, v5);
    4.76 -  Edge v4_t=graph.addEdge(v4, t);
    4.77 -  Edge v5_t=graph.addEdge(v5, t);
    4.78 -  
    4.79 -  //Kis modositas
    4.80 -  //edge_iterator v2_s=graph.add_edge(v2, s);
    4.81 -
    4.82 -  ListGraph::EdgeMap<int> length(graph);
    4.83 -
    4.84 -  length.set(s_v2, 10);
    4.85 -  length.set(s_v3, 10);
    4.86 -  length.set(v2_v4, 5);
    4.87 -  length.set(v2_v5, 8);
    4.88 -  length.set(v3_v5, 5);
    4.89 -  length.set(v4_t, 8);
    4.90 -  length.set(v5_t, 8);
    4.91 -
    4.92 -  //Kis modositas
    4.93 -  //length.put(v2_s, 100);
    4.94 - 
    4.95 -
    4.96 -
    4.97 -
    4.98 -  /*Egyszerű példa
    4.99 -  NodeIt s=flow_test.add_node();
   4.100 -  NodeIt v1=flow_test.add_node();
   4.101 -  NodeIt v2=flow_test.add_node();
   4.102 -  NodeIt t=flow_test.add_node();
   4.103 -  
   4.104 -  node_property_vector<list_graph, std::string> node_name(flow_test);
   4.105 -  node_name.put(s, "s");
   4.106 -  node_name.put(v1, "v1");
   4.107 -  node_name.put(v2, "v2");
   4.108 -  node_name.put(t, "t");
   4.109 -
   4.110 -  edge_iterator s_v1=flow_test.add_edge(s, v1);
   4.111 -  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
   4.112 -  edge_iterator v2_t=flow_test.add_edge(v2, t);
   4.113 -
   4.114 -  edge_property_vector<list_graph, int> length(flow_test); 
   4.115 -    
   4.116 -  length.put(s_v1, 16);
   4.117 -  length.put(v1_v2, 10);
   4.118 -  length.put(v2_t, 4);
   4.119 -  */
   4.120 -
   4.121 -  std::cout << "Suurballe algorithm test..." << std::endl;
   4.122 -
   4.123 -  
   4.124 -  int k=3;
   4.125 -  MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
   4.126 -    surb_test(graph, length);
   4.127 -  std::cout << surb_test.run(s,t,k) << std::endl;
   4.128 -
   4.129 -  return 0;
   4.130 -}

     5.1 --- a/src/work/klao/minlengthpaths.h	Sat Apr 17 01:50:23 2004 +0000
     5.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.3 @@ -1,134 +0,0 @@
     5.4 -// -*- c++ -*-
     5.5 -#ifndef HUGO_MINLENGTHPATHS_H
     5.6 -#define HUGO_MINLENGTHPATHS_H
     5.7 -
     5.8 -///\file
     5.9 -///\brief An algorithm for finding k paths of minimal total length.
    5.10 -
    5.11 -#include <iostream>
    5.12 -#include <dijkstra.h>
    5.13 -#include <graph_wrapper.h>
    5.14 -#include <maps.h>
    5.15 -
    5.16 -namespace hugo {
    5.17 -
    5.18 -
    5.19 -  ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
    5.20 -  /// of minimal total length 
    5.21 -  ///
    5.22 -  /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
    5.23 -  /// an algorithm which finds k edge-disjoint paths
    5.24 -  /// from a given source node to a given target node in an
    5.25 -  /// edge-weighted directed graph having minimal total weigth (length).
    5.26 -
    5.27 -  template <typename Graph, typename LengthMap>
    5.28 -  class MinLengthPaths {
    5.29 -
    5.30 -    typedef typename LengthMap::ValueType Length;
    5.31 -
    5.32 -    typedef typename Graph::Node Node;
    5.33 -    typedef typename Graph::NodeIt NodeIt;
    5.34 -    typedef typename Graph::Edge Edge;
    5.35 -    typedef typename Graph::OutEdgeIt OutEdgeIt;
    5.36 -    typedef typename Graph::EdgeMap<int> EdgeIntMap;
    5.37 -
    5.38 -    typedef ConstMap<Edge,int> ConstMap;
    5.39 -
    5.40 -    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
    5.41 -
    5.42 -
    5.43 -    class ModLengthMap {   
    5.44 -      typedef typename ResGraphType::NodeMap<Length> NodeMap;
    5.45 -      const ResGraphType& G;
    5.46 -      const EdgeIntMap& rev;
    5.47 -      const LengthMap &ol;
    5.48 -      const NodeMap &pot;
    5.49 -    public :
    5.50 -      typedef typename LengthMap::KeyType KeyType;
    5.51 -      typedef typename LengthMap::ValueType ValueType;
    5.52 -
    5.53 -      ValueType operator[](typename ResGraphType::Edge e) const {     
    5.54 -	if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    5.55 -	  ///\TODO This has to be removed
    5.56 -	  std::cout<<"Negative length!!"<<std::endl;
    5.57 -	}
    5.58 -	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    5.59 -      }     
    5.60 -
    5.61 -      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
    5.62 -		   const LengthMap &o,  const NodeMap &p) : 
    5.63 -	G(_G), rev(_rev), ol(o), pot(p){}; 
    5.64 -    };
    5.65 -    
    5.66 -
    5.67 -    const Graph& G;
    5.68 -    const LengthMap& length;
    5.69 -
    5.70 -    //auxiliary variable
    5.71 -    //The value is 1 iff the edge is reversed
    5.72 -    EdgeIntMap reversed; 
    5.73 -
    5.74 -    
    5.75 -  public :
    5.76 -
    5.77 -
    5.78 -    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
    5.79 -      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
    5.80 -
    5.81 -    ///Runs the algorithm
    5.82 -    
    5.83 -    ///Runs the algorithm
    5.84 -    ///Returns k if there are at least k edge-disjoint paths from s to t.
    5.85 -    ///Otherwise it returns the number of edge-disjoint paths from s to t.
    5.86 -    int run(Node s, Node t, int k) {
    5.87 -      ConstMap const1map(1);
    5.88 -
    5.89 -      ResGraphType res_graph(G, reversed, const1map);
    5.90 -
    5.91 -      //Initialize the copy of the Dijkstra potential to zero
    5.92 -      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
    5.93 -      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
    5.94 -
    5.95 -      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
    5.96 -      
    5.97 -      for (int i=0; i<k; ++i){
    5.98 -	dijkstra.run(s);
    5.99 -	if (!dijkstra.reached(t)){
   5.100 -	  //There is no k path from s to t
   5.101 -	  /// \TODO mit keresett itt ez a ++?
   5.102 -	  return i;
   5.103 -	};
   5.104 -	
   5.105 -	{
   5.106 -	  //We have to copy the potential
   5.107 -	  typename ResGraphType::NodeIt n;
   5.108 -	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
   5.109 -	      dijkstra_dist[n] += dijkstra.distMap()[n];
   5.110 -	  }
   5.111 -	}
   5.112 -
   5.113 -
   5.114 -	//Reversing the sortest path
   5.115 -	Node n=t;
   5.116 -	Edge e;
   5.117 -	while (n!=s){
   5.118 -	  e = dijkstra.pred(n);
   5.119 -	  n = dijkstra.predNode(n);
   5.120 -	  reversed[e] = 1-reversed[e];
   5.121 -	}
   5.122 -
   5.123 -	  
   5.124 -      }
   5.125 -      return k;
   5.126 -    }
   5.127 -
   5.128 -
   5.129 -
   5.130 -
   5.131 -
   5.132 -  }; //class MinLengthPaths
   5.133 -
   5.134 -
   5.135 -} //namespace hugo
   5.136 -
   5.137 -#endif //HUGO_MINLENGTHPATHS_H

     6.1 --- a/src/work/makefile	Sat Apr 17 01:50:23 2004 +0000
     6.2 +++ b/src/work/makefile	Sat Apr 17 01:57:48 2004 +0000
     6.3 @@ -1,7 +1,7 @@
     6.4  INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
     6.5  CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
     6.6  
     6.7 -BINARIES ?= bin_heap_demo iterator_bfs_demo
     6.8 +BINARIES ?= bin_heap_demo
     6.9  
    6.10  # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
    6.11  # ismert rendszeren :-)  (Misi)