/* -*- C++ -*-

  * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_GRAPH_UTILS_H

 #define LEMON_GRAPH_UTILS_H

 #include <iterator>

 #include <lemon/invalid.h>

 #include <lemon/utility.h>

 #include <lemon/map_utils.h>

 ///\ingroup gutils

 ///\file

 ///\brief Graph utilities.

 ///

 ///\todo Please

 ///revise the documentation.

 ///

 namespace lemon {

 /// \addtogroup gutils

 /// @{

   /// \brief Function to count the items in the graph.

   ///

   /// This function counts the items in the graph.

   /// The complexity of the function is O(n) because

   /// it iterates on all of the items.

   template <typename Graph, typename ItemIt>

   inline int countItems(const Graph& g) {

     int num = 0;

     for (ItemIt it(g); it != INVALID; ++it) {

       ++num;

     }

     return num;

   }

   // Node counting:

   template <typename Graph>

   inline

   typename enable_if<typename Graph::NodeNumTag, int>::type

   _countNodes(const Graph &g) {

     return g.nodeNum();

   }

   template <typename Graph>

   inline int _countNodes(Wrap<Graph> w) {

     return countItems<Graph, typename Graph::NodeIt>(w.value);

   }

   /// \brief Function to count the nodes in the graph.

   ///

   /// This function counts the nodes in the graph.

   /// The complexity of the function is O(n) but for some

   /// graph structure it is specialized to run in O(1).

   ///

   /// \todo refer how to specialize it

   template <typename Graph>

   inline int countNodes(const Graph& g) {

     return _countNodes<Graph>(g);

   }

   // Edge counting:

   template <typename Graph>

   inline

   typename enable_if<typename Graph::EdgeNumTag, int>::type

   _countEdges(const Graph &g) {

     return g.edgeNum();

   }

   template <typename Graph>

   inline int _countEdges(Wrap<Graph> w) {

     return countItems<Graph, typename Graph::EdgeIt>(w.value);

   }

   /// \brief Function to count the edges in the graph.

   ///

   /// This function counts the edges in the graph.

   /// The complexity of the function is O(e) but for some

   /// graph structure it is specialized to run in O(1).

   template <typename Graph>

   inline int countEdges(const Graph& g) {

     return _countEdges<Graph>(g);

   }

   // Undirected edge counting:

   template <typename Graph>

   inline

   typename enable_if<typename Graph::EdgeNumTag, int>::type

   _countUndirEdges(const Graph &g) {

     return g.undirEdgeNum();

   }

   template <typename Graph>

   inline int _countUndirEdges(Wrap<Graph> w) {

     return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);

   }

   /// \brief Function to count the edges in the graph.

   ///

   /// This function counts the edges in the graph.

   /// The complexity of the function is O(e) but for some

   /// graph structure it is specialized to run in O(1).

   template <typename Graph>

   inline int countUndirEdges(const Graph& g) {

     return _countUndirEdges<Graph>(g);

   }

   template <typename Graph, typename DegIt>

   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {

     int num = 0;

     for (DegIt it(_g, _n); it != INVALID; ++it) {

       ++num;

     }

     return num;

   }

   /// Finds an edge between two nodes of a graph.

   /// Finds an edge from node \c u to node \c v in graph \c g.

   ///

   /// If \c prev is \ref INVALID (this is the default value), then

   /// it finds the first edge from \c u to \c v. Otherwise it looks for

   /// the next edge from \c u to \c v after \c prev.

   /// \return The found edge or \ref INVALID if there is no such an edge.

   ///

   /// Thus you can iterate through each edge from \c u to \c v as it follows.

   /// \code

   /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {

   ///   ...

   /// }

   /// \endcode

   /// \todo We may want to use the \ref concept::GraphBase "GraphBase"

   /// interface here...

   /// \bug Untested ...

   template <typename Graph>

   typename Graph::Edge findEdge(const Graph &g,

 		typename Graph::Node u, typename Graph::Node v,

 		typename Graph::Edge prev = INVALID) 

   {

     typename Graph::OutEdgeIt e(g,prev);

     //    if(prev==INVALID) g.first(e,u);

     if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);

     else ++e;

     while(e!=INVALID && g.target(e)!=v) ++e;

     return e;

   }

   ///\e

   ///\todo Please document.

   ///

   template <typename Graph>

   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {

     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);

   }

   ///\e

   ///\todo Please document.

   ///

   template <typename Graph>

   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {

     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);

   }

   // graph copy

   template <

     typename DestinationGraph, 

     typename SourceGraph, 

     typename NodeBijection>

   void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 

 		 NodeBijection& _nb) {    

     for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {

       _nb[it] = _d.addNode();

     }

   }

   template <

     typename DestinationGraph, 

     typename SourceGraph, 

     typename NodeBijection,

     typename EdgeBijection>

   void copyEdges(DestinationGraph& _d, const SourceGraph& _s,

 		 const NodeBijection& _nb, EdgeBijection& _eb) {    

     for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {

       _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);

     }

   }

   template <

     typename DestinationGraph, 

     typename SourceGraph, 

     typename NodeBijection,

     typename EdgeBijection>

   void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 

 		 NodeBijection& _nb, EdgeBijection& _eb) {

     nodeCopy(_d, _s, _nb);

     edgeCopy(_d, _s, _nb, _eb);

   }

    template <

     typename _DestinationGraph, 

     typename _SourceGraph, 

     typename _NodeBijection 

     =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,

     typename _EdgeBijection 

     =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>

    >

    class GraphCopy {

    public:

      typedef _DestinationGraph DestinationGraph;

      typedef _SourceGraph SourceGraph;

      typedef _NodeBijection NodeBijection;

      typedef _EdgeBijection EdgeBijection;

    protected:          

      NodeBijection node_bijection;

      EdgeBijection edge_bijection;     

    public:

      GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {

        copyGraph(_d, _s, node_bijection, edge_bijection);

      }

      const NodeBijection& getNodeBijection() const {

        return node_bijection;

      }

      const EdgeBijection& getEdgeBijection() const {

        return edge_bijection;

      }

    };

   template <typename _Graph>

   class GraphNodeSet {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Node Item;

     typedef typename Graph::NodeIt ItemIt;

     template <typename _Value>

     class Map : public Graph::template NodeMap<_Value> {

     public:

       typedef typename Graph::template NodeMap<_Value> Parent; 

       typedef typename Parent::Value Value;

       Map(const Graph& _graph) : Parent(_graph) {}

       Map(const Graph& _graph, const Value& _value) 

 	: Parent(_graph, _value) {}

     };

     typedef IdMap<Graph, Item> IdMap;

   private:

     Graph* graph;

   };

   template <typename _Graph>

   class GraphEdgeSet {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Edge Item;

     typedef typename Graph::EdgeIt ItemIt;

     template <typename _Value>

     class Map : public Graph::template EdgeMap<_Value> {

     public:

       typedef typename Graph::template EdgeMap<_Value> Parent; 

       typedef typename Parent::Value Value;

       Map(const Graph& _graph) : Parent(_graph) {}

       Map(const Graph& _graph, const Value& _value) 

 	: Parent(_graph, _value) {}

     };

     typedef IdMap<Graph, Item> IdMap;

   private:

     Graph* graph;

   };

   /// @}

 } //END OF NAMESPACE LEMON

 #endif