00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
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
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
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
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
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
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 }
00268
00269 #endif