# HG changeset patch # User klao # Date 1096475484 0 # Node ID e816fac59f6d709bc4d7f100924a573a09205c35 # Parent 818510fa3d99e8c960874b7074d950a2013098a9 hugo -> lemon renaming leftovers diff -r 818510fa3d99 -r e816fac59f6d AUTHORS --- a/AUTHORS Wed Sep 29 15:30:04 2004 +0000 +++ b/AUTHORS Wed Sep 29 16:31:24 2004 +0000 @@ -1,4 +1,4 @@ -HUGOlib was started as an inter-university project from two +LEMON was started as an inter-university project from two universities: BME (Budapest University of Technology and Economics, Hungary) and ELTE (Eotvos Lorand University, Budapest, Hungary) and supported by ETIK (Inter-University Centre for Telecommunications and @@ -16,7 +16,7 @@ For every contributor we list the supporters who supported his or her work. -So here is (the hopefully complete) list of contributors of the HUGOlib +So here is (the hopefully complete) list of contributors of the LEMON (in alphabetical order). The fields are: name (N), email (E), web-address (W), PGP key ID and fingerprint (P), description (D), snail-mail address (A), Subversion commit name (C), and the list of supporters (S) diff -r 818510fa3d99 -r e816fac59f6d COPYING --- a/COPYING Wed Sep 29 15:30:04 2004 +0000 +++ b/COPYING Wed Sep 29 16:31:24 2004 +0000 @@ -1,8 +1,8 @@ -HUGOlib as a whole is copyrighted by Egerváry Jenő Kombinatorikus +LEMON as a whole is copyrighted by Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoport (Egervary Combinatorial Optimization Research Group, EGRES). -You are free to use, modify and distribute HUGOlib under the terms +You are free to use, modify and distribute LEMON under the terms described in the LICENSE file. This project is supported by diff -r 818510fa3d99 -r e816fac59f6d LICENSE --- a/LICENSE Wed Sep 29 15:30:04 2004 +0000 +++ b/LICENSE Wed Sep 29 16:31:24 2004 +0000 @@ -1,4 +1,4 @@ -HUGOlib code without an explicit copyright is covered by the following +LEMON code without an explicit copyright is covered by the following copyright/license: Copyright (C) 2003-2004 Egervary Jeno Kombinatorikus Optimalizalasi diff -r 818510fa3d99 -r e816fac59f6d doc/Doxyfile --- a/doc/Doxyfile Wed Sep 29 15:30:04 2004 +0000 +++ b/doc/Doxyfile Wed Sep 29 16:31:24 2004 +0000 @@ -17,7 +17,7 @@ # The PROJECT_NAME tag is a single word (or a sequence of words surrounded # by quotes) that should identify the project. -PROJECT_NAME = HugoLib +PROJECT_NAME = LEMON # The PROJECT_NUMBER tag can be used to enter a project or revision number. # This could be handy for archiving the generated documentation or @@ -397,8 +397,8 @@ coding_style.dox \ groups.dox \ namespaces.dox \ - ../src/hugo \ - ../src/hugo/skeletons \ + ../src/lemon \ + ../src/lemon/skeletons \ ../src/test/test_tools.h # If the value of the INPUT tag contains directories, you can use the diff -r 818510fa3d99 -r e816fac59f6d src/demo/sub_graph_wrapper_demo.dim --- a/src/demo/sub_graph_wrapper_demo.dim Wed Sep 29 15:30:04 2004 +0000 +++ b/src/demo/sub_graph_wrapper_demo.dim Wed Sep 29 16:31:24 2004 +0000 @@ -1,4 +1,4 @@ -c HUGO max flow problem +c LEMON max flow problem p max 7 9 n 1 s n 7 t diff -r 818510fa3d99 -r e816fac59f6d src/lemon/tight_edge_filter_map.h --- a/src/lemon/tight_edge_filter_map.h Wed Sep 29 15:30:04 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,63 +0,0 @@ -/* -*- C++ -*- - * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H -#define HUGO_TIGHT_EDGE_FILTER_MAP_H - -#include - -// /// \file -// /// \brief Maximum flow algorithms. -// /// \ingroup galgs - -namespace hugo { - - /// \brief A map for filtering the edge-set to those edges - /// which are tight w.r.t. some node_potential map and - /// edge_distance map. - /// - /// A node-map node_potential is said to be a potential w.r.t. - /// an edge-map edge_distance - /// if and only if for each edge e, node_potential[g.head(e)] - /// <= edge_distance[e]+node_potential[g.tail(e)] - /// (or the reverse inequality holds for each edge). - /// An edge is said to be tight if this inequality holds with equality, - /// and the map returns true exactly for those edges. - /// To avoid rounding errors, it is recommended to use this class with exact - /// types, e.g. with int. - template - class TightEdgeFilterMap : public MapBase { - protected: - const Graph* g; - NodePotentialMap* node_potential; - EdgeDistanceMap* edge_distance; - public: - TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, - EdgeDistanceMap& _edge_distance) : - g(&_g), node_potential(&_node_potential), - edge_distance(&_edge_distance) { } - bool operator[](const typename Graph::Edge& e) const { - return ((*node_potential)[g->head(e)] == - (*edge_distance)[e]+(*node_potential)[g->tail(e)]); - } - }; - -} //namespace hugo - -#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H - - diff -r 818510fa3d99 -r e816fac59f6d src/work/Doxyfile --- a/src/work/Doxyfile Wed Sep 29 15:30:04 2004 +0000 +++ b/src/work/Doxyfile Wed Sep 29 16:31:24 2004 +0000 @@ -17,13 +17,13 @@ # The PROJECT_NAME tag is a single word (or a sequence of words surrounded # by quotes) that should identify the project. -PROJECT_NAME = HugoLib +PROJECT_NAME = LEMON # The PROJECT_NUMBER tag can be used to enter a project or revision number. # This could be handy for archiving the generated documentation or # if some version control system is used. -PROJECT_NUMBER = 0.1 +PROJECT_NUMBER = 0.2 # The OUTPUT_DIRECTORY tag is used to specify the (relative or absolute) # base path where the generated documentation will be put. @@ -395,8 +395,8 @@ ../../doc/graphs.dox \ ../../doc/maps.dox ../../doc/coding_style.dox \ ../../doc/groups.dox \ - ../hugo \ - ../hugo/skeletons \ + ../lemon \ + ../lemon/skeletons \ ../test/test_tools.h \ klao/path.h \ klao/debug.h \ diff -r 818510fa3d99 -r e816fac59f6d src/work/athos/preflow_push.hh --- a/src/work/athos/preflow_push.hh Wed Sep 29 15:30:04 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,486 +0,0 @@ -#ifndef HUGO_PREFLOW_PUSH_HH -#define HUGO_PREFLOW_PUSH_HH - -//#include -#include -#include -#include -//#include "pf_hiba.hh" -//#include -//#include -#include -#include -//#include - -using namespace std; - -namespace hugo { - - template - class preflow_push { - - //Useful typedefs - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - typedef typename Graph::EdgeMap CapacityType; - - typedef ResGraphWrapper ResGraphType; - - - //--------------------------------------------- - //Parameters of the algorithm - //--------------------------------------------- - //Fully examine an active node until excess becomes 0 - enum node_examination_t {examine_full, examine_to_relabel}; - //No more implemented yet:, examine_only_one_edge}; - node_examination_t node_examination; - //Which implementation to be used - enum implementation_t {impl_fifo, impl_highest_label}; - //No more implemented yet:}; - implementation_t implementation; - //--------------------------------------------- - //Parameters of the algorithm - //--------------------------------------------- - - private: - //input - Graph& G; - Node s; - Node t; - CapacityType &capacity; - - //output - CapacityType preflow; - T maxflow_value; - - //auxiliary variables for computation - //The number of the nodes - int number_of_nodes; - //A nodemap for the level - typename Graph::NodeMap level; - //A nodemap for the excess - typename Graph::NodeMap excess; - - //Number of nodes on each level - vector num_of_nodes_on_level; - - //For the FIFO implementation - list fifo_nodes; - //For 'highest label' implementation - int highest_active; - //int second_highest_active; - vector< list > active_nodes; - - public: - - //Constructing the object using the graph, source, sink and capacity vector - preflow_push( - Graph& _G, - Node _s, - Node _t, - typename Graph::EdgeMap & _capacity) - : G(_G), s(_s), t(_t), - capacity(_capacity), - preflow(_G), - //Counting the number of nodes - //number_of_nodes(count(G.first())), - number_of_nodes(G.nodeNum()), - - level(_G), - excess(_G)//, - // Default constructor: active_nodes() - { - //Simplest parameter settings - node_examination = examine_full;//examine_to_relabel;// - //Which implementation to be usedexamine_full - implementation = impl_highest_label;//impl_fifo; - - // - num_of_nodes_on_level.resize(2*number_of_nodes-1); - num_of_nodes_on_level.clear(); - - switch(implementation){ - case impl_highest_label :{ - active_nodes.clear(); - active_nodes.resize(2*number_of_nodes-1); - - break; - } - default: - break; - } - - } - - //Returns the value of a maximal flow - T run(); - - typename Graph::EdgeMap getmaxflow(){ - return preflow; - } - - - private: - //For testing purposes only - //Lists the node_properties - void write_property_vector(typename Graph::NodeMap a, - //node_property_vector a, - char* prop_name="property"){ - for(NodeIt i=G.template first(); G.valid(i); G.next(i)) { - cout<<"Node id.: "<=0 && active_nodes[highest_active].empty() ){ - --highest_active; - } - - if( highest_active>=0) { - - - Node a=active_nodes[highest_active].front(); - active_nodes[highest_active].pop_front(); - - return a; - } - else { - return INVALID; - } - - break; - - } - case impl_fifo : { - - if( ! fifo_nodes.empty() ) { - Node a=fifo_nodes.front(); - fifo_nodes.pop_front(); - return a; - } - else { - return INVALID; - } - break; - } - } - // - return INVALID; - } - - //Puts node 'a' among the active nodes - void make_active(const Node& a){ - //s and t never become active - if (a!=s && a!= t){ - switch(implementation){ - case impl_highest_label : - active_nodes[level[a]].push_back(a); - break; - case impl_fifo : - fifo_nodes.push_back(a); - break; - } - - } - - //Update highest_active label - if (highest_active(); G.valid(i); G.next(i)) { - level.set(i,0); - excess.set(i,0); - for(OutEdgeIt j=G.template first(i); G.valid(j); G.next(j)) - preflow.set(j, 0); - } - num_of_nodes_on_level[0]=number_of_nodes; - highest_active=0; - //--------------------------------------- - //Initialize parameters - //--------------------------------------- - - - //------------------------------------ - //This is the only part that uses BFS - //------------------------------------ - - /*Reverse_bfs from t, to find the starting level.*/ - //Copyright: Jacint - change_level_to(t,0); - - std::queue bfs_queue; - bfs_queue.push(t); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(G.first(e,v); G.valid(e); G.next(e)) { - Node w=G.tail(e); - if ( level[w] == number_of_nodes && w != s ) { - bfs_queue.push(w); - //Node first=level_list[l]; - //if ( G.valid(first) ) left.set(first,w); - //right.set(w,first); - //level_list[l]=w; - change_level_to(w, l); - //level.set(w, l); - } - } - } - change_level_to(s,number_of_nodes); - //level.set(s,number_of_nodes); - - /* - //Setting starting level values using reverse bfs - reverse_bfs rev_bfs(G,t); - rev_bfs.run(); - //write_property_vector(rev_bfs.dist,"rev_bfs"); - for(NodeIt i=G.template first(); G.valid(i); G.next(i)) { - change_level_to(i,rev_bfs.dist(i)); - //level.put(i,rev_bfs.dist.get(i)); - } - */ - //------------------------------------ - //This is the only part that uses BFS - //------------------------------------ - - - //Starting level of s - change_level_to(s,number_of_nodes); - //level.put(s,number_of_nodes); - - - //we push as much preflow from s as possible to start with - for(OutEdgeIt j=G.template first(s); G.valid(j); G.next(j)){ - modify_preflow(j,capacity[j] ); - make_active(G.head(j)); - int lev=level[G.head(j)]; - if(highest_activepreflow[j]){ - if(level[G.tail(j)]==level[G.head(j)]+1){ - return true; - } - else{ - if (level[G.head(j)] < new_level) - new_level=level[G.head(j)]; - } - } - return false; - } - - //If the preflow is greater than 0 on the given edge - //then the edge reversd is an edge in the residual graph - bool is_admissible_backward_edge(Edge j, int& new_level){ - - if (0 - T preflow_push::run() { - - //We need a residual graph - ResGraphType res_graph(G, preflow, capacity); - - preprocess(); - //write_property_vector(level,"level"); - T e,v; - Node a; - while (a=get_active_node(), G.valid(a)){ - - bool go_to_next_node=false; - e = excess[a]; - while (!go_to_next_node){ - - //Initial value for the new level for the active node we are dealing with - int new_level=2*number_of_nodes; - - - //Out edges from node a - { - ResGraphType::OutEdgeIt j=res_graph.first(j,a); - while (res_graph.valid(j) && e){ - if (is_admissible_forward_edge(j,new_level)){ - v=min(e,res_graph.resCap(j)); - e -= v; - //New node might become active - if (excess[res_graph.head(j)]==0){ - make_active(res_graph.head(j)); - } - res_graph.augment(j,v); - excess[res_graph.tail(j)] -= v; - excess[res_graph.head(j)] += v; - } - res_graph.next(j); - } - } - - /* - //Out edges from node a - { - OutEdgeIt j=G.template first(a); - while (G.valid(j) && e){ - - if (is_admissible_forward_edge(j,new_level)){ - v=min(e,capacity[j] - preflow[j]); - e -= v; - //New node might become active - if (excess[G.head(j)]==0){ - make_active(G.head(j)); - } - modify_preflow(j,v); - } - G.next(j); - } - } - //In edges to node a - { - InEdgeIt j=G.template first(a); - while (G.valid(j) && e){ - if (is_admissible_backward_edge(j,new_level)){ - v=min(e,preflow[j]); - e -= v; - //New node might become active - if (excess[G.tail(j)]==0){ - make_active(G.tail(j)); - } - modify_preflow(j,-v); - } - G.next(j); - } - } - */ - - //if (G.id(a)==999) - //cout<