/* -*- C++ -*-

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

  *

  * Copyright (C) 2004 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>

 ///\ingroup utils

 ///\file

 ///\brief Graph utils.

 ///

 namespace lemon {

   // counters in the graph

   /// \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;

   }

   /// \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 O(1).

   template <typename Graph>

   inline int countNodes(const Graph& _g) {

     return countItems<Graph, typename Graph::NodeIt>(_g);

   }

   /// \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 O(1).

   template <typename Graph>

   inline int countEdges(const Graph& _g) {

     return countItems<Graph, typename Graph::EdgeIt>(_g);

   }

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

   ///

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

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

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

   template <typename Graph>

   inline int countSymEdges(const Graph& _g) {

     return countItems<Graph, typename Graph::SymEdgeIt>(_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;

   }

   template <typename Graph>

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

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

   }

   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.tail(it)], _nb[_s.head(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;

      }

    };

 }

 #endif