1.1 --- a/lemon/graph_utils.h Mon Jul 04 13:08:31 2005 +0000
1.2 +++ b/lemon/graph_utils.h Mon Jul 04 13:10:34 2005 +0000
1.3 @@ -143,6 +143,25 @@
1.4 return num;
1.5 }
1.6
1.7 + /// \brief Function to count the number of the out-edges from node \c n.
1.8 + ///
1.9 + /// This function counts the number of the out-edges from node \c n
1.10 + /// in the graph.
1.11 + template <typename Graph>
1.12 + inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
1.13 + return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
1.14 + }
1.15 +
1.16 + /// \brief Function to count the number of the in-edges to node \c n.
1.17 + ///
1.18 + /// This function counts the number of the in-edges to node \c n
1.19 + /// in the graph.
1.20 + template <typename Graph>
1.21 + inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
1.22 + return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
1.23 + }
1.24 +
1.25 +
1.26 /// Finds an edge between two nodes of a graph.
1.27
1.28 /// Finds an edge from node \c u to node \c v in graph \c g.
1.29 @@ -173,99 +192,174 @@
1.30 while(e!=INVALID && g.target(e)!=v) ++e;
1.31 return e;
1.32 }
1.33 -
1.34 - /// \brief Function to count the number of the out-edges from node \c n.
1.35 +
1.36 + /// \brief Copy the source map to the target map.
1.37 ///
1.38 - /// This function counts the number of the out-edges from node \c n
1.39 - /// in the graph.
1.40 - template <typename Graph>
1.41 - inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
1.42 - return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
1.43 - }
1.44 -
1.45 - /// \brief Function to count the number of the in-edges to node \c n.
1.46 - ///
1.47 - /// This function counts the number of the in-edges to node \c n
1.48 - /// in the graph.
1.49 - template <typename Graph>
1.50 - inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
1.51 - return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
1.52 - }
1.53 -
1.54 - // graph copy
1.55 -
1.56 - template <
1.57 - typename DestinationGraph,
1.58 - typename SourceGraph,
1.59 - typename NodeBijection>
1.60 - void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
1.61 - NodeBijection& _nb) {
1.62 - for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
1.63 - _nb[it] = _d.addNode();
1.64 + /// Copy the \c source map to the \c target map. It uses the given iterator
1.65 + /// to iterate on the data structure and it use the \c ref mapping to
1.66 + /// convert the source's keys to the target's keys.
1.67 + template <typename Target, typename Source,
1.68 + typename ItemIt, typename Ref>
1.69 + void copyMap(Target& target, const Source& source,
1.70 + ItemIt it, const Ref& ref) {
1.71 + for (; it != INVALID; ++it) {
1.72 + target[ref[it]] = source[it];
1.73 }
1.74 }
1.75
1.76 - template <
1.77 - typename DestinationGraph,
1.78 - typename SourceGraph,
1.79 - typename NodeBijection,
1.80 - typename EdgeBijection>
1.81 - void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
1.82 - const NodeBijection& _nb, EdgeBijection& _eb) {
1.83 - for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
1.84 - _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
1.85 + /// \brief Copy the source map to the target map.
1.86 + ///
1.87 + /// Copy the \c source map to the \c target map. It uses the given iterator
1.88 + /// to iterate on the data structure.
1.89 + template <typename Target, typename Source,
1.90 + typename ItemIt>
1.91 + void copyMap(Target& target, const Source& source, ItemIt it) {
1.92 + for (; it != INVALID; ++it) {
1.93 + target[it] = source[it];
1.94 }
1.95 }
1.96
1.97 - template <
1.98 - typename DestinationGraph,
1.99 - typename SourceGraph,
1.100 - typename NodeBijection,
1.101 - typename EdgeBijection>
1.102 - void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
1.103 - NodeBijection& _nb, EdgeBijection& _eb) {
1.104 - nodeCopy(_d, _s, _nb);
1.105 - edgeCopy(_d, _s, _nb, _eb);
1.106 - }
1.107 -
1.108 - template <
1.109 - typename _DestinationGraph,
1.110 - typename _SourceGraph,
1.111 - typename _NodeBijection
1.112 - =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
1.113 - typename _EdgeBijection
1.114 - = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
1.115 - >
1.116 +
1.117 + /// \brief Class to copy a graph to an other graph.
1.118 + ///
1.119 + /// Class to copy a graph to an other graph. It can be used easier
1.120 + /// with the \c copyGraph() function.
1.121 + template <typename Target, typename Source>
1.122 class GraphCopy {
1.123 - public:
1.124 -
1.125 - typedef _DestinationGraph DestinationGraph;
1.126 - typedef _SourceGraph SourceGraph;
1.127 + public:
1.128 + typedef typename Source::Node Node;
1.129 + typedef typename Source::NodeIt NodeIt;
1.130 + typedef typename Source::Edge Edge;
1.131 + typedef typename Source::EdgeIt EdgeIt;
1.132
1.133 - typedef _NodeBijection NodeBijection;
1.134 - typedef _EdgeBijection EdgeBijection;
1.135 -
1.136 - protected:
1.137 -
1.138 - NodeBijection node_bijection;
1.139 - EdgeBijection edge_bijection;
1.140 + typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
1.141 + typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
1.142
1.143 - public:
1.144 -
1.145 - GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
1.146 - copyGraph(_d, _s, node_bijection, edge_bijection);
1.147 - }
1.148 -
1.149 - const NodeBijection& getNodeBijection() const {
1.150 - return node_bijection;
1.151 + /// \brief Constructor for the GraphCopy.
1.152 + ///
1.153 + /// It copies the content of the \c _source graph into the
1.154 + /// \c _target graph. It creates also two references, one beetween
1.155 + /// the two nodeset and one beetween the two edgesets.
1.156 + GraphCopy(Target& _target, const Source& _source)
1.157 + : source(_source), target(_target),
1.158 + nodeRefMap(_source), edgeRefMap(_source) {
1.159 + for (NodeIt it(source); it != INVALID; ++it) {
1.160 + nodeRefMap[it] = target.addNode();
1.161 + }
1.162 + for (EdgeIt it(source); it != INVALID; ++it) {
1.163 + edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.164 + nodeRefMap[source.target(it)]);
1.165 + }
1.166 }
1.167
1.168 - const EdgeBijection& getEdgeBijection() const {
1.169 - return edge_bijection;
1.170 + /// \brief Copies the node references into the given map.
1.171 + ///
1.172 + /// Copies the node references into the given map.
1.173 + template <typename NodeRef>
1.174 + const GraphCopy& nodeRef(NodeRef& map) const {
1.175 + for (NodeIt it(source); it != INVALID; ++it) {
1.176 + map.set(it, nodeRefMap[it]);
1.177 + }
1.178 + return *this;
1.179 }
1.180 -
1.181 +
1.182 + /// \brief Reverse and copies the node references into the given map.
1.183 + ///
1.184 + /// Reverse and copies the node references into the given map.
1.185 + template <typename NodeRef>
1.186 + const GraphCopy& nodeCrossRef(NodeRef& map) const {
1.187 + for (NodeIt it(source); it != INVALID; ++it) {
1.188 + map.set(nodeRefMap[it], it);
1.189 + }
1.190 + return *this;
1.191 + }
1.192 +
1.193 + /// \brief Copies the edge references into the given map.
1.194 + ///
1.195 + /// Copies the edge references into the given map.
1.196 + template <typename EdgeRef>
1.197 + const GraphCopy& edgeRef(EdgeRef& map) const {
1.198 + for (EdgeIt it(source); it != INVALID; ++it) {
1.199 + map.set(it, edgeRefMap[it]);
1.200 + }
1.201 + return *this;
1.202 + }
1.203 +
1.204 + /// \brief Reverse and copies the edge references into the given map.
1.205 + ///
1.206 + /// Reverse and copies the edge references into the given map.
1.207 + template <typename EdgeRef>
1.208 + const GraphCopy& edgeCrossRef(EdgeRef& map) const {
1.209 + for (EdgeIt it(source); it != INVALID; ++it) {
1.210 + map.set(edgeRefMap[it], it);
1.211 + }
1.212 + return *this;
1.213 + }
1.214 +
1.215 + /// \brief Make copy of the given map.
1.216 + ///
1.217 + /// Makes copy of the given map for the newly created graph.
1.218 + /// The new map's key type is the target graph's node type,
1.219 + /// and the copied map's key type is the source graph's node
1.220 + /// type.
1.221 + template <typename TargetMap, typename SourceMap>
1.222 + const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
1.223 + copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
1.224 + return *this;
1.225 + }
1.226 +
1.227 + /// \brief Make copy of the given map.
1.228 + ///
1.229 + /// Makes copy of the given map for the newly created graph.
1.230 + /// The new map's key type is the target graph's edge type,
1.231 + /// and the copied map's key type is the source graph's edge
1.232 + /// type.
1.233 + template <typename TargetMap, typename SourceMap>
1.234 + const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
1.235 + copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
1.236 + return *this;
1.237 + }
1.238 +
1.239 + /// \brief Gives back the stored node references.
1.240 + ///
1.241 + /// Gives back the stored node references.
1.242 + const NodeRefMap& nodeRef() const {
1.243 + return nodeRefMap;
1.244 + }
1.245 +
1.246 + /// \brief Gives back the stored edge references.
1.247 + ///
1.248 + /// Gives back the stored edge references.
1.249 + const EdgeRefMap& edgeRef() const {
1.250 + return edgeRefMap;
1.251 + }
1.252 +
1.253 + private:
1.254 +
1.255 + const Source& source;
1.256 + Target& target;
1.257 +
1.258 + NodeRefMap nodeRefMap;
1.259 + EdgeRefMap edgeRefMap;
1.260 };
1.261
1.262 + /// \brief Copy a graph to an other graph.
1.263 + ///
1.264 + /// Copy a graph to an other graph.
1.265 + /// The usage of the function:
1.266 + ///
1.267 + /// \code
1.268 + /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
1.269 + /// \endcode
1.270 + ///
1.271 + /// After the copy the \c nr map will contain the mapping from the
1.272 + /// source graph's nodes to the target graph's nodes and the \c ecr will
1.273 + /// contain the mapping from the target graph's edge to the source's
1.274 + /// edges.
1.275 + template <typename Target, typename Source>
1.276 + GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
1.277 + return GraphCopy<Target, Source>(target, source);
1.278 + }
1.279
1.280 template <typename _Graph, typename _Item>
1.281 class ItemSetTraits {};
2.1 --- a/lemon/maps.h Mon Jul 04 13:08:31 2005 +0000
2.2 +++ b/lemon/maps.h Mon Jul 04 13:10:34 2005 +0000
2.3 @@ -206,6 +206,20 @@
2.4 /// \addtogroup map_adaptors
2.5 /// @{
2.6
2.7 + /// \brief Identity mapping.
2.8 + ///
2.9 + /// This mapping gives back the given key as value without any
2.10 + /// modification.
2.11 + template <typename T>
2.12 + class IdentityMap {
2.13 + public:
2.14 + typedef T Key;
2.15 + typedef T Value;
2.16 +
2.17 + const Value& operator[](const Key& t) const {
2.18 + return t;
2.19 + }
2.20 + };
2.21
2.22 ///Convert the \c Value of a maps to another type.
2.23