/* -*- 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 #include ///\ingroup gutils ///\file ///\brief Graph utilities. /// ///\todo Please ///revise the documentation. /// namespace lemon { /// \addtogroup gutils /// @{ // 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 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 run in O(1). template inline int countNodes(const Graph& _g) { return countItems(_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 run in O(1). template inline int countEdges(const Graph& _g) { return countItems(_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 run in O(1). template inline int countSymEdges(const Graph& _g) { return countItems(_g); } template 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; } /// Finds an edge between two nodes of a graph. /// Finds an edge from node \c u to node \c v in graph \c g. /// /// If \c prev is \ref INVALID (this is the default value), then /// it finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or \ref INVALID if there is no such an edge. /// /// Thus you can iterate through each edge from \c u to \c v as it follows. /// \code /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { /// ... /// } /// \endcode /// \todo We may want to use the \ref concept::GraphBase "GraphBase" /// interface here... /// \bug Untested ... template typename Graph::Edge findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev = INVALID) { typename Graph::OutEdgeIt e(g,prev); if(prev==INVALID) g.first(e,u); else ++e; while(e!=INVALID && g.tail(e)!=v) ++e; return e; } ///\e ///\todo Please document. /// template inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { return countNodeDegree(_g, _n); } ///\e ///\todo Please document. /// template inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { return countNodeDegree(_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 _EdgeBijection =typename _SourceGraph::template EdgeMap > 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; } }; /// @} } //END OF NAMESPACE LEMON #endif