RhodeCode

   useful when the COIN-OR headers and libraries are not under the

   same prefix (which is unlikely).

--without-coin

   Disable COIN-OR support.

    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/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}

  )

DOC_EPS_IMAGES27 = \

	bipartite_matching.eps \

	bipartite_partitions.eps \

	connected_components.eps \

	edge_biconnected_components.eps \

	node_biconnected_components.eps \

	strongly_connected_components.eps

DOC_EPS_IMAGES = \

	$(DOC_EPS_IMAGES18) \

	$(DOC_EPS_IMAGES27)

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// The default type is \ref ListDigraph.

  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  /// the lengths of the arcs. The default map type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=BellmanFordDefaultTraits<GR,LEN> >

  /// \ref BellmanFord "Bellman-Ford" algorithm.

  /// It does not have own \ref run() method, it uses the

  /// functions and features of the plain \ref BellmanFord.

  ///

  /// This class should only be used through the \ref bellmanFord()

  /// function, which makes it easier to use the algorithm.

  template<class TR>

  class BellmanFordWizard : public TR {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  ///There is also a \ref bfs() "function-type interface" for the BFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Bfs.

  ///

  /// This class should only be used through the \ref bfs() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class BfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  /// The value of GR is not used directly by \ref BfsVisit,

  /// it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = BfsVisitor<GR>,

            typename TR = BfsVisitDefaultTraits<GR> >

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

#ifdef DOXYGEN

     \tparam LM The type of the lower bound map. The default

     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

     \tparam UM The type of the upper bound (capacity) map.

     The default map type is \c LM.

     \tparam SM The type of the supply map. The default map type is

     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".

  */

#ifdef DOXYGEN

template< typename GR,

          typename LM,

          typename UM,

          typename SM,

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

  ///

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// \brief The large cost type

    ///

    /// The large cost type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeCost LargeCost;

    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  ///There is also a \ref dfs() "function-type interface" for the DFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=DfsDefaultTraits<GR> >

  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Dfs.

  ///

  /// This class should only be used through the \ref dfs() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class DfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  /// The value of GR is not used directly by \ref DfsVisit,

  /// it is only passed to \ref DfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which

  /// does not observe the DFS events. If you want to observe the DFS

  /// events, you should implement your own visitor class.

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = DfsVisitor<GR>,

            typename TR = DfsVisitDefaultTraits<GR> >

  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  ///the lengths of the arcs.

  ///It is read once for each arc, so the map may involve in

  ///relatively time consuming process to compute the arc lengths if

  ///it is necessary. The default map type is \ref

  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=DijkstraDefaultTraits<GR,LEN> >

  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Dijkstra.

  ///

  /// This class should only be used through the \ref dijkstra() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class DijkstraWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  /// it applies an efficient early termination scheme.

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

  /// minimum mean cycle problem, though the best known theoretical

  /// bound on its running time is exponential.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = HowardDefaultTraits<GR, LEN> >

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

  /// \ref amo93networkflows, \ref dasdan98minmeancycle.

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = KarpDefaultTraits<GR, LEN> >

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

  /// \param GR The digraph type the algorithm runs on.

  /// \param CM A read-only arc map storing the costs of the

  /// arcs. It is read once for each arc, so the map may involve in

  /// relatively time consuming process to compute the arc costs if

  /// it is necessary. The default map type is \ref

  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".

  /// "MinCostArborescenceDefaultTraits<GR, CM>".

#ifndef DOXYGEN

  template <typename GR,

            typename CM = typename GR::template ArcMap<int>,

            typename TR =

              MinCostArborescenceDefaultTraits<GR, CM> >

#else

#endif

  class MinCostArborescence {

  public:

    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 

    /// of the algorithm. 

  /// \ingroup planar

  ///

  /// \brief Planarity checking of an undirected simple graph

  ///

  /// This function implements the Boyer-Myrvold algorithm for

  /// version of the PlanarEmbedding algorithm class because neither

  template <typename GR>

  bool checkPlanarity(const GR& graph) {

    _planarity_bits::PlanarityChecking<GR> pc(graph);

    return pc.run();

  }

  /// \ingroup planar

  ///

  /// \brief Planar embedding of an undirected simple graph

  ///

  /// This class implements the Boyer-Myrvold algorithm for planar

  /// ordering of the outgoing edges of the nodes, which is a possible

  /// configuration to draw the graph in the plane. If there is not

  ///

  /// The current implementation calculates either an embedding or a

  template <typename Graph>

  class PlanarEmbedding {

  private:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

      ROOT = 10, PERTINENT = 11,

      INTERNAL = 12

    };

  public:

    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;

    /// \brief Constructor

    ///

    PlanarEmbedding(const Graph& graph)

      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}

    ///

    /// algorithm does not compute a Kuratowski subdivision.

    bool run(bool kuratowski = true) {

      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;

      PredMap pred_map(_graph, INVALID);

      TreeMap tree_map(_graph, false);

                       arc_lists, flip_map);

      }

      return true;

    }

    ///

    /// possible to query the cyclic order of the outgoing arcs from

    /// a node.

    Arc next(const Arc& arc) const {

      return _embedding[arc];

    }

    ///

    const EmbeddingMap& embeddingMap() const {

      return _embedding;

    }

    ///

      return _kuratowski[edge];

    }

  private:

    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,

  /// \ingroup planar

  ///

  /// \brief Schnyder's planar drawing algorithm

  ///

  /// The planar drawing algorithm calculates positions for the nodes

  /// each other.

  ///

  /// The time complexity of the algorithm is O(n).

  template <typename Graph>

  class PlanarDrawing {

  public:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    typedef dim2::Point<int> Point;

    typedef typename Graph::template NodeMap<Point> PointMap;

    /// \brief Constructor

    ///

    /// Constructor

    PlanarDrawing(const Graph& graph)

      : _graph(graph), _point_map(graph) {}

  private:

    template <typename AuxGraph, typename AuxEmbeddingMap>

      }

    }

  public:

    ///

    bool run() {

      PlanarEmbedding<Graph> pe(_graph);

      if (!pe.run()) return false;

      run(pe);

      return true;

    }

    /// combinatorical embedding

    ///

    template <typename EmbeddingMap>

    void run(const EmbeddingMap& embedding) {

      typedef SmartEdgeSet<Graph> AuxGraph;

      if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {

        drawing(_graph, embedding, _point_map);

      _planarity_bits::makeMaxPlanar(aux_graph, aux_embedding);

      drawing(aux_graph, aux_embedding, _point_map);

    }

    /// \brief The coordinate of the given node

    ///

    Point operator[](const Node& node) const {

      return _point_map[node];

    }

    ///

    const PointMap& coords() const {

      return _point_map;

    }

  private:

  /// \ingroup planar

  ///

  /// \brief Coloring planar graphs

  ///

  /// The graph coloring problem is the coloring of the graph nodes

  /// time algorithm for four coloring, but it could not be used to

  /// quadratic worst case time complexity. The two coloring (if

  /// possible) is solvable with a graph search algorithm and it is

  /// implemented in \ref bipartitePartitions() function in LEMON. To

  ///

  /// This class contains member functions for calculate colorings

  /// with five and six colors. The six coloring algorithm is a simple

  /// greedy coloring on the backward minimum outgoing order of nodes.

  /// guarantees that when a node is chosen for coloring it has at

  /// most five already colored adjacents. The five coloring algorithm

  /// use the same method, but if the greedy approach fails to color

  /// with five colors, i.e. the node has five already different

  /// colored neighbours, it swaps the colors in one of the connected

  /// two colored sets with the Kempe recoloring method.

  template <typename Graph>

  class PlanarColoring {

  public:

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

    typedef typename Graph::template NodeMap<int> IndexMap;

    typedef ComposeMap<Palette, IndexMap> ColorMap;

    /// \brief Constructor

    ///

    PlanarColoring(const Graph& graph)

      : _graph(graph), _color_map(graph), _palette(0) {

      _palette.add(Color(1,0,0));

      _palette.add(Color(0,1,0));

      _palette.add(Color(0,0,1));

      _palette.add(Color(1,1,0));

      _palette.add(Color(1,0,1));

      _palette.add(Color(0,1,1));

    }

    ///

    IndexMap colorIndexMap() const {

      return _color_map;

    }

    ///

    ColorMap colorMap() const {

      return composeMap(_palette, _color_map);

    }

    ///

    int colorIndex(const Node& node) const {

      return _color_map[node];

    }

    ///

    Color color(const Node& node) const {

      return _palette[_color_map[node]];

    }

    ///

    /// This function calculates a coloring with at most six colors. The time

    /// complexity of this variant is linear in the size of the graph.

    bool runSixColoring() {

      typename Graph::template NodeMap<int> heap_index(_graph, -1);

      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);

      for (NodeIt n(_graph); n != INVALID; ++n) {

        _color_map[node] = color;

      }

    }

  public:

    ///

    /// This function calculates a coloring with at most five

    /// colors. The worst case time complexity of this variant is

    /// quadratic in the size of the graph.