RhodeCode

/**

@defgroup datas Data Structures

*/

/**

@ingroup graphs

\brief Graph types between real graphs and graph adaptors.

These classes wrap graphs to give new functionality as the adaptors do it.

On the other hand they are not light-weight structures as the adaptors.

*/

@ingroup datas

\brief Map structures implemented in LEMON.

LEMON provides several special purpose maps and map adaptors that e.g. combine

new maps from existing ones.

@ingroup maps

\brief Special graph-related maps.

values to the nodes and arcs/edges of graphs.

If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,

\ingroup maps

\brief Tools to create new maps from existing ones

maps from other maps.

Most of them are \ref concepts::ReadMap "read-only maps".

@ingroup datas

\brief Two dimensional data storages implemented in LEMON.

*/

/**

@ingroup datas

\brief %Path structures implemented in LEMON.

LEMON provides flexible data structures to work with paths.

All of them have similar interfaces and they can be copied easily with

@ingroup datas

\brief Auxiliary data structures implemented in LEMON.

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup algs Algorithms

implemented in LEMON.

implemented in LEMON.

*/

@ingroup algs

\brief Common graph search algorithms.

\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).

*/

@ingroup algs

\brief Algorithms for finding shortest paths.

 - \ref Dijkstra algorithm for finding shortest paths from a source node

   when all arc lengths are non-negative.

@ingroup algs

\brief Algorithms for finding maximum flows.

feasible circulations.

The \e maximum \e flow \e problem is to find a flow of maximum value between

\brief Algorithms for finding minimum cost flows and circulations.

circulations.

The \e minimum \e cost \e flow \e problem is to find a feasible flow of

\brief Algorithms for finding minimum cut in graphs.

The \e minimum \e cut \e problem is to find a non-empty and non-complete

\f$X\f$ subset of the nodes with minimum overall capacity on

  in directed graphs.

- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for

  calculating minimum cut in undirected graphs.

  all-pairs minimum cut in undirected graphs.

If you want to find minimum cut just between two distinict nodes,

@ingroup algs

\brief Algorithms for discovering the graph properties

like connectivity, bipartiteness, euler property, simplicity etc.

\image html edge_biconnected_components.png

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

embedding and drawing.

\image html planar.png

@ingroup algs

\brief Algorithms for finding a minimum cost spanning tree in a graph.

tree in a graph.

*/

@ingroup algs

\brief Auxiliary algorithms implemented in LEMON.

in order to make it easier to implement complex algorithms.

*/

@ingroup algs

\brief Approximation algorithms.

implemented in LEMON.

*/

/**

@defgroup gen_opt_group General Optimization Tools

implemented in LEMON.

implemented in LEMON.

*/

@ingroup gen_opt_group

\brief Lp and Mip solver interfaces for LEMON.

various LP solvers could be used in the same manner with this

interface.

*/

@ingroup gen_opt_group

\brief Metaheuristics for LEMON library.

*/

/**

@ingroup utils

\brief Simple basic graph utilities.

*/

/**

@ingroup utils

\brief Tools for development, debugging and testing.

debugging and testing.

*/

@ingroup misc

\brief Simple tools for measuring the performance of algorithms.

of algorithms.

*/

@ingroup utils

\brief Exceptions defined in LEMON.

*/

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

and graph related data. Now it supports the \ref lgf-format

"LEMON Graph Format", the \c DIMACS format and the encapsulated

postscript (EPS) format.

@ingroup io_group

\brief Reading and writing LEMON Graph Format.

\ref lgf-format "LEMON Graph Format".

*/

@ingroup io_group

\brief General \c EPS drawer and graph exporter

graph exporting tools.

*/

@defgroup concept Concepts

\brief Skeleton classes and concept checking classes

classes implemented in LEMON.

The purpose of the classes in this group is fourfold.

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

graph structures and helper classes used to implement these.

*/

@ingroup concept

\brief Skeleton and concept checking classes for maps

*/

/**

take a look at our \ref quicktour

"Quick Tour to LEMON" which will guide you along.

If you know what you are looking for then try to find it under the

If you are a user of the old (0.x) series of LEMON, please check out the

\ref migration "Migration Guide" for the backward incompatibilities.

    ///

    /// This map adaptor class adapts two arc maps of the underlying

    /// digraph to get an arc map of the undirected graph.

    class CombinedArcMap {

    public:

      /// The key type of the map

      typedef typename Parent::Arc Key;

      /// The value type of the map

      /// Constructor

        : _forward(&forward), _backward(&backward) {}

      /// Sets the value associated with the given key.

    protected:

    };

    /// \brief Returns a combined arc map

    ///

    /// This function just returns a combined arc map.

    }

  };

    ///

    /// This map adaptor class adapts two node maps of the original digraph

    /// to get a node map of the split digraph.

    class CombinedNodeMap {

    public:

      /// The key type of the map

      typedef Node Key;

      /// The value type of the map

      /// Constructor

        : _in_map(in_map), _out_map(out_map) {}

      /// Returns the value associated with the given key.

    private:

    };

    /// \brief Returns a combined node map

    ///

    /// This function just returns a combined node map.

    }

    /// \brief Arc map combined from an arc map and a node map of the

    ///

    /// This map adaptor class adapts an arc map and a node map of the

    /// original digraph to get an arc map of the split digraph.

    class CombinedArcMap {

    public:

      /// The key type of the map

      typedef Arc Key;

      /// The value type of the map

      /// Constructor

        : _arc_map(arc_map), _node_map(node_map) {}

      /// Returns the value associated with the given key.

      }

    private:

    };

    /// \brief Returns a combined arc map

  ///

  ///\brief A Binary Heap implementation.

  ///

  ///

  ///to handle the cross references.

  ///

  ///\sa FibHeap

  ///\sa Dijkstra

  class BinHeap {

  public:

    ///\e

    ///\e

    ///\e

    typedef typename ItemIntMap::Key Item;

    ///\e

    typedef std::pair<Item,Prio> Pair;

    ///\e

    /// \brief Type to represent the items states.

    ///

    /// "pre heap" or "post heap". The latter two are indifferent from the

    /// heap's point of view, but may be useful to the user.

    ///

    enum State {

    };

  private:

  public:

    /// \brief The constructor.

    ///

    /// The constructor.

    /// internally to handle the cross references. The value of the map

    /// \brief The constructor.

    ///

    /// The constructor.

    /// internally to handle the cross references. The value of the map

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

    ///

    /// The number of items stored in the heap.

    ///

    /// \brief Returns the number of items stored in the heap.

    /// \brief Checks if the heap stores no items.

    ///

    /// Returns \c true if and only if the heap stores no items.

    /// \brief Make empty this heap.

    ///

    /// the heap and after that you should set the cross reference map for

    /// each item to \c PRE_HEAP.

    void clear() {

    }

  private:

    static int second_child(int i) { return 2*i+2; }

    bool less(const Pair &p1, const Pair &p2) const {

    }

    int bubble_up(int hole, Pair p) {

      int par = parent(hole);

        hole = par;

        par = parent(hole);

      }

    int bubble_down(int hole, Pair p, int length) {

      int child = second_child(hole);

      while(child < length) {

          --child;

        }

          goto ok;

        hole = child;

        child = second_child(hole);

      }

      child--;

        hole=child;

      }

    ok:

    }

    void move(const Pair &p, int i) {

    }

  public:

    /// Adds \c p.first to the heap with priority \c p.second.

    /// \param p The pair to insert.

    void push(const Pair &p) {

      bubble_up(n, p);

    }

    /// Compare.

    /// \pre The heap must be nonempty.

    Item top() const {

    }

    /// \brief Returns the minimum priority relative to \c Compare.

    /// It returns the minimum priority relative to \c Compare.

    /// \pre The heap must be nonempty.

    Prio prio() const {

    }

    /// \brief Deletes the item with minimum priority relative to \c Compare.

    /// Compare from the heap.

    /// \pre The heap must be non-empty.

    void pop() {

      if (n > 0) {

      }

    }

    /// \brief Deletes \c i from the heap.

    /// \param i The item to erase.

    /// \pre The item should be in the heap.

    void erase(const Item &i) {

      if( h < n ) {

        }

      }

    }

    /// \brief Returns the priority of \c i.

    ///

    /// This function returns the priority of item \c i.

    /// \pre \c i must be in the heap.

    Prio operator[](const Item &i) const {

    }

    /// \brief \c i gets to the heap with priority \c p independently

    /// \param i The item.

    /// \param p The priority.

    void set(const Item &i, const Prio &p) {

      if( idx < 0 ) {

        push(i,p);

      }

        bubble_up(idx, Pair(i,p));

      }

      else {

      }

    }

    /// \brief Decreases the priority of \c i to \c p.

    ///

    /// This method decreases the priority of item \c i to \c p.

    /// \pre \c i must be stored in the heap with priority at least \c

    /// p relative to \c Compare.

    void decrease(const Item &i, const Prio &p) {

      bubble_up(idx, Pair(i,p));

    }

    /// \brief Increases the priority of \c i to \c p.

    ///

    /// This method sets the priority of item \c i to \c p.

    /// \pre \c i must be stored in the heap with priority at most \c

    /// p relative to \c Compare.

    void increase(const Item &i, const Prio &p) {

    }

    /// \brief Returns if \c item is in, has already been in, or has

    /// get back to the heap again.

    /// \param i The item.

    State state(const Item &i) const {

      if( s>=0 )

        s=0;

      return State(s);

        if (state(i) == IN_HEAP) {

          erase(i);

        }

        break;

      case IN_HEAP:

        break;

    /// \c i item will out of the heap and \c j will be in the heap

    /// with the same prioriority as prevoiusly the \c i item.

    void replace(const Item& i, const Item& j) {

    }

  }; // class BinHeap

#include <lemon/bits/default_map.h>

#include <lemon/bits/map_extender.h>

namespace lemon {

  template <typename Base>

  class ArcSetExtender : public Base {

  public:

    // Alteration notifier extensions

    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;

  protected:

    using Parent::notifier;

    ArcNotifier& notifier(Arc) const {

      return arc_notifier;

    }

    };

    Node baseNode(const OutArcIt &e) const {

      return Parent::source(static_cast<const Arc&>(e));

    }

    Node runningNode(const OutArcIt &e) const {

      return Parent::target(static_cast<const Arc&>(e));

    }

    Node baseNode(const InArcIt &e) const {

      return Parent::target(static_cast<const Arc&>(e));

    }

    Node runningNode(const InArcIt &e) const {

      return Parent::source(static_cast<const Arc&>(e));

    }

  };

  template <typename Base>

  class EdgeSetExtender : public Base {

      }

    };

    Node baseNode(const OutArcIt &e) const {

      return Parent::source(static_cast<const Arc&>(e));