lemon-0.x: comparison lemon/ugraph

equal deleted inserted replaced

-:2dd05e6c3b90
+:9f352bd70429
 /// \ingroup graph_adaptors
 ///
 /// \brief Base type for the Graph Adaptors
 ///
-/// \warning Graph adaptors are in even more experimental state than the
-/// other parts of the lib. Use them at you own risk.
-///
 /// This is the base type for most of LEMON graph adaptors.
 /// This class implements a trivial graph adaptor i.e. it only wraps the
 /// functions and types of the graph. The purpose of this class is to
 /// make easier implementing graph adaptors. E.g. if an adaptor is
 /// considered which differs from the wrapped graph only in some of its
 void next(UEdge& i) const { graph->next(i); }
 void nextIn(Edge& i) const { graph->nextIn(i); }
 void nextOut(Edge& i) const { graph->nextOut(i); }
 void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
 Node source(const UEdge& e) const { return graph->source(e); }
 Node target(const UEdge& e) const { return graph->target(e); }
 Node source(const Edge& e) const { return graph->source(e); }
 Node target(const Edge& e) const { return graph->target(e); }
 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 Edge findEdge(const Node& source, const Node& target,
 		  const Edge& prev = INVALID) {
 return graph->findEdge(source, target, prev);
 }
 UEdge findUEdge(const Node& source, const Node& target,
 const UEdge& prev = INVALID) {
 return graph->findUEdge(source, target, prev);
 }
 int id(const Node& v) const { return graph->id(v); }
 int id(const UEdge& e) const { return graph->id(e); }
 bool direction(const Edge& e) const { return graph->direction(e); }
 Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
-Edge direct(const UEdge& e, const Node& n) const {
-return graph->direct(e, n);
+int maxNodeId() const {
-}
+return graph->maxNodeId();
+}
-Node oppositeNode(const Node& n, const Edge& e) const {
-return graph->oppositeNode(n, e);
+int maxEdgeId() const {
-}
+return graph->maxEdgeId();
+}
-Edge oppositeEdge(const Edge& e) const {
-return graph->oppositeEdge(e);
+int maxUEdgeId() const {
-}
+return graph->maxEdgeId();
+}
+typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+NodeNotifier& getNotifier(Node) const {
+return graph->getNotifier(Node());
+}
+typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
+EdgeNotifier& getNotifier(Edge) const {
+return graph->getNotifier(Edge());
+}
+typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
+UEdgeNotifier& getNotifier(UEdge) const {
+return graph->getNotifier(UEdge());
+}
 template <typename _Value>
 class NodeMap : public Graph::template NodeMap<_Value> {
 public:
 typedef typename Graph::template NodeMap<_Value> Parent;
 ///
 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
 typedef False NodeNumTag;
 typedef False EdgeNumTag;
+typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+Edge findEdge(const Node& source, const Node& target,
+		  const Edge& prev = INVALID) {
+if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
+return INVALID;
+}
+Edge edge = Parent::findEdge(source, target, prev);
+while (edge != INVALID && !(*uedge_filter_map)[edge]) {
+edge = Parent::findEdge(source, target, edge);
+}
+return edge;
+}
+UEdge findUEdge(const Node& source, const Node& target,
+		  const UEdge& prev = INVALID) {
+if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
+return INVALID;
+}
+UEdge uedge = Parent::findUEdge(source, target, prev);
+while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
+uedge = Parent::findUEdge(source, target, uedge);
+}
+return uedge;
+}
 };
 template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
 class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
 : public UGraphAdaptorBase<_UGraph> {
 ///
 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
 typedef False NodeNumTag;
 typedef False EdgeNumTag;
+typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+Edge findEdge(const Node& source, const Node& target,
+		  const Edge& prev = INVALID) {
+Edge edge = Parent::findEdge(source, target, prev);
+while (edge != INVALID && !(*uedge_filter_map)[edge]) {
+edge = Parent::findEdge(source, target, edge);
+}
+return edge;
+}
+UEdge findUEdge(const Node& source, const Node& target,
+		  const UEdge& prev = INVALID) {
+UEdge uedge = Parent::findUEdge(source, target, prev);
+while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
+uedge = Parent::findUEdge(source, target, uedge);
+}
+return uedge;
+}
 };
 /// \ingroup graph_adaptors
 ///
 /// \brief A graph adaptor for hiding nodes and edges from an undirected
 /// \ingroup graph_adaptors
 ///
 /// \brief An adaptor for hiding nodes from an undirected graph.
 ///
-///
 /// An adaptor for hiding nodes from an undirected graph.
 /// This adaptor specializes SubUGraphAdaptor in the way that only
 /// the node-set
 /// can be filtered. In usual case the checked parameter is true, we get the
 /// induced subgraph. But if the checked parameter is false then we can only
 typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
 ConstMap<typename _UGraph::UEdge, bool> > Parent;
 typedef _UGraph Graph;
 protected:
 ConstMap<typename _UGraph::UEdge, bool> const_true_map;
+NodeSubUGraphAdaptor() : const_true_map(true) {
+Parent::setUEdgeFilterMap(const_true_map);
+}
 public:
 NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
 Parent(), const_true_map(true) {
 Parent::setGraph(_graph);
 Parent::setNodeFilterMap(_node_filter_map);
 typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
 UEdgeFilterMap, false> Parent;
 typedef _UGraph Graph;
 protected:
 ConstMap<typename Graph::Node, bool> const_true_map;
+EdgeSubUGraphAdaptor() : const_true_map(true) {
+Parent::setNodeFilterMap(const_true_map);
+}
 public:
 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
 Parent(), const_true_map(true) {
 Parent::setGraph(_graph);
 Parent::setNodeFilterMap(const_true_map);
 typedef _DirectionMap DirectionMap;
 typedef typename _UGraph::Node Node;
 typedef typename _UGraph::UEdge Edge;
+void reverseEdge(const Edge& edge) {
+direction->set(edge, !(*direction)[edge]);
+}
 void first(Node& i) const { graph->first(i); }
 void first(Edge& i) const { graph->first(i); }
 void firstIn(Edge& i, const Node& n) const {
 bool d;
 graph->firstInc(i, d, n);
 void clear() const { graph->clear(); }
 int id(const Node& v) const { return graph->id(v); }
 int id(const Edge& e) const { return graph->id(e); }
-void reverseEdge(const Edge& edge) {
+int maxNodeId() const {
-direction->set(edge, !(*direction)[edge]);
+return graph->maxNodeId();
 }
+int maxEdgeId() const {
+return graph->maxEdgeId();
+}
+typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+NodeNotifier& getNotifier(Node) const {
+return graph->getNotifier(Node());
+}
+typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
+EdgeNotifier& getNotifier(Edge) const {
+return graph->getNotifier(Edge());
+}
 template <typename _Value>
 class NodeMap : public _UGraph::template NodeMap<_Value> {
 public:
 typedef typename _UGraph::template NodeMap<_Value> Parent;
 };
 /// \ingroup graph_adaptors
-/// \brief A directed graph is made from a undirected graph by an adaptor
+///
+/// \brief A directed graph is made from an undirected graph by an adaptor
 ///
 /// This adaptor gives a direction for each uedge in the undirected graph.
 /// The direction of the edges stored in the DirectionMap. This map is
 /// a bool map on the undirected edges. If the uedge is mapped to true
 /// then the direction of the directed edge will be the same as the

changeset 1992	6e1b62d42d94
parent 1985	8782ff6fd98a
child 1993	2115143eceea