RhodeCode

This group describes the several data structures implemented in LEMON.

This group describes some graph types between real graphs and graph adaptors.

This group describes the map structures implemented in LEMON.

This group describes maps that are specifically designed to assign

This group describes map adaptors that are used to create "implicit"

This group describes two dimensional data storages implemented in LEMON.

This group describes the path structures implemented in LEMON.

This group describes some data structures implemented in LEMON in

\brief This group describes the several algorithms

This group describes the several algorithms

This group describes the common graph search algorithms, namely

This group describes the algorithms for finding shortest paths in digraphs.

This group describes the algorithms for finding maximum flows and

This group describes the algorithms for finding minimum cost flows and

This group describes the algorithms for finding minimum cut in graphs.

- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating

This group describes the algorithms for discovering the graph properties

This group describes the algorithms for planarity checking,

This group describes the algorithms for finding a minimum cost spanning

This group describes some algorithms implemented in LEMON

This group describes the approximation and heuristic algorithms

\brief This group describes some general optimization frameworks

This group describes some general optimization frameworks

This group describes Lp and Mip solver interfaces for LEMON. The

This group describes some metaheuristic optimization tools.

This group describes some simple basic graph utilities.

This group describes several useful tools for development,

This group describes simple tools for measuring the performance

This group describes the exceptions defined in LEMON.

This group describes the tools for importing and exporting graphs

This group describes methods for reading and writing

This group describes general \c EPS drawing methods and special

This group describes the data/algorithm skeletons and concept checking

This group describes the skeletons and concept checking classes of LEMON's

This group describes the skeletons and concept checking classes of maps.

If you already feel like using our library, see the page that tells you

\ref getstart "How to start using LEMON".

If you

want to see how LEMON works, see

some \ref demoprograms "demo programs".

<a class="el" href="modules.html">Modules</a>

section.

    /// Its value type is inherited from the first arc map type

    /// (\c %ForwardMap).

    template <typename ForwardMap, typename BackwardMap>

      typedef typename ForwardMap::Value Value;

      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;

      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;

      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;

      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)

      ForwardMap* _forward;

      BackwardMap* _backward;

    template <typename ForwardMap, typename BackwardMap>

    static CombinedArcMap<ForwardMap, BackwardMap>

    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {

      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);

    }

    template <typename ForwardMap, typename BackwardMap>

    static CombinedArcMap<const ForwardMap, BackwardMap>

    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {

      return CombinedArcMap<const ForwardMap,

        BackwardMap>(forward, backward);

    }

    template <typename ForwardMap, typename BackwardMap>

    static CombinedArcMap<ForwardMap, const BackwardMap>

    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {

      return CombinedArcMap<ForwardMap,

        const BackwardMap>(forward, backward);

    }

    template <typename ForwardMap, typename BackwardMap>

    static CombinedArcMap<const ForwardMap, const BackwardMap>

    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {

      return CombinedArcMap<const ForwardMap,

        const BackwardMap>(forward, backward);

    /// Its value type is inherited from the first node map type

    /// (\c InNodeMap).

    template <typename InNodeMap, typename OutNodeMap>

      typedef typename InNodeMap::Value Value;

      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;

      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)

      InNodeMap& _in_map;

      OutNodeMap& _out_map;

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<InNodeMap, OutNodeMap>

    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {

      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<const InNodeMap, OutNodeMap>

    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {

      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<InNodeMap, const OutNodeMap>

    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {

      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<const InNodeMap, const OutNodeMap>

    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {

      return CombinedNodeMap<const InNodeMap,

        const OutNodeMap>(in_map, out_map);

    /// Its value type is inherited from the original arc map type

    /// (\c ArcMap).

    template <typename ArcMap, typename NodeMap>

      typedef typename ArcMap::Value Value;

      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;

      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<ArcMap>::ReturnValue Reference;

      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;

      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)

      ArcMap& _arc_map;

      NodeMap& _node_map;

  ///This class implements the \e binary \e heap data structure. A \e heap

  ///is a data structure for storing items with specified values called \e

  ///priorities in such a way that finding the item with minimum priority is

  ///efficient. \c Compare specifies the ordering of the priorities. In a heap

  ///one can change the priority of an item, add or erase an item, etc.

  ///\tparam _Prio Type of the priority of the items.

  ///\tparam _ItemIntMap A read and writable Item int map, used internally

  ///\tparam _Compare A class for the ordering of the priorities. The

  ///default is \c std::less<_Prio>.

  template <typename _Prio, typename _ItemIntMap,

            typename _Compare = std::less<_Prio> >

    typedef _ItemIntMap ItemIntMap;

    typedef _Prio Prio;

    typedef _Compare Compare;

    /// The ItemIntMap \e should be initialized in such way that it maps

    /// PRE_HEAP (-1) to any element to be put in the heap...

      IN_HEAP = 0,

      PRE_HEAP = -1,

      POST_HEAP = -2

    std::vector<Pair> data;

    Compare comp;

    ItemIntMap &iim;

    /// \param _iim should be given to the constructor, since it is used

    /// should be PRE_HEAP (-1) for each element.

    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}

    /// \param _iim should be given to the constructor, since it is used

    /// \param _comp The comparator function object.

    BinHeap(ItemIntMap &_iim, const Compare &_comp)

      : iim(_iim), comp(_comp) {}

    int size() const { return data.size(); }

    bool empty() const { return data.empty(); }

      data.clear();

      return comp(p1.second, p2.second);

      while( hole>0 && less(p,data[par]) ) {

        move(data[par],hole);

        if( less(data[child-1], data[child]) ) {

        if( !less(data[child], p) )

        move(data[child], hole);

      if( child<length && less(data[child], p) ) {

        move(data[child], hole);

      data[i] = p;

      iim.set(p.first, i);

      int n = data.size();

      data.resize(n+1);

      return data[0].first;

      return data[0].second;

      int n = data.size()-1;

      iim.set(data[0].first, POST_HEAP);

        bubble_down(0, data[n], n);

      data.pop_back();

      int h = iim[i];

      int n = data.size()-1;

      iim.set(data[h].first, POST_HEAP);

        if ( bubble_up(h, data[n]) == h) {

          bubble_down(h, data[n], n);

      data.pop_back();

    /// \param i The item.

      int idx = iim[i];

      return data[idx].second;

      int idx = iim[i];

      else if( comp(p, data[idx].second) ) {

        bubble_down(idx, Pair(i,p), data.size());

    /// \param i The item.

    /// \param p The priority.

      int idx = iim[i];

    /// \param i The item.

    /// \param p The priority.

      int idx = iim[i];

      bubble_down(idx, Pair(i,p), data.size());

      int s = iim[i];

        iim[i] = st;

      int idx = iim[i];

      iim.set(i, iim[j]);

      iim.set(j, idx);

      data[idx].first = j;

///\ingroup digraphbits

///\file

///\brief Extenders for the arc set types

  /// \ingroup digraphbits

  ///

  /// \brief Extender for the ArcSets

    /// The arc observer registry.

    /// \brief Gives back the arc alteration notifier.

    ///

    /// Gives back the arc alteration notifier.

    /// \brief Base node of the iterator

    ///

    /// Returns the base node (ie. the source in this case) of the iterator

    /// \brief Running node of the iterator

    ///

    /// Returns the running node (ie. the target in this case) of the

    /// iterator

    /// \brief Base node of the iterator

    ///

    /// Returns the base node (ie. the target in this case) of the iterator

    /// \brief Running node of the iterator

    ///

    /// Returns the running node (ie. the source in this case) of the

    /// iterator

  /// \ingroup digraphbits

  ///

  /// \brief Extender for the EdgeSets

    /// \brief Base node of the iterator

    ///

    /// Returns the base node (ie. the source in this case) of the iterator

    /// \brief Running node of the iterator

    ///

    /// Returns the running node (ie. the target in this case) of the

    /// iterator

    /// \brief Base node of the iterator

    ///

    /// Returns the base node (ie. the target in this case) of the iterator

    /// \brief Running node of the iterator

    ///

    /// Returns the running node (ie. the source in this case) of the

    /// iterator

    /// Base node of the iterator

    ///

    /// Returns the base node of the iterator

    /// Running node of the iterator

    ///

    /// Returns the running node of the iterator

    template <typename _FlowMap>

      typedef _FlowMap FlowMap;

    template <typename _FlowMap>

                           SetFlowMapTraits<_FlowMap> > {

                          SetFlowMapTraits<_FlowMap> > Create;

    template <typename _Elevator>

      typedef _Elevator Elevator;

    template <typename _Elevator>

                           SetElevatorTraits<_Elevator> > {

                          SetElevatorTraits<_Elevator> > Create;

    template <typename _Elevator>

      typedef _Elevator Elevator;

    template <typename _Elevator>

                       SetStandardElevatorTraits<_Elevator> > {

                      SetStandardElevatorTraits<_Elevator> > Create;

    /// so it runs in \f$O(n)\f$ time.

      /// \return the opposite of the given Node on the given Edge

      /// \return the first node of the given Edge.

      /// don't have source and target node. But we use these two methods

      /// to query the two nodes of the arc. The direction of the arc

      /// which arises this way is called the inherent direction of the

      /// \sa direction

    template <char _selector = '0'>

    template <typename _Base = BaseDigraphComponent>

    class IDableDigraphComponent : public _Base {

      typedef _Base Base;

    template <typename _Base = BaseGraphComponent>

    class IDableGraphComponent : public IDableDigraphComponent<_Base> {

      typedef _Base Base;

      using IDableDigraphComponent<_Base>::id;

    template <typename _Graph, typename _Item>

    class GraphItemIt : public _Item {

      explicit GraphItemIt(const _Graph&) {}

          _Item bi = it1;

        _Graph& g;

    /// base class, the _selector is a additional template parameter. For

    /// InArcIt you should instantiate it with character 'i' and for

    template <typename _Graph,

              typename _Item = typename _Graph::Arc,

              typename _Base = typename _Graph::Node,

              char _selector = '0'>

    class GraphIncIt : public _Item {

      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}

      explicit GraphIncIt(const _Graph&, const _Base&) {}

          checkConcept<GraphItem<_selector>, _GraphIncIt>();

          _Item e = it1;

        _Item arc;

        _Base node;

        _Graph graph;