1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/graph_utils.h Wed Oct 27 22:38:50 2004 +0000
1.3 @@ -0,0 +1,174 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_GRAPH_UTILS_H
1.21 +#define LEMON_GRAPH_UTILS_H
1.22 +
1.23 +#include <iterator>
1.24 +
1.25 +#include <lemon/invalid.h>
1.26 +
1.27 +///\ingroup utils
1.28 +///\file
1.29 +///\brief Graph utils.
1.30 +///
1.31 +
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 + // counters in the graph
1.36 + /// \brief Function to count the items in the graph.
1.37 + ///
1.38 + /// This function counts the items in the graph.
1.39 + /// The complexity of the function is O(n) because
1.40 + /// it iterates on all of the items.
1.41 +
1.42 + template <typename Graph, typename ItemIt>
1.43 + inline int countItems(const Graph& _g) {
1.44 + int num = 0;
1.45 + for (ItemIt it(_g); it != INVALID; ++it) {
1.46 + ++num;
1.47 + }
1.48 + return num;
1.49 + }
1.50 +
1.51 + /// \brief Function to count the nodes in the graph.
1.52 + ///
1.53 + /// This function counts the nodes in the graph.
1.54 + /// The complexity of the function is O(n) but for some
1.55 + /// graph structure it is specialized to O(1).
1.56 +
1.57 + template <typename Graph>
1.58 + inline int countNodes(const Graph& _g) {
1.59 + return countItems<Graph, typename Graph::NodeIt>(_g);
1.60 + }
1.61 +
1.62 + /// \brief Function to count the edges in the graph.
1.63 + ///
1.64 + /// This function counts the edges in the graph.
1.65 + /// The complexity of the function is O(e) but for some
1.66 + /// graph structure it is specialized to O(1).
1.67 + template <typename Graph>
1.68 + inline int countEdges(const Graph& _g) {
1.69 + return countItems<Graph, typename Graph::EdgeIt>(_g);
1.70 + }
1.71 +
1.72 + /// \brief Function to count the symmetric edges in the graph.
1.73 + ///
1.74 + /// This function counts the symmetric edges in the graph.
1.75 + /// The complexity of the function is O(e) but for some
1.76 + /// graph structure it is specialized to O(1).
1.77 + template <typename Graph>
1.78 + inline int countSymEdges(const Graph& _g) {
1.79 + return countItems<Graph, typename Graph::SymEdgeIt>(_g);
1.80 + }
1.81 +
1.82 + template <typename Graph, typename DegIt>
1.83 + inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
1.84 + int num = 0;
1.85 + for (DegIt it(_g, _n); it != INVALID; ++it) {
1.86 + ++num;
1.87 + }
1.88 + return num;
1.89 + }
1.90 +
1.91 + template <typename Graph>
1.92 + inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
1.93 + return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
1.94 + }
1.95 +
1.96 + template <typename Graph>
1.97 + inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
1.98 + return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
1.99 + }
1.100 +
1.101 + // graph copy
1.102 +
1.103 + template <
1.104 + typename DestinationGraph,
1.105 + typename SourceGraph,
1.106 + typename NodeBijection>
1.107 + void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
1.108 + NodeBijection& _nb) {
1.109 + for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
1.110 + _nb[it] = _d.addNode();
1.111 + }
1.112 + }
1.113 +
1.114 + template <
1.115 + typename DestinationGraph,
1.116 + typename SourceGraph,
1.117 + typename NodeBijection,
1.118 + typename EdgeBijection>
1.119 + void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
1.120 + const NodeBijection& _nb, EdgeBijection& _eb) {
1.121 + for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
1.122 + _eb[it] = _d.addEdge(_nb[_s.tail(it)], _nb[_s.head(it)]);
1.123 + }
1.124 + }
1.125 +
1.126 + template <
1.127 + typename DestinationGraph,
1.128 + typename SourceGraph,
1.129 + typename NodeBijection,
1.130 + typename EdgeBijection>
1.131 + void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
1.132 + NodeBijection& _nb, EdgeBijection& _eb) {
1.133 + nodeCopy(_d, _s, _nb);
1.134 + edgeCopy(_d, _s, _nb, _eb);
1.135 + }
1.136 +
1.137 + template <
1.138 + typename _DestinationGraph,
1.139 + typename _SourceGraph,
1.140 + typename _NodeBijection
1.141 + =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
1.142 + typename _EdgeBijection
1.143 + =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
1.144 + >
1.145 + class GraphCopy {
1.146 + public:
1.147 +
1.148 + typedef _DestinationGraph DestinationGraph;
1.149 + typedef _SourceGraph SourceGraph;
1.150 +
1.151 + typedef _NodeBijection NodeBijection;
1.152 + typedef _EdgeBijection EdgeBijection;
1.153 +
1.154 + protected:
1.155 +
1.156 + NodeBijection node_bijection;
1.157 + EdgeBijection edge_bijection;
1.158 +
1.159 + public:
1.160 +
1.161 + GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
1.162 + copyGraph(_d, _s, node_bijection, edge_bijection);
1.163 + }
1.164 +
1.165 + const NodeBijection& getNodeBijection() const {
1.166 + return node_bijection;
1.167 + }
1.168 +
1.169 + const EdgeBijection& getEdgeBijection() const {
1.170 + return edge_bijection;
1.171 + }
1.172 +
1.173 + };
1.174 +
1.175 +}
1.176 +
1.177 +#endif