Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

graph_utils.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_GRAPH_UTILS_H
00018 #define LEMON_GRAPH_UTILS_H
00019 
00020 #include <iterator>
00021 
00022 #include <lemon/invalid.h>
00023 #include <lemon/utility.h>
00024 
00032 
00033 
00034 namespace lemon {
00035 
00038 
00044 
00045   template <typename Graph, typename ItemIt>
00046   inline int countItems(const Graph& g) {
00047     int num = 0;
00048     for (ItemIt it(g); it != INVALID; ++it) {
00049       ++num;
00050     }
00051     return num;
00052   }
00053 
00054   // Node counting:
00055 
00056   template <typename Graph>
00057   inline
00058   typename enable_if<typename Graph::NodeNumTag, int>::type
00059   _countNodes(const Graph &g) {
00060     return g.nodeNum();
00061   }
00062 
00063   template <typename Graph>
00064   inline int _countNodes(Wrap<Graph> w) {
00065     return countItems<Graph, typename Graph::NodeIt>(w.value);
00066   }
00067 
00075 
00076   template <typename Graph>
00077   inline int countNodes(const Graph& g) {
00078     return _countNodes<Graph>(g);
00079   }
00080 
00081   // Edge counting:
00082 
00083   template <typename Graph>
00084   inline
00085   typename enable_if<typename Graph::EdgeNumTag, int>::type
00086   _countEdges(const Graph &g) {
00087     return g.edgeNum();
00088   }
00089 
00090   template <typename Graph>
00091   inline int _countEdges(Wrap<Graph> w) {
00092     return countItems<Graph, typename Graph::EdgeIt>(w.value);
00093   }
00094 
00100 
00101   template <typename Graph>
00102   inline int countEdges(const Graph& g) {
00103     return _countEdges<Graph>(g);
00104   }
00105 
00106   // Undirected edge counting:
00107 
00108   template <typename Graph>
00109   inline
00110   typename enable_if<typename Graph::EdgeNumTag, int>::type
00111   _countUndirEdges(const Graph &g) {
00112     return g.undirEdgeNum();
00113   }
00114 
00115   template <typename Graph>
00116   inline int _countUndirEdges(Wrap<Graph> w) {
00117     return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
00118   }
00119 
00125 
00126   template <typename Graph>
00127   inline int countUndirEdges(const Graph& g) {
00128     return _countUndirEdges<Graph>(g);
00129   }
00130 
00131 
00132 
00133   template <typename Graph, typename DegIt>
00134   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
00135     int num = 0;
00136     for (DegIt it(_g, _n); it != INVALID; ++it) {
00137       ++num;
00138     }
00139     return num;
00140   }
00141 
00143 
00160   template <typename Graph>
00161   typename Graph::Edge findEdge(const Graph &g,
00162                 typename Graph::Node u, typename Graph::Node v,
00163                 typename Graph::Edge prev = INVALID) 
00164   {
00165     typename Graph::OutEdgeIt e(g,prev);
00166     //    if(prev==INVALID) g.first(e,u);
00167     if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
00168     else ++e;
00169     while(e!=INVALID && g.target(e)!=v) ++e;
00170     return e;
00171   }
00172   
00174 
00177   template <typename Graph>
00178   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
00179     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
00180   }
00181 
00183 
00186   template <typename Graph>
00187   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
00188     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
00189   }
00190 
00191   // graph copy
00192 
00193   template <
00194     typename DestinationGraph, 
00195     typename SourceGraph, 
00196     typename NodeBijection>
00197   void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 
00198                  NodeBijection& _nb) {    
00199     for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
00200       _nb[it] = _d.addNode();
00201     }
00202   }
00203 
00204   template <
00205     typename DestinationGraph, 
00206     typename SourceGraph, 
00207     typename NodeBijection,
00208     typename EdgeBijection>
00209   void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
00210                  const NodeBijection& _nb, EdgeBijection& _eb) {    
00211     for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
00212       _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
00213     }
00214   }
00215 
00216   template <
00217     typename DestinationGraph, 
00218     typename SourceGraph, 
00219     typename NodeBijection,
00220     typename EdgeBijection>
00221   void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 
00222                  NodeBijection& _nb, EdgeBijection& _eb) {
00223     nodeCopy(_d, _s, _nb);
00224     edgeCopy(_d, _s, _nb, _eb);
00225   }
00226  
00227    template <
00228     typename _DestinationGraph, 
00229     typename _SourceGraph, 
00230     typename _NodeBijection 
00231     =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
00232     typename _EdgeBijection 
00233     =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
00234    >
00235    class GraphCopy {
00236    public:
00237 
00238      typedef _DestinationGraph DestinationGraph;
00239      typedef _SourceGraph SourceGraph;
00240 
00241      typedef _NodeBijection NodeBijection;
00242      typedef _EdgeBijection EdgeBijection;
00243 
00244    protected:          
00245 
00246      NodeBijection node_bijection;
00247      EdgeBijection edge_bijection;     
00248 
00249    public:
00250      
00251      GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
00252        copyGraph(_d, _s, node_bijection, edge_bijection);
00253      }
00254 
00255      const NodeBijection& getNodeBijection() const {
00256        return node_bijection;
00257      }
00258 
00259      const EdgeBijection& getEdgeBijection() const {
00260        return edge_bijection;
00261      }
00262      
00263    };
00264 
00266   
00267 } //END OF NAMESPACE LEMON
00268 
00269 #endif

Generated on Sat Mar 19 10:58:40 2005 for LEMON by  doxygen 1.4.1