lemon-0.x: comparison lemon/graph

equal deleted inserted replaced

-:1ef52a3eb8ab
+:7b4eca91f158
 template <typename Graph>
 inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
 }
-/// \brief Function to count the number of the in-edges to node \c n.
+/// \brief Function to count the number of the inc-edges to node \c n.
 ///
-/// This function counts the number of the in-edges to node \c n
+/// This function counts the number of the inc-edges to node \c n
 /// in the graph.
 template <typename Graph>
 inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
 }
 ///   ...
 /// }
 /// \endcode
 // /// \todo We may want to use the "GraphBase"
 // /// interface here...
-// /// It would not work with the undirected graphs.
 template <typename Graph>
 inline typename Graph::Edge findEdge(const Graph &g,
 				       typename Graph::Node u,
 				       typename Graph::Node v,
 				       typename Graph::Edge prev = INVALID) {
 /// \brief Increment operator.
 ///
 /// It increments the iterator and gives back the next edge.
 ConEdgeIt& operator++() {
 Parent::operator=(findEdge(graph, graph.source(*this),
+				 graph.target(*this), *this));
+return *this;
+}
+private:
+const Graph& graph;
+};
+template <typename Graph>
+inline
+typename enable_if<
+typename Graph::FindEdgeTag,
+typename Graph::UndirEdge>::type
+_findUndirEdge(const Graph &g,
+	    typename Graph::Node u, typename Graph::Node v,
+	    typename Graph::UndirEdge prev = INVALID) {
+return g.findUndirEdge(u, v, prev);
+}
+template <typename Graph>
+inline typename Graph::UndirEdge
+_findUndirEdge(Wrap<Graph> w,
+	    typename Graph::Node u,
+	    typename Graph::Node v,
+	    typename Graph::UndirEdge prev = INVALID) {
+const Graph& g = w.value;
+if (prev == INVALID) {
+typename Graph::OutEdgeIt e(g, u);
+while (e != INVALID && g.target(e) != v) ++e;
+return e;
+} else {
+typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
+while (e != INVALID && g.target(e) != v) ++e;
+return e;
+}
+}
+/// \brief Finds an undir edge between two nodes of a graph.
+///
+/// Finds an undir 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(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
+///     e = findUndirEdge(g,u,v,e)) {
+///   ...
+/// }
+/// \endcode
+// /// \todo We may want to use the "GraphBase"
+// /// interface here...
+template <typename Graph>
+inline typename Graph::UndirEdge
+findUndirEdge(const Graph &g,
+		typename Graph::Node u,
+		typename Graph::Node v,
+		typename Graph::UndirEdge prev = INVALID) {
+return _findUndirEdge<Graph>(g, u, v, prev);
+}
+/// \brief Iterator for iterating on undir edges connected the same nodes.
+///
+/// Iterator for iterating on undir edges connected the same nodes. It is
+/// higher level interface for the findUndirEdge() function. You can
+/// use it the following way:
+/// \code
+/// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
+///   ...
+/// }
+/// \endcode
+///
+/// \author Balazs Dezso
+template <typename _Graph>
+class ConUndirEdgeIt : public _Graph::UndirEdge {
+public:
+typedef _Graph Graph;
+typedef typename Graph::UndirEdge Parent;
+typedef typename Graph::UndirEdge UndirEdge;
+typedef typename Graph::Node Node;
+/// \brief Constructor.
+///
+/// Construct a new ConUndirEdgeIt iterating on the edges which
+/// connects the \c u and \c v node.
+ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
+Parent::operator=(findUndirEdge(graph, u, v));
+}
+/// \brief Constructor.
+///
+/// Construct a new ConUndirEdgeIt which continues the iterating from
+/// the \c e edge.
+ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
+/// \brief Increment operator.
+///
+/// It increments the iterator and gives back the next edge.
+ConUndirEdgeIt& operator++() {
+Parent::operator=(findUndirEdge(graph, graph.source(*this),
 				 graph.target(*this), *this));
 return *this;
 }
 private:
 const Graph& graph;
 typedef _Graph Graph;
 typedef int Value;
 typedef _Item Item;
 typedef _Item Key;
-typedef True NeedCopy;
 /// \brief Constructor.
 ///
 /// Constructor for creating id map.
 IdMap(const Graph& _graph) : graph(&_graph) {}
 ///
 /// The class represents the inverse of its owner (IdMap).
 /// \see inverse()
 class InverseMap {
 public:
-typedef True NeedCopy;
 /// \brief Constructor.
 ///
 /// Constructor for creating an id-to-item map.
 InverseMap(const Graph& _graph) : graph(&_graph) {}
 /// \author Balazs Dezso
 template <typename Graph>
 class SourceMap {
 public:
-typedef True NeedCopy;
 typedef typename Graph::Node Value;
 typedef typename Graph::Edge Key;
 /// \brief Constructor
 ///
 /// \author Balazs Dezso
 template <typename Graph>
 class TargetMap {
 public:
-typedef True NeedCopy;
 typedef typename Graph::Node Value;
 typedef typename Graph::Edge Key;
 /// \brief Constructor
 ///
 /// \author Balazs Dezso
 template <typename Graph>
 class ForwardMap {
 public:
-typedef True NeedCopy;
 typedef typename Graph::Edge Value;
 typedef typename Graph::UndirEdge Key;
 /// \brief Constructor
 ///
 /// Returns the "backward" directed edge view of an undirected edge.
 /// \author Balazs Dezso
 template <typename Graph>
 class BackwardMap {
 public:
-typedef True NeedCopy;
 typedef typename Graph::Edge Value;
 typedef typename Graph::UndirEdge Key;
 /// \brief Constructor
 RowMap rowMap(Node row) { return RowMap(*this, row); }
 protected:
 static int index(int i, int j) {
-int m = i > j ? i : j;
 if (i < j) {
-	return m * m + i;
+	return j * j + i;
 } else {
-	return m * m + m + j;
+	return i * i + i + j;
 }
 }
 static int size(int s) {
 return s * s;

changeset 1707	39496e5482af
parent 1695	e6f99fe1723f
child 1712	4fb435ad31cf