LEMON/LEMON-official Changeset - r1021:4980b05606bd

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r1021:4980b05606bd

« 1019:234d63
« 1020:70bee0

1025:140c95 »
1022:8583fb »

r1021:4980b05606bd

Tue, 16 Nov 2010 07:46:01

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 8 3

merge default

3 files changed with 913 insertions and 14 deletions:

lemon/lemon.pc.cmake

lemon/nagamochi_ibaraki.h

697

test/nagamochi_ibaraki_test.cc

141

CMakeLists.txt

doc/CMakeLists.txt

doc/Doxyfile.in

lemon/CMakeLists.txt

lemon/Makefile.am

lemon/hao_orlin.h

test/CMakeLists.txt

test/Makefile.am

↑ Collapse diff ↑

lemon/lemon.pc.cmake

Show inline comments

 		prefix=@CMAKE_INSTALL_PREFIX@
 		exec_prefix=@CMAKE_INSTALL_PREFIX@/bin
 		libdir=@CMAKE_INSTALL_PREFIX@/lib
 		includedir=@CMAKE_INSTALL_PREFIX@/include
 		Name: @PROJECT_NAME@
 		Description: Library for Efficient Modeling and Optimization in Networks
 		Version: @PROJECT_VERSION@
 		Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
 		Cflags: -I${includedir}

lemon/nagamochi_ibaraki.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, 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 LEMON_NAGAMOCHI_IBARAKI_H
 		#define LEMON_NAGAMOCHI_IBARAKI_H
 		/// \ingroup min_cut
 		/// \file
 		/// \brief Implementation of the Nagamochi-Ibaraki algorithm.
 		#include <lemon/core.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/bucket_heap.h>
 		#include <lemon/maps.h>
 		#include <lemon/radix_sort.h>
 		#include <lemon/unionfind.h>
 		#include <cassert>
 		namespace lemon {
 		  /// \brief Default traits class for NagamochiIbaraki class.
 		  ///
 		  /// Default traits class for NagamochiIbaraki class.
 		  /// \param GR The undirected graph type.
 		  /// \param CM Type of capacity map.
 		  template <typename GR, typename CM>
 		  struct NagamochiIbarakiDefaultTraits {
 		    /// The type of the capacity map.
 		    typedef typename CM::Value Value;
 		    /// The undirected graph type the algorithm runs on.
 		    typedef GR Graph;
 		    /// \brief The type of the map that stores the edge capacities.
 		    ///
 		    /// The type of the map that stores the edge capacities.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CM CapacityMap;
 		    /// \brief Instantiates a CapacityMap.
 		    ///
 		    /// This function instantiates a \ref CapacityMap.
 		#ifdef DOXYGEN
 		    static CapacityMap *createCapacityMap(const Graph& graph)
 		#else
 		    static CapacityMap *createCapacityMap(const Graph&)
 		#endif
+		    {
 		        LEMON_ASSERT(false, "CapacityMap is not initialized");
 		        return 0; // ignore warnings
+		    }
 		    /// \brief The cross reference type used by heap.
 		    ///
 		    /// The cross reference type used by heap.
 		    /// Usually \c Graph::NodeMap<int>.
 		    typedef typename Graph::template NodeMap<int> HeapCrossRef;
 		    /// \brief Instantiates a HeapCrossRef.
 		    ///
 		    /// This function instantiates a \ref HeapCrossRef.
 		    /// \param g is the graph, to which we would like to define the
 		    /// \ref HeapCrossRef.
 		    static HeapCrossRef *createHeapCrossRef(const Graph& g) {
 		      return new HeapCrossRef(g);
+		    }
 		    /// \brief The heap type used by NagamochiIbaraki algorithm.
 		    ///
 		    /// The heap type used by NagamochiIbaraki algorithm. It has to
 		    /// maximize the priorities.
 		    ///
 		    /// \sa BinHeap
 		    /// \sa NagamochiIbaraki
 		    typedef BinHeap<Value, HeapCrossRef, std::greater<Value> > Heap;
 		    /// \brief Instantiates a Heap.
 		    ///
 		    /// This function instantiates a \ref Heap.
 		    /// \param r is the cross reference of the heap.
 		    static Heap *createHeap(HeapCrossRef& r) {
 		      return new Heap(r);
+		    }
 		  };
 		  /// \ingroup min_cut
 		  ///
 		  /// \brief Calculates the minimum cut in an undirected graph.
 		  ///
 		  /// Calculates the minimum cut in an undirected graph with the
 		  /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
 		  /// nodes into two partitions with the minimum sum of edge capacities
 		  /// between the two partitions. The algorithm can be used to test
 		  /// the network reliability, especially to test how many links have
 		  /// to be destroyed in the network to split it to at least two
 		  /// distinict subnetworks.
 		  ///
 		  /// The complexity of the algorithm is \f$ O(nm\log(n)) \f$ but with
 		  /// \ref FibHeap "Fibonacci heap" it can be decreased to
 		  /// \f$ O(nm+n^2\log(n)) \f$.  When the edges have unit capacities,
 		  /// \c BucketHeap can be used which yields \f$ O(nm) \f$ time
 		  /// complexity.
 		  ///
 		  /// \warning The value type of the capacity map should be able to
 		  /// hold any cut value of the graph, otherwise the result can
 		  /// overflow.
 		  /// \note This capacity is supposed to be integer type.
 		#ifdef DOXYGEN
 		  template <typename GR, typename CM, typename TR>
 		#else
 		  template <typename GR,
 		            typename CM = typename GR::template EdgeMap<int>,
 		            typename TR = NagamochiIbarakiDefaultTraits<GR, CM> >
 		#endif
 		  class NagamochiIbaraki {
 		  public:
 		    typedef TR Traits;
 		    /// The type of the underlying graph.
 		    typedef typename Traits::Graph Graph;
 		    /// The type of the capacity map.
 		    typedef typename Traits::CapacityMap CapacityMap;
 		    /// The value type of the capacity map.
 		    typedef typename Traits::CapacityMap::Value Value;
 		    /// The heap type used by the algorithm.
 		    typedef typename Traits::Heap Heap;
 		    /// The cross reference type used for the heap.
 		    typedef typename Traits::HeapCrossRef HeapCrossRef;
 		    ///\name Named template parameters
 		    ///@{
 		    struct SetUnitCapacityTraits : public Traits {
 		      typedef ConstMap<typename Graph::Edge, Const<int, 1> > CapacityMap;
 		      static CapacityMap *createCapacityMap(const Graph&) {
 		        return new CapacityMap();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// the capacity map to a constMap<Edge, int, 1>() instance
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// the capacity map to a constMap<Edge, int, 1>() instance
 		    struct SetUnitCapacity
 		      : public NagamochiIbaraki<Graph, CapacityMap,
 		                                SetUnitCapacityTraits> {
 		      typedef NagamochiIbaraki<Graph, CapacityMap,
 		                               SetUnitCapacityTraits> Create;
 		    };
 		    template <class H, class CR>
 		    struct SetHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(int num) {
 		        LEMON_ASSERT(false, "HeapCrossRef is not initialized");
 		        return 0; // ignore warnings
+		      }
 		      static Heap *createHeap(HeapCrossRef &) {
 		        LEMON_ASSERT(false, "Heap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// heap and cross reference type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting heap and
 		    /// cross reference type. The heap has to maximize the priorities.
 		    template <class H, class CR = RangeMap<int> >
 		    struct SetHeap
 		      : public NagamochiIbaraki<Graph, CapacityMap, SetHeapTraits<H, CR> > {
 		      typedef NagamochiIbaraki< Graph, CapacityMap, SetHeapTraits<H, CR> >
 		      Create;
 		    };
 		    template <class H, class CR>
 		    struct SetStandardHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(int size) {
 		        return new HeapCrossRef(size);
+		      }
 		      static Heap *createHeap(HeapCrossRef &crossref) {
 		        return new Heap(crossref);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// heap and cross reference type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting heap and
 		    /// cross reference type with automatic allocation. They should
 		    /// have standard constructor interfaces to be able to
 		    /// automatically created by the algorithm (i.e. the graph should
 		    /// be passed to the constructor of the cross reference and the
 		    /// cross reference should be passed to the constructor of the
 		    /// heap). However, external heap and cross reference objects
 		    /// could also be passed to the algorithm using the \ref heap()
 		    /// function before calling \ref run() or \ref init(). The heap
 		    /// has to maximize the priorities.
 		    /// \sa SetHeap
 		    template <class H, class CR = RangeMap<int> >
 		    struct SetStandardHeap
 		      : public NagamochiIbaraki<Graph, CapacityMap,
 		                                SetStandardHeapTraits<H, CR> > {
 		      typedef NagamochiIbaraki<Graph, CapacityMap,
 		                               SetStandardHeapTraits<H, CR> > Create;
 		    };
 		    ///@}
 		  private:
 		    const Graph &_graph;
 		    const CapacityMap *_capacity;
 		    bool _local_capacity; // unit capacity
 		    struct ArcData {
 		      typename Graph::Node target;
 		      int prev, next;
 		    };
 		    struct EdgeData {
 		      Value capacity;
 		      Value cut;
 		    };
 		    struct NodeData {
 		      int first_arc;
 		      typename Graph::Node prev, next;
 		      int curr_arc;
 		      typename Graph::Node last_rep;
 		      Value sum;
 		    };
 		    typename Graph::template NodeMap<NodeData> *_nodes;
 		    std::vector<ArcData> _arcs;
 		    std::vector<EdgeData> _edges;
 		    typename Graph::Node _first_node;
 		    int _node_num;
 		    Value _min_cut;
 		    HeapCrossRef *_heap_cross_ref;
 		    bool _local_heap_cross_ref;
 		    Heap *_heap;
 		    bool _local_heap;
 		    typedef typename Graph::template NodeMap<typename Graph::Node> NodeList;
 		    NodeList *_next_rep;
 		    typedef typename Graph::template NodeMap<bool> MinCutMap;
 		    MinCutMap *_cut_map;
 		    void createStructures() {
 		      if (!_nodes) {
 		        _nodes = new (typename Graph::template NodeMap<NodeData>)(_graph);
+		      }
 		      if (!_capacity) {
 		        _local_capacity = true;
 		        _capacity = Traits::createCapacityMap(_graph);
+		      }
 		      if (!_heap_cross_ref) {
 		        _local_heap_cross_ref = true;
 		        _heap_cross_ref = Traits::createHeapCrossRef(_graph);
+		      }
 		      if (!_heap) {
 		        _local_heap = true;
 		        _heap = Traits::createHeap(*_heap_cross_ref);
+		      }
 		      if (!_next_rep) {
 		        _next_rep = new NodeList(_graph);
+		      }
 		      if (!_cut_map) {
 		        _cut_map = new MinCutMap(_graph);
+		      }
+		    }
 		  public :
 		    typedef NagamochiIbaraki Create;
 		    /// \brief Constructor.
 		    ///
 		    /// \param graph The graph the algorithm runs on.
 		    /// \param capacity The capacity map used by the algorithm.
 		    NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity)
 		      : _graph(graph), _capacity(&capacity), _local_capacity(false),
 		        _nodes(0), _arcs(), _edges(), _min_cut(),
 		        _heap_cross_ref(0), _local_heap_cross_ref(false),
 		        _heap(0), _local_heap(false),
 		        _next_rep(0), _cut_map(0) {}
 		    /// \brief Constructor.
 		    ///
 		    /// This constructor can be used only when the Traits class
 		    /// defines how can the local capacity map be instantiated.
 		    /// If the SetUnitCapacity used the algorithm automatically
 		    /// constructs the capacity map.
 		    ///
 		    ///\param graph The graph the algorithm runs on.
 		    NagamochiIbaraki(const Graph& graph)
 		      : _graph(graph), _capacity(0), _local_capacity(false),
 		        _nodes(0), _arcs(), _edges(), _min_cut(),
 		        _heap_cross_ref(0), _local_heap_cross_ref(false),
 		        _heap(0), _local_heap(false),
 		        _next_rep(0), _cut_map(0) {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor.
 		    ~NagamochiIbaraki() {
 		      if (_local_capacity) delete _capacity;
 		      if (_nodes) delete _nodes;
 		      if (_local_heap) delete _heap;
 		      if (_local_heap_cross_ref) delete _heap_cross_ref;
 		      if (_next_rep) delete _next_rep;
 		      if (_cut_map) delete _cut_map;
+		    }
 		    /// \brief Sets the heap and the cross reference used by algorithm.
 		    ///
 		    /// Sets the heap and the cross reference used by algorithm.
 		    /// If you don't use this function before calling \ref run(),
 		    /// it will allocate one. The destuctor deallocates this
 		    /// automatically allocated heap and cross reference, of course.
 		    /// \return <tt> (*this) </tt>
 		    NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr)
+		    {
 		      if (_local_heap_cross_ref) {
 		        delete _heap_cross_ref;
 		        _local_heap_cross_ref = false;
+		      }
 		      _heap_cross_ref = &cr;
 		      if (_local_heap) {
 		        delete _heap;
 		        _local_heap = false;
+		      }
 		      _heap = &hp;
 		      return *this;
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \c run().
 		    /// \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init() and then call the start()
 		    /// or proper times the processNextPhase() member functions.
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      createStructures();
 		      int edge_num = countEdges(_graph);
 		      _edges.resize(edge_num);
 		      _arcs.resize(2 * edge_num);
 		      typename Graph::Node prev = INVALID;
 		      _node_num = 0;
 		      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_cut_map)[n] = false;
 		        (*_next_rep)[n] = INVALID;
 		        (*_nodes)[n].last_rep = n;
 		        (*_nodes)[n].first_arc = -1;
 		        (*_nodes)[n].curr_arc = -1;
 		        (*_nodes)[n].prev = prev;
 		        if (prev != INVALID) {
 		          (*_nodes)[prev].next = n;
+		        }
 		        (*_nodes)[n].next = INVALID;
 		        (*_nodes)[n].sum = 0;
 		        prev = n;
 		        ++_node_num;
+		      }
 		      _first_node = typename Graph::NodeIt(_graph);
 		      int index = 0;
 		      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
 		        for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) {
 		          typename Graph::Node m = _graph.target(a);
 		          if (!(n < m)) continue;
 		          (*_nodes)[n].sum += (*_capacity)[a];
 		          (*_nodes)[m].sum += (*_capacity)[a];
 		          int c = (*_nodes)[m].curr_arc;
 		          if (c != -1 && _arcs[c ^ 1].target == n) {
 		            _edges[c >> 1].capacity += (*_capacity)[a];
 		          } else {
 		            _edges[index].capacity = (*_capacity)[a];
 		            _arcs[index << 1].prev = -1;
 		            if ((*_nodes)[n].first_arc != -1) {
 		              _arcs[(*_nodes)[n].first_arc].prev = (index << 1);
+		            }
 		            _arcs[index << 1].next = (*_nodes)[n].first_arc;
 		            (*_nodes)[n].first_arc = (index << 1);
 		            _arcs[index << 1].target = m;
 		            (*_nodes)[m].curr_arc = (index << 1);
 		            _arcs[(index << 1) | 1].prev = -1;
 		            if ((*_nodes)[m].first_arc != -1) {
 		              _arcs[(*_nodes)[m].first_arc].prev = ((index << 1) | 1);
+		            }
 		            _arcs[(index << 1) | 1].next = (*_nodes)[m].first_arc;
 		            (*_nodes)[m].first_arc = ((index << 1) | 1);
 		            _arcs[(index << 1) | 1].target = n;
 		            ++index;
+		          }
+		        }
+		      }
 		      typename Graph::Node cut_node = INVALID;
 		      _min_cut = std::numeric_limits<Value>::max();
 		      for (typename Graph::Node n = _first_node;
 		           n != INVALID; n = (*_nodes)[n].next) {
 		        if ((*_nodes)[n].sum < _min_cut) {
 		          cut_node = n;
 		          _min_cut = (*_nodes)[n].sum;
+		        }
+		      }
 		      (*_cut_map)[cut_node] = true;
 		      if (_min_cut == 0) {
 		        _first_node = INVALID;
+		      }
+		    }
 		  public:
 		    /// \brief Processes the next phase
 		    ///
 		    /// Processes the next phase in the algorithm. It must be called
 		    /// at most one less the number of the nodes in the graph.
 		    ///
 		    ///\return %True when the algorithm finished.
 		    bool processNextPhase() {
 		      if (_first_node == INVALID) return true;
 		      _heap->clear();
 		      for (typename Graph::Node n = _first_node;
 		           n != INVALID; n = (*_nodes)[n].next) {
 		        (*_heap_cross_ref)[n] = Heap::PRE_HEAP;
+		      }
 		      std::vector<typename Graph::Node> order;
 		      order.reserve(_node_num);
 		      int sep = 0;
 		      Value alpha = 0;
 		      Value pmc = std::numeric_limits<Value>::max();
 		      _heap->push(_first_node, static_cast<Value>(0));
 		      while (!_heap->empty()) {
 		        typename Graph::Node n = _heap->top();
 		        Value v = _heap->prio();
 		        _heap->pop();
 		        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
 		          switch (_heap->state(_arcs[a].target)) {
 		          case Heap::PRE_HEAP:
+		            {
 		              Value nv = _edges[a >> 1].capacity;
 		              _heap->push(_arcs[a].target, nv);
 		              _edges[a >> 1].cut = nv;
 		            } break;
 		          case Heap::IN_HEAP:
+		            {
 		              Value nv = _edges[a >> 1].capacity + (*_heap)[_arcs[a].target];
 		              _heap->decrease(_arcs[a].target, nv);
 		              _edges[a >> 1].cut = nv;
 		            } break;
 		          case Heap::POST_HEAP:
 		            break;
+		          }
+		        }
 		        alpha += (*_nodes)[n].sum;
 		        alpha -= 2 * v;
 		        order.push_back(n);
 		        if (!_heap->empty()) {
 		          if (alpha < pmc) {
 		            pmc = alpha;
 		            sep = order.size();
+		          }
+		        }
+		      }
 		      if (static_cast<int>(order.size()) < _node_num) {
 		        _first_node = INVALID;
 		        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
 		          (*_cut_map)[n] = false;
+		        }
 		        for (int i = 0; i < static_cast<int>(order.size()); ++i) {
 		          typename Graph::Node n = order[i];
 		          while (n != INVALID) {
 		            (*_cut_map)[n] = true;
 		            n = (*_next_rep)[n];
+		          }
+		        }
 		        _min_cut = 0;
 		        return true;
+		      }
 		      if (pmc < _min_cut) {
 		        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
 		          (*_cut_map)[n] = false;
+		        }
 		        for (int i = 0; i < sep; ++i) {
 		          typename Graph::Node n = order[i];
 		          while (n != INVALID) {
 		            (*_cut_map)[n] = true;
 		            n = (*_next_rep)[n];
+		          }
+		        }
 		        _min_cut = pmc;
+		      }
 		      for (typename Graph::Node n = _first_node;
 		           n != INVALID; n = (*_nodes)[n].next) {
 		        bool merged = false;
 		        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
 		          if (!(_edges[a >> 1].cut < pmc)) {
 		            if (!merged) {
 		              for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) {
 		                (*_nodes)[_arcs[b].target].curr_arc = b;
+		              }
 		              merged = true;
+		            }
 		            typename Graph::Node m = _arcs[a].target;
 		            int nb = 0;
 		            for (int b = (*_nodes)[m].first_arc; b != -1; b = nb) {
 		              nb = _arcs[b].next;
 		              if ((b ^ a) == 1) continue;
 		              typename Graph::Node o = _arcs[b].target;
 		              int c = (*_nodes)[o].curr_arc;
 		              if (c != -1 && _arcs[c ^ 1].target == n) {
 		                _edges[c >> 1].capacity += _edges[b >> 1].capacity;
 		                (*_nodes)[n].sum += _edges[b >> 1].capacity;
 		                if (_edges[b >> 1].cut < _edges[c >> 1].cut) {
 		                  _edges[b >> 1].cut = _edges[c >> 1].cut;
+		                }
 		                if (_arcs[b ^ 1].prev != -1) {
 		                  _arcs[_arcs[b ^ 1].prev].next = _arcs[b ^ 1].next;
 		                } else {
 		                  (*_nodes)[o].first_arc = _arcs[b ^ 1].next;
+		                }
 		                if (_arcs[b ^ 1].next != -1) {
 		                  _arcs[_arcs[b ^ 1].next].prev = _arcs[b ^ 1].prev;
+		                }
 		              } else {
 		                if (_arcs[a].next != -1) {
 		                  _arcs[_arcs[a].next].prev = b;
+		                }
 		                _arcs[b].next = _arcs[a].next;
 		                _arcs[b].prev = a;
 		                _arcs[a].next = b;
 		                _arcs[b ^ 1].target = n;
 		                (*_nodes)[n].sum += _edges[b >> 1].capacity;
 		                (*_nodes)[o].curr_arc = b;
+		              }
+		            }
 		            if (_arcs[a].prev != -1) {
 		              _arcs[_arcs[a].prev].next = _arcs[a].next;
 		            } else {
 		              (*_nodes)[n].first_arc = _arcs[a].next;
+		            }
 		            if (_arcs[a].next != -1) {
 		              _arcs[_arcs[a].next].prev = _arcs[a].prev;
+		            }
 		            (*_nodes)[n].sum -= _edges[a >> 1].capacity;
 		            (*_next_rep)[(*_nodes)[n].last_rep] = m;
 		            (*_nodes)[n].last_rep = (*_nodes)[m].last_rep;
 		            if ((*_nodes)[m].prev != INVALID) {
 		              (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next;
 		            } else{
 		              _first_node = (*_nodes)[m].next;
+		            }
 		            if ((*_nodes)[m].next != INVALID) {
 		              (*_nodes)[(*_nodes)[m].next].prev = (*_nodes)[m].prev;
+		            }
 		            --_node_num;
+		          }
+		        }
+		      }
 		      if (_node_num == 1) {
 		        _first_node = INVALID;
 		        return true;
+		      }
 		      return false;
+		    }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// \pre init() must be called
 		    void start() {
 		      while (!processNextPhase()) {}
+		    }
 		    /// \brief Runs %NagamochiIbaraki algorithm.
 		    ///
 		    /// This method runs the %Min cut algorithm
 		    ///
 		    /// \note mc.run(s) is just a shortcut of the following code.
 		    ///\code
 		    ///  mc.init();
 		    ///  mc.start();
 		    ///\endcode
 		    void run() {
 		      init();
 		      start();
+		    }
 		    ///@}
 		    /// \name Query Functions
 		    ///
 		    /// The result of the %NagamochiIbaraki
 		    /// algorithm can be obtained using these functions.\n
 		    /// Before the use of these functions, either run() or start()
 		    /// must be called.
 		    ///@{
 		    /// \brief Returns the min cut value.
 		    ///
 		    /// Returns the min cut value if the algorithm finished.
 		    /// After the first processNextPhase() it is a value of a
 		    /// valid cut in the graph.
 		    Value minCutValue() const {
 		      return _min_cut;
+		    }
 		    /// \brief Returns a min cut in a NodeMap.
 		    ///
 		    /// It sets the nodes of one of the two partitions to true and
 		    /// the other partition to false.
 		    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
 		    /// \c bool (or convertible) value type.
 		    template <typename CutMap>
 		    Value minCutMap(CutMap& cutMap) const {
 		      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
 		        cutMap.set(n, (*_cut_map)[n]);
+		      }
 		      return minCutValue();
+		    }
 		    ///@}
 		  };
+		}
 		#endif

test/nagamochi_ibaraki_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, 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.
+		 *
 		 */
 		#include <sstream>
 		#include <lemon/smart_graph.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/nagamochi_ibaraki.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace std;
 		const std::string lgf =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@edges\n"
 		  "     cap1 cap2 cap3\n"
 		  "0 1  1    1    1   \n"
 		  "0 2  2    2    4   \n"
 		  "1 2  4    4    4   \n"
 		  "3 4  1    1    1   \n"
 		  "3 5  2    2    4   \n"
 		  "4 5  4    4    4   \n"
 		  "2 3  1    6    6   \n";
 		void checkNagamochiIbarakiCompile()
+		{
 		  typedef int Value;
 		  typedef concepts::Graph Graph;
 		  typedef Graph::Node Node;
 		  typedef Graph::Edge Edge;
 		  typedef concepts::ReadMap<Edge, Value> CapMap;
 		  typedef concepts::WriteMap<Node, bool> CutMap;
 		  Graph g;
 		  Node n;
 		  CapMap cap;
 		  CutMap cut;
 		  Value v;
 		  bool b;
 		  NagamochiIbaraki<Graph, CapMap> ni_test(g, cap);
 		  const NagamochiIbaraki<Graph, CapMap>& const_ni_test = ni_test;
 		  ni_test.init();
 		  ni_test.start();
 		  b = ni_test.processNextPhase();
 		  ni_test.run();
 		  v = const_ni_test.minCutValue();
 		  v = const_ni_test.minCutMap(cut);
+		}
 		template <typename Graph, typename CapMap, typename CutMap>
 		typename CapMap::Value
 		  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
+		{
 		  typename CapMap::Value sum = 0;
 		  for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) {
 		    if (cut[graph.u(e)] != cut[graph.v(e)]) {
 		      sum += cap[e];
+		    }
+		  }
 		  return sum;
+		}
 		int main() {
 		  SmartGraph graph;
 		  SmartGraph::EdgeMap<int> cap1(graph), cap2(graph), cap3(graph);
 		  SmartGraph::NodeMap<bool> cut(graph);
 		  istringstream input(lgf);
 		  graphReader(graph, input)
 		    .edgeMap("cap1", cap1)
 		    .edgeMap("cap2", cap2)
 		    .edgeMap("cap3", cap3)
 		    .run();
+		  {
 		    NagamochiIbaraki<SmartGraph> ni(graph, cap1);
 		    ni.run();
 		    ni.minCutMap(cut);
 		    check(ni.minCutValue() == 1, "Wrong cut value");
 		    check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
+		  }
+		  {
 		    NagamochiIbaraki<SmartGraph> ni(graph, cap2);
 		    ni.run();
 		    ni.minCutMap(cut);
 		    check(ni.minCutValue() == 3, "Wrong cut value");
 		    check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
+		  }
+		  {
 		    NagamochiIbaraki<SmartGraph> ni(graph, cap3);
 		    ni.run();
 		    ni.minCutMap(cut);
 		    check(ni.minCutValue() == 5, "Wrong cut value");
 		    check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
+		  }
+		  {
 		    NagamochiIbaraki<SmartGraph>::SetUnitCapacity::Create ni(graph);
 		    ni.run();
 		    ni.minCutMap(cut);
 		    ConstMap<SmartGraph::Edge, int> cap4(1);
 		    check(ni.minCutValue() == 1, "Wrong cut value");
 		    check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value");
+		  }
 		  return 0;
+		}

CMakeLists.txt

Show inline comments

 		CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
 		SET(PROJECT_NAME "LEMON")
 		PROJECT(${PROJECT_NAME})
 		INCLUDE(FindPythonInterp)
 		INCLUDE(FindWget)
 		IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		ELSEIF(DEFINED ENV{LEMON_VERSION})
 		  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
 		ELSE()
 		  EXECUTE_PROCESS(
 		    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
 		    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		    OUTPUT_VARIABLE HG_REVISION_PATH
 		    ERROR_QUIET
 		    OUTPUT_STRIP_TRAILING_WHITESPACE
+		  )
 		  EXECUTE_PROCESS(
 		    COMMAND hg id -i
 		    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		    OUTPUT_VARIABLE HG_REVISION
 		    ERROR_QUIET
 		    OUTPUT_STRIP_TRAILING_WHITESPACE
+		  )
 		  IF(HG_REVISION STREQUAL "")
 		    SET(HG_REVISION_ID "hg-tip")
 		  ELSE()
 		    IF(HG_REVISION_PATH STREQUAL "")
 		      SET(HG_REVISION_ID ${HG_REVISION})
 		    ELSE()
 		      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
 		    ENDIF()
 		  ENDIF()
 		  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
 		ENDIF()
 		SET(PROJECT_VERSION ${LEMON_VERSION})
 		SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
 		FIND_PACKAGE(Doxygen)
 		FIND_PACKAGE(Ghostscript)
 		FIND_PACKAGE(GLPK 4.33)
 		FIND_PACKAGE(CPLEX)
 		FIND_PACKAGE(COIN)
 		IF(DEFINED ENV{LEMON_CXX_WARNING})
 		  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
 		ELSE()
 		  IF(CMAKE_COMPILER_IS_GNUCXX)
 		    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
 		    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
 		    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
 		  ELSEIF(MSVC)
 		    # This part is unnecessary 'casue the same is set by the lemon/core.h.
 		    # Still keep it as an example.
 		    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
 		    # Suppressed warnings:
 		    # C4250: 'class1' : inherits 'class2::member' via dominance
 		    # C4355: 'this' : used in base member initializer list
 		    # C4503: 'function' : decorated name length exceeded, name was truncated
 		    # C4800: 'type' : forcing value to bool 'true' or 'false'
 		    #        (performance warning)
 		    # C4996: 'function': was declared deprecated
 		  ELSE()
 		    SET(CXX_WARNING "-Wall -W")
 		  ENDIF()
 		ENDIF()
 		SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
 		SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
 		SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
 		    "Flags used by the C++ compiler during maintainer builds."
 		    FORCE )
 		SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
 		    "Flags used by the C compiler during maintainer builds."
 		    FORCE )
 		SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
 		    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
 		    "Flags used for linking binaries during maintainer builds."
 		    FORCE )
 		SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
 		    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
 		    "Flags used by the shared libraries linker during maintainer builds."
 		    FORCE )
 		MARK_AS_ADVANCED(
 		    CMAKE_CXX_FLAGS_MAINTAINER
 		    CMAKE_C_FLAGS_MAINTAINER
 		    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
 		    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
 		IF(CMAKE_CONFIGURATION_TYPES)
 		  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
 		  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
 		  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
 		      "Add the configurations that we need"
 		      FORCE)
 		 endif()
 		IF(NOT CMAKE_BUILD_TYPE)
 		  SET(CMAKE_BUILD_TYPE "Release")
 		ENDIF()
 		SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
 		    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
 		    FORCE )
 		INCLUDE(CheckTypeSize)
 		CHECK_TYPE_SIZE("long long" LONG_LONG)
 		SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 		ENABLE_TESTING()
 		IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
 		  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
 		ELSE()
 		  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
 		ENDIF()
 		ADD_SUBDIRECTORY(lemon)
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  ADD_SUBDIRECTORY(demo)
 		  ADD_SUBDIRECTORY(tools)
 		  ADD_SUBDIRECTORY(doc)
 		  ADD_SUBDIRECTORY(test)
 		ENDIF()
 		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
 		  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		  @ONLY
+		)
 		IF(UNIX)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION share/lemon/cmake
+		  )
 		ELSEIF(WIN32)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION cmake
+		  )
 		ENDIF()
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
 		  SET(CPACK_PACKAGE_VENDOR "EGRES")
 		  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
 		    "LEMON - Library for Efficient Modeling and Optimization in Networks")
 		  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
 		  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
 		  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
 		    "${PROJECT_NAME} ${PROJECT_VERSION}")
 		  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
 		    "${PROJECT_NAME} ${PROJECT_VERSION}")
 		  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 		  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
 		  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
 		  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 		  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
 		    "C++ header files")
 		  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
 		    "DLL and import library")
 		  SET(CPACK_COMPONENT_BIN_DESCRIPTION
 		    "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
 		    "Doxygen generated documentation")
 		  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
 		  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
 		  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
 		  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
 		    "Components needed to develop software using LEMON")
 		  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
 		    "Documentation of LEMON")
 		  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
 		  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
 		  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
 		  SET(CPACK_GENERATOR "NSIS")
 		  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
 		  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
 		  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
 		    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
 		    ")
 		  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
 		    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
 		    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
 		    ")
 		  INCLUDE(CPack)
 		ENDIF()

doc/CMakeLists.txt

Show inline comments

 		SET(PACKAGE_NAME ${PROJECT_NAME})
 		SET(PACKAGE_VERSION ${PROJECT_VERSION})
 		SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
 		SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 		SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
 		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
 		  ${PROJECT_BINARY_DIR}/doc/Doxyfile
 		  @ONLY
+		)
 		IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
 		  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
 		  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
 		  ADD_CUSTOM_TARGET(html
 		    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
 		    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
 		    COMMAND ${CMAKE_COMMAND} -E remove_directory html
 		    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
 		    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
 		    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+		  )
 		  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
 		  IF(UNIX)
 		    INSTALL(
 		      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		      DESTINATION share/doc/lemon/html
 		      COMPONENT html_documentation
+		    )
 		  ELSEIF(WIN32)
 		    INSTALL(
 		      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		      DESTINATION doc
 		      COMPONENT html_documentation
+		    )
 		  ENDIF()
 		ENDIF()
 		IF(WGET_FOUND)
 		ADD_CUSTOM_TARGET(update-external-tags
 		  COMMAND ${CMAKE_COMMAND} -E make_directory dl
 		  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
 		  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
 		  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
 		  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
 		  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
 		  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+		  )
 		ENDIF()

doc/Doxyfile.in

Show inline comments

 		# Doxyfile 1.5.9
 		#---------------------------------------------------------------------------
 		# Project related configuration options
 		#---------------------------------------------------------------------------
 		DOXYFILE_ENCODING      = UTF-8
 		PROJECT_NAME           = @PACKAGE_NAME@
 		PROJECT_NUMBER         = @PACKAGE_VERSION@
 		OUTPUT_DIRECTORY       =
 		CREATE_SUBDIRS         = NO
 		OUTPUT_LANGUAGE        = English
 		BRIEF_MEMBER_DESC      = YES
 		REPEAT_BRIEF           = NO
 		ABBREVIATE_BRIEF       =
 		ALWAYS_DETAILED_SEC    = NO
 		INLINE_INHERITED_MEMB  = NO
 		FULL_PATH_NAMES        = YES
 		STRIP_FROM_PATH        = "@abs_top_srcdir@"
 		STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
 		SHORT_NAMES            = YES
 		JAVADOC_AUTOBRIEF      = NO
 		QT_AUTOBRIEF           = NO
 		MULTILINE_CPP_IS_BRIEF = NO
 		INHERIT_DOCS           = NO
 		SEPARATE_MEMBER_PAGES  = NO
 		TAB_SIZE               = 8
 		ALIASES                =
 		OPTIMIZE_OUTPUT_FOR_C  = NO
 		OPTIMIZE_OUTPUT_JAVA   = NO
 		OPTIMIZE_FOR_FORTRAN   = NO
 		OPTIMIZE_OUTPUT_VHDL   = NO
 		BUILTIN_STL_SUPPORT    = YES
 		CPP_CLI_SUPPORT        = NO
 		SIP_SUPPORT            = NO
 		IDL_PROPERTY_SUPPORT   = YES
 		DISTRIBUTE_GROUP_DOC   = NO
 		SUBGROUPING            = YES
 		TYPEDEF_HIDES_STRUCT   = NO
 		SYMBOL_CACHE_SIZE      = 0
 		#---------------------------------------------------------------------------
 		# Build related configuration options
 		#---------------------------------------------------------------------------
 		EXTRACT_ALL            = NO
 		EXTRACT_PRIVATE        = YES
 		EXTRACT_STATIC         = YES
 		EXTRACT_LOCAL_CLASSES  = NO
 		EXTRACT_LOCAL_METHODS  = NO
 		EXTRACT_ANON_NSPACES   = NO
 		HIDE_UNDOC_MEMBERS     = YES
 		HIDE_UNDOC_CLASSES     = YES
 		HIDE_FRIEND_COMPOUNDS  = NO
 		HIDE_IN_BODY_DOCS      = NO
 		INTERNAL_DOCS          = NO
 		CASE_SENSE_NAMES       = YES
 		HIDE_SCOPE_NAMES       = YES
 		SHOW_INCLUDE_FILES     = YES
 		INLINE_INFO            = YES
 		SORT_MEMBER_DOCS       = NO
 		SORT_BRIEF_DOCS        = NO
 		SORT_GROUP_NAMES       = NO
 		SORT_BY_SCOPE_NAME     = NO
 		GENERATE_TODOLIST      = YES
 		GENERATE_TESTLIST      = YES
 		GENERATE_BUGLIST       = YES
 		GENERATE_DEPRECATEDLIST= YES
 		ENABLED_SECTIONS       =
 		MAX_INITIALIZER_LINES  = 5
 		SHOW_USED_FILES        = NO
 		SHOW_DIRECTORIES       = YES
 		SHOW_FILES             = YES
 		SHOW_NAMESPACES        = YES
 		FILE_VERSION_FILTER    =
 		LAYOUT_FILE            = DoxygenLayout.xml
+		LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
 		#---------------------------------------------------------------------------
 		# configuration options related to warning and progress messages
 		#---------------------------------------------------------------------------
 		QUIET                  = NO
 		WARNINGS               = YES
 		WARN_IF_UNDOCUMENTED   = YES
 		WARN_IF_DOC_ERROR      = YES
 		WARN_NO_PARAMDOC       = NO
 		WARN_FORMAT            = "$file:$line: $text"
 		WARN_LOGFILE           = doxygen.log
 		#---------------------------------------------------------------------------
 		# configuration options related to the input files
 		#---------------------------------------------------------------------------
 		INPUT                  = "@abs_top_srcdir@/doc" \
 		                         "@abs_top_srcdir@/lemon" \
 		                         "@abs_top_srcdir@/lemon/bits" \
 		                         "@abs_top_srcdir@/lemon/concepts" \
 		                         "@abs_top_srcdir@/demo" \
 		                         "@abs_top_srcdir@/tools" \
 		                         "@abs_top_srcdir@/test/test_tools.h" \
 		                         "@abs_top_builddir@/doc/references.dox"
 		INPUT_ENCODING         = UTF-8
 		FILE_PATTERNS          = *.h \
 		                         *.cc \
 		                         *.dox
 		RECURSIVE              = NO
 		EXCLUDE                =
 		EXCLUDE_SYMLINKS       = NO
 		EXCLUDE_PATTERNS       =
 		EXCLUDE_SYMBOLS        =
 		EXAMPLE_PATH           = "@abs_top_srcdir@/demo" \
 		                         "@abs_top_srcdir@/LICENSE" \
 		                         "@abs_top_srcdir@/doc"
 		EXAMPLE_PATTERNS       =
 		EXAMPLE_RECURSIVE      = NO
 		IMAGE_PATH             = "@abs_top_srcdir@/doc/images" \
 		                         "@abs_top_builddir@/doc/gen-images"
 		INPUT_FILTER           =
 		FILTER_PATTERNS        =
 		FILTER_SOURCE_FILES    = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to source browsing
 		#---------------------------------------------------------------------------
-		SOURCE_BROWSER         = NO
+		SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
 		INLINE_SOURCES         = NO
 		STRIP_CODE_COMMENTS    = YES
 		REFERENCED_BY_RELATION = NO
 		REFERENCES_RELATION    = NO
 		REFERENCES_LINK_SOURCE = YES
 		USE_HTAGS              = NO
 		VERBATIM_HEADERS       = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the alphabetical class index
 		#---------------------------------------------------------------------------
 		ALPHABETICAL_INDEX     = YES
 		COLS_IN_ALPHA_INDEX    = 2
 		IGNORE_PREFIX          =
 		#---------------------------------------------------------------------------
 		# configuration options related to the HTML output
 		#---------------------------------------------------------------------------
 		GENERATE_HTML          = YES
 		HTML_OUTPUT            = html
 		HTML_FILE_EXTENSION    = .html
 		HTML_HEADER            =
 		HTML_FOOTER            =
 		HTML_STYLESHEET        =
 		HTML_ALIGN_MEMBERS     = YES
 		HTML_DYNAMIC_SECTIONS  = NO
 		GENERATE_DOCSET        = NO
 		DOCSET_FEEDNAME        = "Doxygen generated docs"
 		DOCSET_BUNDLE_ID       = org.doxygen.Project
 		GENERATE_HTMLHELP      = NO
 		CHM_FILE               =
 		HHC_LOCATION           =
 		GENERATE_CHI           = NO
 		CHM_INDEX_ENCODING     =
 		BINARY_TOC             = NO
 		TOC_EXPAND             = NO
 		GENERATE_QHP           = NO
 		QCH_FILE               =
 		QHP_NAMESPACE          = org.doxygen.Project
 		QHP_VIRTUAL_FOLDER     = doc
 		QHG_LOCATION           =
 		DISABLE_INDEX          = NO
 		ENUM_VALUES_PER_LINE   = 4
 		GENERATE_TREEVIEW      = NO
 		TREEVIEW_WIDTH         = 250
 		FORMULA_FONTSIZE       = 10
 		#---------------------------------------------------------------------------
 		# configuration options related to the LaTeX output
 		#---------------------------------------------------------------------------
 		GENERATE_LATEX         = NO
 		LATEX_OUTPUT           = latex
 		LATEX_CMD_NAME         = latex
 		MAKEINDEX_CMD_NAME     = makeindex
 		COMPACT_LATEX          = YES
 		PAPER_TYPE             = a4wide
 		EXTRA_PACKAGES         = amsmath \
 		                         amssymb
 		LATEX_HEADER           =
 		PDF_HYPERLINKS         = YES
 		USE_PDFLATEX           = YES
 		LATEX_BATCHMODE        = NO
 		LATEX_HIDE_INDICES     = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the RTF output
 		#---------------------------------------------------------------------------
 		GENERATE_RTF           = NO
 		RTF_OUTPUT             = rtf
 		COMPACT_RTF            = NO
 		RTF_HYPERLINKS         = NO
 		RTF_STYLESHEET_FILE    =
 		RTF_EXTENSIONS_FILE    =
 		#---------------------------------------------------------------------------
 		# configuration options related to the man page output
 		#---------------------------------------------------------------------------
 		GENERATE_MAN           = NO
 		MAN_OUTPUT             = man
 		MAN_EXTENSION          = .3
 		MAN_LINKS              = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the XML output
 		#---------------------------------------------------------------------------
 		GENERATE_XML           = NO
 		XML_OUTPUT             = xml
 		XML_SCHEMA             =
 		XML_DTD                =
 		XML_PROGRAMLISTING     = YES
 		#---------------------------------------------------------------------------
 		# configuration options for the AutoGen Definitions output
 		#---------------------------------------------------------------------------
 		GENERATE_AUTOGEN_DEF   = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the Perl module output
 		#---------------------------------------------------------------------------
 		GENERATE_PERLMOD       = NO
 		PERLMOD_LATEX          = NO
 		PERLMOD_PRETTY         = YES
 		PERLMOD_MAKEVAR_PREFIX =
 		#---------------------------------------------------------------------------
 		# Configuration options related to the preprocessor
 		#---------------------------------------------------------------------------
 		ENABLE_PREPROCESSING   = YES
 		MACRO_EXPANSION        = NO
 		EXPAND_ONLY_PREDEF     = NO
 		SEARCH_INCLUDES        = YES
 		INCLUDE_PATH           =
 		INCLUDE_FILE_PATTERNS  =
 		PREDEFINED             = DOXYGEN
 		EXPAND_AS_DEFINED      =
 		SKIP_FUNCTION_MACROS   = YES
 		#---------------------------------------------------------------------------
 		# Options related to the search engine
 		#---------------------------------------------------------------------------
-		TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
+		TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 		GENERATE_TAGFILE       = html/lemon.tag
 		ALLEXTERNALS           = NO
 		EXTERNAL_GROUPS        = NO
 		PERL_PATH              = /usr/bin/perl
 		#---------------------------------------------------------------------------
 		# Configuration options related to the dot tool
 		#---------------------------------------------------------------------------
 		CLASS_DIAGRAMS         = YES
 		MSCGEN_PATH            =
 		HIDE_UNDOC_RELATIONS   = YES
 		HAVE_DOT               = YES
 		DOT_FONTNAME           = FreeSans
 		DOT_FONTSIZE           = 10
 		DOT_FONTPATH           =
 		CLASS_GRAPH            = YES
 		COLLABORATION_GRAPH    = NO
 		GROUP_GRAPHS           = NO
 		UML_LOOK               = NO
 		TEMPLATE_RELATIONS     = NO
 		INCLUDE_GRAPH          = NO
 		INCLUDED_BY_GRAPH      = NO
 		CALL_GRAPH             = NO
 		CALLER_GRAPH           = NO
 		GRAPHICAL_HIERARCHY    = NO
 		DIRECTORY_GRAPH        = NO
 		DOT_IMAGE_FORMAT       = png
 		DOT_PATH               =
 		DOTFILE_DIRS           =
 		DOT_GRAPH_MAX_NODES    = 50
 		MAX_DOT_GRAPH_DEPTH    = 0
 		DOT_TRANSPARENT        = NO
 		DOT_MULTI_TARGETS      = NO
 		GENERATE_LEGEND        = YES
 		DOT_CLEANUP            = YES
 		#---------------------------------------------------------------------------
 		# Configuration::additions related to the search engine
 		#---------------------------------------------------------------------------
 		SEARCHENGINE           = NO

lemon/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		CONFIGURE_FILE(
 		  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
 		  ${CMAKE_CURRENT_BINARY_DIR}/config.h
+		)
 		CONFIGURE_FILE(
 		  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
 		  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
 		  @ONLY
+		)
 		SET(LEMON_SOURCES
 		  arg_parser.cc
 		  base.cc
 		  color.cc
 		  lp_base.cc
 		  lp_skeleton.cc
 		  random.cc
 		  bits/windows.cc
+		)
 		IF(LEMON_HAVE_GLPK)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
 		  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
 		  IF(WIN32)
 		    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
 		    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
 		    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
 		  ENDIF()
 		ENDIF()
 		IF(LEMON_HAVE_CPLEX)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
 		  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
 		ENDIF()
 		IF(LEMON_HAVE_CLP)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
 		  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
 		ENDIF()
 		IF(LEMON_HAVE_CBC)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
 		  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
 		ENDIF()
 		ADD_LIBRARY(lemon ${LEMON_SOURCES})
 		IF(UNIX)
 		  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
 		ENDIF()
 		INSTALL(
 		  TARGETS lemon
 		  ARCHIVE DESTINATION lib
 		  COMPONENT library
+		)
 		INSTALL(
 		  DIRECTORY . bits concepts
 		  DESTINATION include/lemon
 		  COMPONENT headers
 		  FILES_MATCHING PATTERN "*.h"
+		)
 		INSTALL(
 		  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
 		  DESTINATION include/lemon
 		  COMPONENT headers
+		)
 		INSTALL(
 		  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
 		  DESTINATION lib/pkgconfig
+		)

lemon/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			lemon/lemon.pc.in \
 			lemon/CMakeLists.txt \
 			lemon/config.h.cmake
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 			lemon/arg_parser.cc \
 			lemon/base.cc \
 			lemon/color.cc \
 			lemon/lp_base.cc \
 			lemon/lp_skeleton.cc \
 			lemon/random.cc \
 			lemon/bits/windows.cc
 		nodist_lemon_HEADERS = lemon/config.h
 		lemon_libemon_la_CXXFLAGS = \
 			$(AM_CXXFLAGS) \
 			$(GLPK_CFLAGS) \
 			$(CPLEX_CFLAGS) \
 			$(SOPLEX_CXXFLAGS) \
 			$(CLP_CXXFLAGS) \
 			$(CBC_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = \
 			$(GLPK_LIBS) \
 			$(CPLEX_LIBS) \
 			$(SOPLEX_LIBS) \
 			$(CLP_LIBS) \
 			$(CBC_LIBS)
 		if HAVE_GLPK
 		lemon_libemon_la_SOURCES += lemon/glpk.cc
 		endif
 		if HAVE_CPLEX
 		lemon_libemon_la_SOURCES += lemon/cplex.cc
 		endif
 		if HAVE_SOPLEX
 		lemon_libemon_la_SOURCES += lemon/soplex.cc
 		endif
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		if HAVE_CBC
 		lemon_libemon_la_SOURCES += lemon/cbc.cc
 		endif
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 			lemon/arg_parser.h \
 			lemon/assert.h \
 			lemon/bellman_ford.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
 			lemon/binomial_heap.h \
 			lemon/bucket_heap.h \
 			lemon/capacity_scaling.h \
 			lemon/cbc.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/connectivity.h \
 			lemon/core.h \
 			lemon/cost_scaling.h \
 			lemon/counter.h \
 			lemon/cplex.h \
 			lemon/cycle_canceling.h \
 			lemon/dfs.h \
 			lemon/dheap.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/fib_heap.h \
 			lemon/fractional_matching.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/grosso_locatelli_pullan_mc.h \
 			lemon/hartmann_orlin_mmc.h \
 			lemon/howard_mmc.h \
 			lemon/hypercube_graph.h \
 			lemon/karp_mmc.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			lemon/min_cost_arborescence.h \
 			lemon/max_cardinality_search.h \
 			lemon/nagamochi_ibaraki.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/pairing_heap.h \
 			lemon/path.h \
 			lemon/planarity.h \
 			lemon/preflow.h \
 			lemon/quad_heap.h \
 			lemon/radix_heap.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/soplex.h \
 			lemon/static_graph.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
 			lemon/bits/windows.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/graph_components.h \
 			lemon/concepts/heap.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h

lemon/hao_orlin.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, 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 LEMON_HAO_ORLIN_H
 		#define LEMON_HAO_ORLIN_H
 		#include <vector>
 		#include <list>
 		#include <limits>
 		#include <lemon/maps.h>
 		#include <lemon/core.h>
 		#include <lemon/tolerance.h>
 		/// \file
 		/// \ingroup min_cut
 		/// \brief Implementation of the Hao-Orlin algorithm.
 		///
 		/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
 		/// in a digraph.
 		namespace lemon {
 		  /// \ingroup min_cut
 		  ///
 		  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
 		  ///
 		  /// This class implements the Hao-Orlin algorithm for finding a minimum
 		  /// value cut in a directed graph \f$D=(V,A)\f$.
 		  /// It takes a fixed node \f$ source \in V \f$ and
 		  /// consists of two phases: in the first phase it determines a
 		  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
 		  /// capacity) and in the second phase it determines a minimum cut
 		  /// with \f$ source \f$ on the sink-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
 		  /// capacity). Obviously, the smaller of these two cuts will be a
 		  /// minimum cut of \f$ D \f$. The algorithm is a modified
 		  /// preflow push-relabel algorithm. Our implementation calculates
 		  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
 		  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
 		  /// purpose of such algorithm is e.g. testing network reliability.
 		  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
 		  /// use of this algorithm is testing network reliability.
 		  ///
 		  /// For an undirected graph you can run just the first phase of the
 		  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
 		  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
 		  /// time. It is implemented in the NagamochiIbaraki algorithm class.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CAP The type of the arc map containing the capacities,
 		  /// which can be any numreric type. The default map type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TOL Tolerance class for handling inexact computations. The
 		  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TOL>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TOL = Tolerance<typename CAP::Value> >
 		#endif
 		  class HaoOrlin {
 		  public:
 		    /// The digraph type of the algorithm
 		    typedef GR Digraph;
 		    /// The capacity map type of the algorithm
 		    typedef CAP CapacityMap;
 		    /// The tolerance type of the algorithm
 		    typedef TOL Tolerance;
 		  private:
 		    typedef typename CapacityMap::Value Value;
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph& _graph;
 		    const CapacityMap* _capacity;
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    FlowMap* _flow;
 		    Node _source;
 		    int _node_num;
 		    // Bucketing structure
 		    std::vector<Node> _first, _last;
 		    typename Digraph::template NodeMap<Node>* _next;
 		    typename Digraph::template NodeMap<Node>* _prev;
 		    typename Digraph::template NodeMap<bool>* _active;
 		    typename Digraph::template NodeMap<int>* _bucket;
 		    std::vector<bool> _dormant;
 		    std::list<std::list<int> > _sets;
 		    std::list<int>::iterator _highest;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    typedef typename Digraph::template NodeMap<bool> SourceSetMap;
 		    SourceSetMap* _source_set;
 		    Value _min_cut;
 		    typedef typename Digraph::template NodeMap<bool> MinCutMap;
 		    MinCutMap* _min_cut_map;
 		    Tolerance _tolerance;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the algorithm class.
 		    HaoOrlin(const Digraph& graph, const CapacityMap& capacity,
 		             const Tolerance& tolerance = Tolerance()) :
 		      _graph(graph), _capacity(&capacity), _flow(0), _source(),
 		      _node_num(), _first(), _last(), _next(0), _prev(0),
 		      _active(0), _bucket(0), _dormant(), _sets(), _highest(),
 		      _excess(0), _source_set(0), _min_cut(), _min_cut_map(0),
 		      _tolerance(tolerance) {}
 		    ~HaoOrlin() {
 		      if (_min_cut_map) {
 		        delete _min_cut_map;
+		      }
 		      if (_source_set) {
 		        delete _source_set;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
 		      if (_next) {
 		        delete _next;
+		      }
 		      if (_prev) {
 		        delete _prev;
+		      }
 		      if (_active) {
 		        delete _active;
+		      }
 		      if (_bucket) {
 		        delete _bucket;
+		      }
 		      if (_flow) {
 		        delete _flow;
+		      }
+		    }
 		    /// \brief Set the tolerance used by the algorithm.
 		    ///
 		    /// This function sets the tolerance object used by the algorithm.
 		    /// \return <tt>(*this)</tt>
 		    HaoOrlin& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// This function returns a const reference to the tolerance object
 		    /// used by the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tolerance;
+		    }
 		  private:
 		    void activate(const Node& i) {
 		      (*_active)[i] = true;
 		      int bucket = (*_bucket)[i];
 		      if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
 		      //unlace
 		      (*_next)[(*_prev)[i]] = (*_next)[i];
 		      if ((*_next)[i] != INVALID) {
 		        (*_prev)[(*_next)[i]] = (*_prev)[i];
 		      } else {
 		        _last[bucket] = (*_prev)[i];
+		      }
 		      //lace
 		      (*_next)[i] = _first[bucket];
 		      (*_prev)[_first[bucket]] = i;
 		      (*_prev)[i] = INVALID;
 		      _first[bucket] = i;
+		    }
 		    void deactivate(const Node& i) {
 		      (*_active)[i] = false;
 		      int bucket = (*_bucket)[i];
 		      if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;
 		      //unlace
 		      (*_prev)[(*_next)[i]] = (*_prev)[i];
 		      if ((*_prev)[i] != INVALID) {
 		        (*_next)[(*_prev)[i]] = (*_next)[i];
 		      } else {
 		        _first[bucket] = (*_next)[i];
+		      }
 		      //lace
 		      (*_prev)[i] = _last[bucket];
 		      (*_next)[_last[bucket]] = i;
 		      (*_next)[i] = INVALID;
 		      _last[bucket] = i;
+		    }
 		    void addItem(const Node& i, int bucket) {
 		      (*_bucket)[i] = bucket;
 		      if (_last[bucket] != INVALID) {
 		        (*_prev)[i] = _last[bucket];
 		        (*_next)[_last[bucket]] = i;
 		        (*_next)[i] = INVALID;
 		        _last[bucket] = i;
 		      } else {
 		        (*_prev)[i] = INVALID;
 		        _first[bucket] = i;
 		        (*_next)[i] = INVALID;
 		        _last[bucket] = i;
+		      }
+		    }
 		    void findMinCutOut() {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_excess)[n] = 0;
 		        (*_source_set)[n] = false;
+		      }
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        (*_flow)[a] = 0;
+		      }
 		      int bucket_num = 0;
 		      std::vector<Node> queue(_node_num);
 		      int qfirst = 0, qlast = 0, qsep = 0;
+		      {
 		        typename Digraph::template NodeMap<bool> reached(_graph, false);
 		        reached[_source] = true;
 		        bool first_set = true;
 		        for (NodeIt t(_graph); t != INVALID; ++t) {
 		          if (reached[t]) continue;
 		          _sets.push_front(std::list<int>());
 		          queue[qlast++] = t;
 		          reached[t] = true;
 		          while (qfirst != qlast) {
 		            if (qsep == qfirst) {
 		              ++bucket_num;
 		              _sets.front().push_front(bucket_num);
 		              _dormant[bucket_num] = !first_set;
 		              _first[bucket_num] = _last[bucket_num] = INVALID;
 		              qsep = qlast;
+		            }
 		            Node n = queue[qfirst++];
 		            addItem(n, bucket_num);
 		            for (InArcIt a(_graph, n); a != INVALID; ++a) {
 		              Node u = _graph.source(a);
 		              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
 		                reached[u] = true;
 		                queue[qlast++] = u;
+		              }
+		            }
+		          }
 		          first_set = false;
+		        }
 		        ++bucket_num;
 		        (*_bucket)[_source] = 0;
 		        _dormant[0] = true;
+		      }
 		      (*_source_set)[_source] = true;
 		      Node target = _last[_sets.back().back()];
+		      {
 		        for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
 		          if (_tolerance.positive((*_capacity)[a])) {
 		            Node u = _graph.target(a);
 		            (*_flow)[a] = (*_capacity)[a];
 		            (*_excess)[u] += (*_capacity)[a];
 		            if (!(*_active)[u] && u != _source) {
 		              activate(u);
+		            }
+		          }
+		        }
 		        if ((*_active)[target]) {
 		          deactivate(target);
@@ -659,347 +659,357 @@
+		          }
 		          for (OutArcIt a(_graph, n); a != INVALID; ++a) {
 		            Node v = _graph.target(a);
 		            if (_dormant[(*_bucket)[v]]) continue;
 		            Value rem = (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            if ((*_bucket)[v] == under_bucket) {
 		              if (!(*_active)[v] && v != target) {
 		                activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                (*_flow)[a] -= excess;
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                (*_flow)[a] = 0;
+		              }
 		            } else if (next_bucket > (*_bucket)[v]) {
 		              next_bucket = (*_bucket)[v];
+		            }
+		          }
 		        no_more_push:
 		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if ((*_next)[n] == INVALID) {
 		              typename std::list<std::list<int> >::iterator new_set =
 		                _sets.insert(--_sets.end(), std::list<int>());
 		              new_set->splice(new_set->end(), _sets.back(),
 		                              _sets.back().begin(), ++_highest);
 		              for (std::list<int>::iterator it = new_set->begin();
 		                   it != new_set->end(); ++it) {
 		                _dormant[*it] = true;
+		              }
 		              while (_highest != _sets.back().end() &&
 		                     !(*_active)[_first[*_highest]]) {
 		                ++_highest;
+		              }
 		            } else if (next_bucket == _node_num) {
 		              _first[(*_bucket)[n]] = (*_next)[n];
 		              (*_prev)[(*_next)[n]] = INVALID;
 		              std::list<std::list<int> >::iterator new_set =
 		                _sets.insert(--_sets.end(), std::list<int>());
 		              new_set->push_front(bucket_num);
 		              (*_bucket)[n] = bucket_num;
 		              _first[bucket_num] = _last[bucket_num] = n;
 		              (*_next)[n] = INVALID;
 		              (*_prev)[n] = INVALID;
 		              _dormant[bucket_num] = true;
 		              ++bucket_num;
 		              while (_highest != _sets.back().end() &&
 		                     !(*_active)[_first[*_highest]]) {
 		                ++_highest;
+		              }
 		            } else {
 		              _first[*_highest] = (*_next)[n];
 		              (*_prev)[(*_next)[n]] = INVALID;
 		              while (next_bucket != *_highest) {
 		                --_highest;
+		              }
 		              if (_highest == _sets.back().begin()) {
 		                _sets.back().push_front(bucket_num);
 		                _dormant[bucket_num] = false;
 		                _first[bucket_num] = _last[bucket_num] = INVALID;
 		                ++bucket_num;
+		              }
 		              --_highest;
 		              (*_bucket)[n] = *_highest;
 		              (*_next)[n] = _first[*_highest];
 		              if (_first[*_highest] != INVALID) {
 		                (*_prev)[_first[*_highest]] = n;
 		              } else {
 		                _last[*_highest] = n;
+		              }
 		              _first[*_highest] = n;
+		            }
 		          } else {
 		            deactivate(n);
 		            if (!(*_active)[_first[*_highest]]) {
 		              ++_highest;
 		              if (_highest != _sets.back().end() &&
 		                  !(*_active)[_first[*_highest]]) {
 		                _highest = _sets.back().end();
+		              }
+		            }
+		          }
+		        }
 		        if ((*_excess)[target] < _min_cut) {
 		          _min_cut = (*_excess)[target];
 		          for (NodeIt i(_graph); i != INVALID; ++i) {
 		            (*_min_cut_map)[i] = false;
+		          }
 		          for (std::list<int>::iterator it = _sets.back().begin();
 		               it != _sets.back().end(); ++it) {
 		            Node n = _first[*it];
 		            while (n != INVALID) {
 		              (*_min_cut_map)[n] = true;
 		              n = (*_next)[n];
+		            }
+		          }
+		        }
+		        {
 		          Node new_target;
 		          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
 		            if ((*_next)[target] == INVALID) {
 		              _last[(*_bucket)[target]] = (*_prev)[target];
 		              new_target = (*_prev)[target];
 		            } else {
 		              (*_prev)[(*_next)[target]] = (*_prev)[target];
 		              new_target = (*_next)[target];
+		            }
 		            if ((*_prev)[target] == INVALID) {
 		              _first[(*_bucket)[target]] = (*_next)[target];
 		            } else {
 		              (*_next)[(*_prev)[target]] = (*_next)[target];
+		            }
 		          } else {
 		            _sets.back().pop_back();
 		            if (_sets.back().empty()) {
 		              _sets.pop_back();
 		              if (_sets.empty())
 		                break;
 		              for (std::list<int>::iterator it = _sets.back().begin();
 		                   it != _sets.back().end(); ++it) {
 		                _dormant[*it] = false;
+		              }
+		            }
 		            new_target = _last[_sets.back().back()];
+		          }
 		          (*_bucket)[target] = 0;
 		          (*_source_set)[target] = true;
 		          for (InArcIt a(_graph, target); a != INVALID; ++a) {
 		            Value rem = (*_capacity)[a] - (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = (*_capacity)[a];
+		          }
 		          for (OutArcIt a(_graph, target); a != INVALID; ++a) {
 		            Value rem = (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = 0;
+		          }
 		          target = new_target;
 		          if ((*_active)[target]) {
 		            deactivate(target);
+		          }
 		          _highest = _sets.back().begin();
 		          while (_highest != _sets.back().end() &&
 		                 !(*_active)[_first[*_highest]]) {
 		            ++_highest;
+		          }
+		        }
+		      }
+		    }
 		  public:
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \ref run().
 		    /// \n
 		    /// If you need better control on the execution,
 		    /// you have to call one of the \ref init() functions first, then
 		    /// \ref calculateOut() and/or \ref calculateIn().
 		    /// @{
 		    /// \brief Initialize the internal data structures.
 		    ///
 		    /// This function initializes the internal data structures. It creates
 		    /// the maps and some bucket structures for the algorithm.
 		    /// The first node is used as the source node for the push-relabel
 		    /// algorithm.
 		    void init() {
 		      init(NodeIt(_graph));
+		    }
 		    /// \brief Initialize the internal data structures.
 		    ///
 		    /// This function initializes the internal data structures. It creates
 		    /// the maps and some bucket structures for the algorithm.
 		    /// The given node is used as the source node for the push-relabel
 		    /// algorithm.
 		    void init(const Node& source) {
 		      _source = source;
 		      _node_num = countNodes(_graph);
 		      _first.resize(_node_num);
 		      _last.resize(_node_num);
 		      _dormant.resize(_node_num);
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
+		      }
 		      if (!_next) {
 		        _next = new typename Digraph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_prev) {
 		        _prev = new typename Digraph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_active) {
 		        _active = new typename Digraph::template NodeMap<bool>(_graph);
+		      }
 		      if (!_bucket) {
 		        _bucket = new typename Digraph::template NodeMap<int>(_graph);
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
 		      if (!_source_set) {
 		        _source_set = new SourceSetMap(_graph);
+		      }
 		      if (!_min_cut_map) {
 		        _min_cut_map = new MinCutMap(_graph);
+		      }
 		      _min_cut = std::numeric_limits<Value>::max();
+		    }
 		    /// \brief Calculate a minimum cut with \f$ source \f$ on the
 		    /// source-side.
 		    ///
 		    /// This function calculates a minimum cut with \f$ source \f$ on the
 		    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
 		    /// \f$ source \in X \f$ and minimal outgoing capacity).
 		    /// It updates the stored cut if (and only if) the newly found one
 		    /// is better.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    void calculateOut() {
 		      findMinCutOut();
+		    }
 		    /// \brief Calculate a minimum cut with \f$ source \f$ on the
 		    /// sink-side.
 		    ///
 		    /// This function calculates a minimum cut with \f$ source \f$ on the
 		    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
 		    /// \f$ source \notin X \f$ and minimal outgoing capacity).
 		    /// It updates the stored cut if (and only if) the newly found one
 		    /// is better.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    void calculateIn() {
 		      findMinCutIn();
+		    }
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm. It finds nodes \c source and
 		    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
 		    /// This function runs the algorithm. It chooses source node,
 		    /// then calls \ref init(), \ref calculateOut()
 		    /// and \ref calculateIn().
 		    void run() {
 		      init();
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm. It uses the given \c source node,
 		    /// finds a proper \c target node and then calls the \ref init(),
-		    /// \ref calculateOut() and \ref calculateIn().
+		    /// This function runs the algorithm. It calls \ref init(),
 		    /// \ref calculateOut() and \ref calculateIn() with the given
 		    /// source node.
 		    void run(const Node& s) {
 		      init(s);
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The result of the %HaoOrlin algorithm
 		    /// can be obtained using these functions.\n
 		    /// \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// should be called before using them.
 		    /// @{
 		    /// \brief Return the value of the minimum cut.
 		    ///
-		    /// This function returns the value of the minimum cut.
+		    /// This function returns the value of the best cut found by the
 		    /// previously called \ref run(), \ref calculateOut() or \ref
 		    /// calculateIn().
 		    ///
 		    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// must be called before using this function.
 		    Value minCutValue() const {
 		      return _min_cut;
+		    }
 		    /// \brief Return a minimum cut.
 		    ///
 		    /// This function sets \c cutMap to the characteristic vector of a
 		    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
-		    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
+		    /// This function gives the best cut found by the
 		    /// previously called \ref run(), \ref calculateOut() or \ref
 		    /// calculateIn().
 		    ///
 		    /// It sets \c cutMap to the characteristic vector of the found
 		    /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
 		    /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
 		    /// for the nodes of \f$ X \f$).
 		    ///
 		    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
 		    /// \c bool (or convertible) value type.
 		    ///
 		    /// \return The value of the minimum cut.
 		    ///
 		    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// must be called before using this function.
 		    template <typename CutMap>
 		    Value minCutMap(CutMap& cutMap) const {
 		      for (NodeIt it(_graph); it != INVALID; ++it) {
 		        cutMap.set(it, (*_min_cut_map)[it]);
+		      }
 		      return _min_cut;
+		    }
 		    /// @}
 		  }; //class HaoOrlin
 		} //namespace lemon
 		#endif //LEMON_HAO_ORLIN_H

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		LINK_DIRECTORIES(
 		  ${PROJECT_BINARY_DIR}/lemon
+		)
 		SET(TESTS
 		  adaptors_test
 		  bellman_ford_test
 		  bfs_test
 		  circulation_test
 		  connectivity_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  fractional_matching_test
 		  gomory_hu_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  maps_test
 		  matching_test
 		  max_cardinality_search_test
 		  max_clique_test
 		  min_cost_arborescence_test
 		  min_cost_flow_test
 		  min_mean_cycle_test
 		  nagamochi_ibaraki_test
 		  path_test
 		  planarity_test
 		  preflow_test
 		  radix_sort_test
 		  random_test
 		  suurballe_test
 		  time_measure_test
 		  unionfind_test
+		)
 		IF(LEMON_HAVE_LP)
 		  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
 		  ADD_EXECUTABLE(lp_test lp_test.cc)
 		  ELSE()
 		    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
 		  ENDIF()
 		  SET(LP_TEST_LIBS lemon)
 		  IF(LEMON_HAVE_GLPK)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
 		  ENDIF()
 		  IF(LEMON_HAVE_CPLEX)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
 		  ENDIF()
 		  IF(LEMON_HAVE_CLP)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
 		  ENDIF()
 		  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
 		  ADD_TEST(lp_test lp_test)
 		  IF(WIN32 AND LEMON_HAVE_GLPK)
 		    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+		    )
 		  ENDIF()
 		  IF(WIN32 AND LEMON_HAVE_CPLEX)
 		    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
 		      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+		    )
 		  ENDIF()
 		ENDIF()
 		IF(LEMON_HAVE_MIP)
 		  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
 		  ADD_EXECUTABLE(mip_test mip_test.cc)
 		  ELSE()
 		    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
 		  ENDIF()
 		  SET(MIP_TEST_LIBS lemon)
 		  IF(LEMON_HAVE_GLPK)
 		    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})
 		  ENDIF()
 		  IF(LEMON_HAVE_CPLEX)
 		    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
 		  ENDIF()
 		  IF(LEMON_HAVE_CBC)
 		    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})
 		  ENDIF()
 		  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
 		  ADD_TEST(mip_test mip_test)
 		  IF(WIN32 AND LEMON_HAVE_GLPK)
 		    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+		    )
 		  ENDIF()
 		  IF(WIN32 AND LEMON_HAVE_CPLEX)
 		    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
 		      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+		    )
 		  ENDIF()
 		ENDIF()
 		FOREACH(TEST_NAME ${TESTS})
 		  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
 		    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
 		  ELSE()
 		    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
 		  ENDIF()
 		  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
 		  ADD_TEST(${TEST_NAME} ${TEST_NAME})
 		  ADD_DEPENDENCIES(check ${TEST_NAME})
 		ENDFOREACH()

test/Makefile.am

Show inline comments

 		if USE_VALGRIND
 		TESTS_ENVIRONMENT=$(top_srcdir)/scripts/valgrind-wrapper.sh
 		endif
 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bellman_ford_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/connectivity_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/euler_test \
 			test/fractional_matching_test \
 			test/gomory_hu_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/hao_orlin_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/maps_test \
 			test/matching_test \
 			test/max_cardinality_search_test \
 			test/max_clique_test \
 			test/min_cost_arborescence_test \
 			test/min_cost_flow_test \
 			test/min_mean_cycle_test \
 			test/nagamochi_ibaraki_test \
 			test/path_test \
 			test/planarity_test \
 			test/preflow_test \
 			test/radix_sort_test \
 			test/random_test \
 			test/suurballe_test \
 			test/test_tools_fail \
 			test/test_tools_pass \
 			test/time_measure_test \
 			test/unionfind_test
 		test_test_tools_pass_DEPENDENCIES = demo
 		if HAVE_LP
 		check_PROGRAMS += test/lp_test
 		endif HAVE_LP
 		if HAVE_MIP
 		check_PROGRAMS += test/mip_test
 		endif HAVE_MIP
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_connectivity_test_SOURCES = test/connectivity_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_euler_test_SOURCES = test/euler_test.cc
 		test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
 		test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 		test_lp_test_SOURCES = test/lp_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_mip_test_SOURCES = test/mip_test.cc
 		test_matching_test_SOURCES = test/matching_test.cc
 		test_max_cardinality_search_test_SOURCES = test/max_cardinality_search_test.cc
 		test_max_clique_test_SOURCES = test/max_clique_test.cc
 		test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 		test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
 		test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
 		test_nagamochi_ibaraki_test_SOURCES = test/nagamochi_ibaraki_test.cc
 		test_path_test_SOURCES = test/path_test.cc
 		test_planarity_test_SOURCES = test/planarity_test.cc
 		test_preflow_test_SOURCES = test/preflow_test.cc
 		test_radix_sort_test_SOURCES = test/radix_sort_test.cc
 		test_suurballe_test_SOURCES = test/suurballe_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_time_measure_test_SOURCES = test/time_measure_test.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

0 comments (0 inline)

RhodeCode

Login to your account