lemon-0.x: comparison lemon/graph

equal deleted inserted replaced

-:c174ad9cf7e0
+:5588a06c73c0
 ///Creates convenience typedefs for the undirected graph types and iterators
 ///This \c \#define creates the same convenience typedefs as defined by
 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
-///\c UndirEdge, \c UndirEdgeIt, \c IncEdgeIt,
+///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
-///\c BoolUndirEdgeMap, \c IntUndirEdgeMap,  \c DoubleUndirEdgeMap.
+///\c BoolUEdgeMap, \c IntUEdgeMap,  \c DoubleUEdgeMap.
 ///
 ///\note If \c G it a template parameter, it should be used in this way.
 ///\code
 ///  UNDIRGRAPH_TYPEDEFS(typename G)
 ///\endcode
 ///
 ///\warning There are no typedefs for the graph maps because of the lack of
 ///template typedefs in C++.
 #define UNDIRGRAPH_TYPEDEFS(Graph)				\
 GRAPH_TYPEDEFS(Graph)						\
-typedef Graph:: UndirEdge   UndirEdge;			\
+typedef Graph:: UEdge   UEdge;			\
-typedef Graph:: UndirEdgeIt UndirEdgeIt;			\
+typedef Graph:: UEdgeIt UEdgeIt;			\
 typedef Graph:: IncEdgeIt   IncEdgeIt;
-//     typedef Graph::template UndirEdgeMap<bool> BoolUndirEdgeMap;
+//     typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;
-//     typedef Graph::template UndirEdgeMap<int> IntUndirEdgeMap;
+//     typedef Graph::template UEdgeMap<int> IntUEdgeMap;
-//     typedef Graph::template UndirEdgeMap<double> DoubleUndirEdgeMap;
+//     typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
 /// \brief Function to count the items in the graph.
 ///
 // Undirected edge counting:
 template <typename Graph>
 inline
 typename enable_if<typename Graph::EdgeNumTag, int>::type
-_countUndirEdges(const Graph &g) {
+_countUEdges(const Graph &g) {
-return g.undirEdgeNum();
+return g.uEdgeNum();
 }
 template <typename Graph>
-inline int _countUndirEdges(Wrap<Graph> w) {
+inline int _countUEdges(Wrap<Graph> w) {
-return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
+return countItems<Graph, typename Graph::UEdgeIt>(w.value);
 }
 /// \brief Function to count the undirected edges in the graph.
 ///
 /// This function counts the undirected edges in the graph.
 /// The complexity of the function is O(e) but for some
 /// graph structures it is specialized to run in O(1).
 template <typename Graph>
-inline int countUndirEdges(const Graph& g) {
+inline int countUEdges(const Graph& g) {
-return _countUndirEdges<Graph>(g);
+return _countUEdges<Graph>(g);
 }
 template <typename Graph, typename DegIt>
 template <typename Graph>
 inline
 typename enable_if<
 typename Graph::FindEdgeTag,
-typename Graph::UndirEdge>::type
+typename Graph::UEdge>::type
-_findUndirEdge(const Graph &g,
+_findUEdge(const Graph &g,
 	    typename Graph::Node u, typename Graph::Node v,
-	    typename Graph::UndirEdge prev = INVALID) {
+	    typename Graph::UEdge prev = INVALID) {
-return g.findUndirEdge(u, v, prev);
+return g.findUEdge(u, v, prev);
 }
 template <typename Graph>
-inline typename Graph::UndirEdge
+inline typename Graph::UEdge
-_findUndirEdge(Wrap<Graph> w,
+_findUEdge(Wrap<Graph> w,
 	    typename Graph::Node u,
 	    typename Graph::Node v,
-	    typename Graph::UndirEdge prev = INVALID) {
+	    typename Graph::UEdge 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;
 while (e != INVALID && g.target(e) != v) ++e;
 return e;
 }
 }
-/// \brief Finds an undir edge between two nodes of a graph.
+/// \brief Finds an uedge between two nodes of a graph.
 ///
-/// Finds an undir edge from node \c u to node \c v in graph \c g.
+/// Finds an uedge 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;
+/// for(UEdge e = findUEdge(g,u,v); e != INVALID;
-///     e = findUndirEdge(g,u,v,e)) {
+///     e = findUEdge(g,u,v,e)) {
 ///   ...
 /// }
 /// \endcode
 // /// \todo We may want to use the "GraphBase"
 // /// interface here...
 template <typename Graph>
-inline typename Graph::UndirEdge
+inline typename Graph::UEdge
-findUndirEdge(const Graph &g,
+findUEdge(const Graph &g,
 		typename Graph::Node u,
 		typename Graph::Node v,
-		typename Graph::UndirEdge prev = INVALID) {
+		typename Graph::UEdge prev = INVALID) {
-return _findUndirEdge<Graph>(g, u, v, prev);
+return _findUEdge<Graph>(g, u, v, prev);
 }
-/// \brief Iterator for iterating on undir edges connected the same nodes.
+/// \brief Iterator for iterating on uedges connected the same nodes.
 ///
-/// Iterator for iterating on undir edges connected the same nodes. It is
+/// Iterator for iterating on uedges connected the same nodes. It is
-/// higher level interface for the findUndirEdge() function. You can
+/// higher level interface for the findUEdge() function. You can
 /// use it the following way:
 /// \code
-/// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
+/// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
 ///   ...
 /// }
 /// \endcode
 ///
 /// \author Balazs Dezso
 template <typename _Graph>
-class ConUndirEdgeIt : public _Graph::UndirEdge {
+class ConUEdgeIt : public _Graph::UEdge {
 public:
 typedef _Graph Graph;
-typedef typename Graph::UndirEdge Parent;
+typedef typename Graph::UEdge Parent;
-typedef typename Graph::UndirEdge UndirEdge;
+typedef typename Graph::UEdge UEdge;
 typedef typename Graph::Node Node;
 /// \brief Constructor.
 ///
-/// Construct a new ConUndirEdgeIt iterating on the edges which
+/// Construct a new ConUEdgeIt iterating on the edges which
 /// connects the \c u and \c v node.
-ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
+ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
-Parent::operator=(findUndirEdge(graph, u, v));
+Parent::operator=(findUEdge(graph, u, v));
 }
 /// \brief Constructor.
 ///
-/// Construct a new ConUndirEdgeIt which continues the iterating from
+/// Construct a new ConUEdgeIt which continues the iterating from
 /// the \c e edge.
-ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
+ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
 /// \brief Increment operator.
 ///
 /// It increments the iterator and gives back the next edge.
-ConUndirEdgeIt& operator++() {
+ConUEdgeIt& operator++() {
-Parent::operator=(findUndirEdge(graph, graph.source(*this),
+Parent::operator=(findUEdge(graph, graph.source(*this),
 				      graph.target(*this), *this));
 return *this;
 }
 private:
 const Graph& graph;
 }
 /// \brief Class to copy an undirected graph.
 ///
 /// Class to copy an undirected graph to an other graph (duplicate a graph).
-/// The simplest way of using it is through the \c copyUndirGraph() function.
+/// The simplest way of using it is through the \c copyUGraph() function.
 template <typename Target, typename Source>
-class UndirGraphCopy {
+class UGraphCopy {
 public:
 typedef typename Source::Node Node;
 typedef typename Source::NodeIt NodeIt;
 typedef typename Source::Edge Edge;
 typedef typename Source::EdgeIt EdgeIt;
-typedef typename Source::UndirEdge UndirEdge;
+typedef typename Source::UEdge UEdge;
-typedef typename Source::UndirEdgeIt UndirEdgeIt;
+typedef typename Source::UEdgeIt UEdgeIt;
 typedef typename Source::
 template NodeMap<typename Target::Node> NodeRefMap;
 typedef typename Source::
-template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
+template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
 private:
 struct EdgeRefMap {
-EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
+EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
 typedef typename Source::Edge Key;
 typedef typename Target::Edge Value;
 Value operator[](const Key& key) {
-	return gc.target.direct(gc.undirEdgeRef[key],
+	return gc.target.direct(gc.uEdgeRef[key],
 				gc.target.direction(key));
 }
-UndirGraphCopy& gc;
+UGraphCopy& gc;
 };
 public:
-/// \brief Constructor for the UndirGraphCopy.
+/// \brief Constructor for the UGraphCopy.
 ///
 /// It copies the content of the \c _source graph into the
 /// \c _target graph. It creates also two references, one beetween
 /// the two nodeset and one beetween the two edgesets.
-UndirGraphCopy(Target& _target, const Source& _source)
+UGraphCopy(Target& _target, const Source& _source)
 : source(_source), target(_target),
-	nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
+	nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
 for (NodeIt it(source); it != INVALID; ++it) {
 	nodeRefMap[it] = target.addNode();
 }
-for (UndirEdgeIt it(source); it != INVALID; ++it) {
+for (UEdgeIt it(source); it != INVALID; ++it) {
-	undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
+	uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
 					nodeRefMap[source.target(it)]);
 }
 }
 /// \brief Copies the node references into the given map.
 ///
 /// Copies the node references into the given map.
 template <typename NodeRef>
-const UndirGraphCopy& nodeRef(NodeRef& map) const {
+const UGraphCopy& nodeRef(NodeRef& map) const {
 for (NodeIt it(source); it != INVALID; ++it) {
 	map.set(it, nodeRefMap[it]);
 }
 return *this;
 }
 /// \brief Reverse and copies the node references into the given map.
 ///
 /// Reverse and copies the node references into the given map.
 template <typename NodeRef>
-const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
+const UGraphCopy& nodeCrossRef(NodeRef& map) const {
 for (NodeIt it(source); it != INVALID; ++it) {
 	map.set(nodeRefMap[it], it);
 }
 return *this;
 }
 /// \brief Copies the edge references into the given map.
 ///
 /// Copies the edge references into the given map.
 template <typename EdgeRef>
-const UndirGraphCopy& edgeRef(EdgeRef& map) const {
+const UGraphCopy& edgeRef(EdgeRef& map) const {
 for (EdgeIt it(source); it != INVALID; ++it) {
 	map.set(edgeRefMap[it], it);
 }
 return *this;
 }
 /// \brief Reverse and copies the undirected edge references into the
 /// given map.
 ///
 /// Reverse and copies the undirected edge references into the given map.
 template <typename EdgeRef>
-const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
+const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
 for (EdgeIt it(source); it != INVALID; ++it) {
 	map.set(it, edgeRefMap[it]);
 }
 return *this;
 }
 /// \brief Copies the undirected edge references into the given map.
 ///
 /// Copies the undirected edge references into the given map.
 template <typename EdgeRef>
-const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
+const UGraphCopy& uEdgeRef(EdgeRef& map) const {
-for (UndirEdgeIt it(source); it != INVALID; ++it) {
+for (UEdgeIt it(source); it != INVALID; ++it) {
-	map.set(it, undirEdgeRefMap[it]);
+	map.set(it, uEdgeRefMap[it]);
 }
 return *this;
 }
 /// \brief Reverse and copies the undirected edge references into the
 /// given map.
 ///
 /// Reverse and copies the undirected edge references into the given map.
 template <typename EdgeRef>
-const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
+const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
-for (UndirEdgeIt it(source); it != INVALID; ++it) {
+for (UEdgeIt it(source); it != INVALID; ++it) {
-	map.set(undirEdgeRefMap[it], it);
+	map.set(uEdgeRefMap[it], it);
 }
 return *this;
 }
 /// \brief Make copy of the given map.
 /// Makes copy of the given map for the newly created graph.
 /// The new map's key type is the target graph's node type,
 /// and the copied map's key type is the source graph's node
 /// type.
 template <typename TargetMap, typename SourceMap>
-const UndirGraphCopy& nodeMap(TargetMap& tMap,
+const UGraphCopy& nodeMap(TargetMap& tMap,
 				  const SourceMap& sMap) const {
 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
 return *this;
 }
 /// Makes copy of the given map for the newly created graph.
 /// The new map's key type is the target graph's edge type,
 /// and the copied map's key type is the source graph's edge
 /// type.
 template <typename TargetMap, typename SourceMap>
-const UndirGraphCopy& edgeMap(TargetMap& tMap,
+const UGraphCopy& edgeMap(TargetMap& tMap,
 				  const SourceMap& sMap) const {
 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
 return *this;
 }
 /// Makes copy of the given map for the newly created graph.
 /// The new map's key type is the target graph's edge type,
 /// and the copied map's key type is the source graph's edge
 /// type.
 template <typename TargetMap, typename SourceMap>
-const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
+const UGraphCopy& uEdgeMap(TargetMap& tMap,
 				  const SourceMap& sMap) const {
-copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
+copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
 return *this;
 }
 /// \brief Gives back the stored node references.
 ///
 /// Gives back the stored edge references.
 const EdgeRefMap& edgeRef() const {
 return edgeRefMap;
 }
-/// \brief Gives back the stored undir edge references.
+/// \brief Gives back the stored uedge references.
 ///
-/// Gives back the stored undir edge references.
+/// Gives back the stored uedge references.
-const UndirEdgeRefMap& undirEdgeRef() const {
+const UEdgeRefMap& uEdgeRef() const {
-return undirEdgeRefMap;
+return uEdgeRefMap;
 }
 void run() {}
 private:
 const Source& source;
 Target& target;
 NodeRefMap nodeRefMap;
 EdgeRefMap edgeRefMap;
-UndirEdgeRefMap undirEdgeRefMap;
+UEdgeRefMap uEdgeRefMap;
 };
 /// \brief Copy a graph to an other graph.
 ///
 /// Copy a graph to an other graph.
 /// After the copy the \c nr map will contain the mapping from the
 /// source graph's nodes to the target graph's nodes and the \c ecr will
 /// contain the mapping from the target graph's edges to the source's
 /// edges.
 template <typename Target, typename Source>
-UndirGraphCopy<Target, Source>
+UGraphCopy<Target, Source>
-copyUndirGraph(Target& target, const Source& source) {
+copyUGraph(Target& target, const Source& source) {
-return UndirGraphCopy<Target, Source>(target, source);
+return UGraphCopy<Target, Source>(target, source);
 }
 /// @}
 public:
 typedef _Map Map;
 typedef _Graph Graph;
-/// The key type of InvertableMap (Node, Edge, UndirEdge).
+/// The key type of InvertableMap (Node, Edge, UEdge).
 typedef typename _Map::Key Key;
 /// The value type of the InvertableMap.
 typedef typename _Map::Value Value;
 /// \brief Constructor.
 /// other node, i.e. this id is mutable).  </ul> This map can be inverted
 /// with its member class \c InverseMap.
 ///
 /// \param _Graph The graph class the \c DescriptorMap belongs to.
 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
-/// UndirEdge.
+/// UEdge.
 #ifndef DOXYGEN
 /// \param _Map A ReadWriteMap mapping from the item type to integer.
 template <
 typename _Graph, typename _Item, typename _Map
 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
 public:
 /// The graph class of DescriptorMap.
 typedef _Graph Graph;
-/// The key type of DescriptorMap (Node, Edge, UndirEdge).
+/// The key type of DescriptorMap (Node, Edge, UEdge).
 typedef typename _Map::Key Key;
 /// The value type of DescriptorMap.
 typedef typename _Map::Value Value;
 /// \brief Constructor.
 template <typename Graph>
 class ForwardMap {
 public:
 typedef typename Graph::Edge Value;
-typedef typename Graph::UndirEdge Key;
+typedef typename Graph::UEdge Key;
 /// \brief Constructor
 ///
 /// Constructor
 /// \param _graph The graph that the map belongs to.
 template <typename Graph>
 class BackwardMap {
 public:
 typedef typename Graph::Edge Value;
-typedef typename Graph::UndirEdge Key;
+typedef typename Graph::UEdge Key;
 /// \brief Constructor
 ///
 /// Constructor
 /// \param _graph The graph that the map belongs to.

changeset 1914	7ef30a71937f
parent 1875	98698b69a902
child 1931	6abf67b02ff5