lemon/bits/undir_graph_extender.h
changeset 1752 dce1f28ac595
parent 1627 3fd1ba6e9872
equal deleted inserted replaced
1:171b2c8a77a2 2:6851e02b36da
    69     /// Returns the Edge of opposite direction.
    69     /// Returns the Edge of opposite direction.
    70     Edge oppositeEdge(const Edge &e) const {
    70     Edge oppositeEdge(const Edge &e) const {
    71       return Edge(e,!e.forward);
    71       return Edge(e,!e.forward);
    72     }
    72     }
    73 
    73 
    74   protected:
       
    75 
       
    76     template <typename E>
       
    77     Node _dirSource(const E &e) const {
       
    78       return e.forward ? Parent::source(e) : Parent::target(e);
       
    79     }
       
    80 
       
    81     template <typename E>
       
    82     Node _dirTarget(const E &e) const {
       
    83       return e.forward ? Parent::target(e) : Parent::source(e);
       
    84     }
       
    85 
       
    86   public:
    74   public:
    87     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    75     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    88     /// or something???
    76     /// or something???
    89     using Parent::source;
    77     using Parent::source;
    90 
    78 
    91     /// Source of the given Edge.
    79     /// Source of the given Edge.
    92     Node source(const Edge &e) const {
    80     Node source(const Edge &e) const {
    93       return _dirSource(e);
    81       return e.forward ? Parent::source(e) : Parent::target(e);
    94     }
    82     }
    95 
    83 
    96     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    84     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    97     /// or something???
    85     /// or something???
    98     using Parent::target;
    86     using Parent::target;
    99 
    87 
   100     /// Target of the given Edge.
    88     /// Target of the given Edge.
   101     Node target(const Edge &e) const {
    89     Node target(const Edge &e) const {
   102       return _dirTarget(e);
    90       return e.forward ? Parent::target(e) : Parent::source(e);
   103     }
    91     }
   104 
    92 
   105     Node oppositeNode(const Node &n, const UndirEdge &e) const {
    93     Node oppositeNode(const Node &n, const UndirEdge &e) const {
   106       if( n == Parent::source(e))
    94       if( n == Parent::source(e))
   107 	return Parent::target(e);
    95 	return Parent::target(e);
   152 	Parent::next(e);
   140 	Parent::next(e);
   153 	e.forward = true;
   141 	e.forward = true;
   154       }
   142       }
   155     }
   143     }
   156 
   144 
   157     
   145   public:
   158   protected:
   146 
   159 
   147     void firstOut(Edge &e, const Node &n) const {
   160     template <typename E>
       
   161     void _dirFirstOut(E &e, const Node &n) const {
       
   162       Parent::firstIn(e,n);
   148       Parent::firstIn(e,n);
   163       if( UndirEdge(e) != INVALID ) {
   149       if( UndirEdge(e) != INVALID ) {
   164 	e.forward = false;
   150 	e.forward = false;
   165       }
   151       }
   166       else {
   152       else {
   167 	Parent::firstOut(e,n);
   153 	Parent::firstOut(e,n);
   168 	e.forward = true;
   154 	e.forward = true;
   169       }
   155       }
   170     }
   156     }
   171     template <typename E>
   157     void nextOut(Edge &e) const {
   172     void _dirFirstIn(E &e, const Node &n) const {
       
   173       Parent::firstOut(e,n);
       
   174       if( UndirEdge(e) != INVALID ) {
       
   175 	e.forward = false;
       
   176       }
       
   177       else {
       
   178 	Parent::firstIn(e,n);
       
   179 	e.forward = true;
       
   180       }
       
   181     }
       
   182 
       
   183     template <typename E>
       
   184     void _dirNextOut(E &e) const {
       
   185       if( ! e.forward ) {
   158       if( ! e.forward ) {
   186 	Node n = Parent::target(e);
   159 	Node n = Parent::target(e);
   187 	Parent::nextIn(e);
   160 	Parent::nextIn(e);
   188 	if( UndirEdge(e) == INVALID ) {
   161 	if( UndirEdge(e) == INVALID ) {
   189 	  Parent::firstOut(e, n);
   162 	  Parent::firstOut(e, n);
   192       }
   165       }
   193       else {
   166       else {
   194 	Parent::nextOut(e);
   167 	Parent::nextOut(e);
   195       }
   168       }
   196     }
   169     }
   197     template <typename E>
   170 
   198     void _dirNextIn(E &e) const {
   171     void firstIn(Edge &e, const Node &n) const {
       
   172       Parent::firstOut(e,n);
       
   173       if( UndirEdge(e) != INVALID ) {
       
   174 	e.forward = false;
       
   175       }
       
   176       else {
       
   177 	Parent::firstIn(e,n);
       
   178 	e.forward = true;
       
   179       }
       
   180     }
       
   181     void nextIn(Edge &e) const {
   199       if( ! e.forward ) {
   182       if( ! e.forward ) {
   200 	Node n = Parent::source(e);
   183 	Node n = Parent::source(e);
   201 	Parent::nextOut(e);
   184 	Parent::nextOut(e);
   202 	if( UndirEdge(e) == INVALID ) {
   185 	if( UndirEdge(e) == INVALID ) {
   203 	  Parent::firstIn(e, n);
   186 	  Parent::firstIn(e, n);
   207       else {
   190       else {
   208 	Parent::nextIn(e);
   191 	Parent::nextIn(e);
   209       }
   192       }
   210     }
   193     }
   211 
   194 
   212   public:
   195     void firstInc(UndirEdge &e, const Node &n) const {
   213 
   196       Parent::firstOut(e, n);
   214     void firstOut(Edge &e, const Node &n) const {
   197       if (e != INVALID) return;
   215       _dirFirstOut(e, n);
   198       Parent::firstIn(e, n);
   216     }
   199     }
   217     void firstIn(Edge &e, const Node &n) const {
   200     void nextInc(UndirEdge &e, const Node &n) const {
   218       _dirFirstIn(e, n);
   201       if (Parent::source(e) == n) {
   219     }
   202 	Parent::nextOut(e);
   220 
   203 	if (e != INVALID) return;
   221     void nextOut(Edge &e) const {
   204 	Parent::firstIn(e, n);
   222       _dirNextOut(e);
   205       } else {
   223     }
   206 	Parent::nextIn(e);
   224     void nextIn(Edge &e) const {
   207       }
   225       _dirNextIn(e);
   208     }
       
   209 
       
   210     void firstInc(UndirEdge &e, bool &d, const Node &n) const {
       
   211       d = true;
       
   212       Parent::firstOut(e, n);
       
   213       if (e != INVALID) return;
       
   214       d = false;
       
   215       Parent::firstIn(e, n);
       
   216     }
       
   217     void nextInc(UndirEdge &e, bool &d) const {
       
   218       if (d) {
       
   219 	Node s = Parent::source(e);
       
   220 	Parent::nextOut(e);
       
   221 	if (e != INVALID) return;
       
   222 	d = false;
       
   223 	Parent::firstIn(e, s);
       
   224       } else {
       
   225 	Parent::nextIn(e);
       
   226       }
   226     }
   227     }
   227 
   228 
   228     // Miscellaneous stuff:
   229     // Miscellaneous stuff:
   229 
   230 
   230     /// \todo these methods (id, maxEdgeId) should be moved into separate
   231     /// \todo these methods (id, maxEdgeId) should be moved into separate
   260 
   261 
   261 
   262 
   262     int edgeNum() const {
   263     int edgeNum() const {
   263       return 2 * Parent::edgeNum();
   264       return 2 * Parent::edgeNum();
   264     }
   265     }
       
   266 
   265     int undirEdgeNum() const {
   267     int undirEdgeNum() const {
   266       return Parent::edgeNum();
   268       return Parent::edgeNum();
   267     }
   269     }
   268 
   270 
       
   271     Edge findEdge(Node source, Node target, Edge prev) const {
       
   272       if (prev == INVALID) {
       
   273 	UndirEdge edge = Parent::findEdge(source, target);
       
   274 	if (edge != INVALID) return direct(edge, true);
       
   275 	edge = Parent::findEdge(target, source);
       
   276 	if (edge != INVALID) return direct(edge, false);
       
   277       } else if (direction(prev)) {
       
   278 	UndirEdge edge = Parent::findEdge(source, target, prev);
       
   279 	if (edge != INVALID) return direct(edge, true);
       
   280 	edge = Parent::findEdge(target, source);
       
   281 	if (edge != INVALID) return direct(edge, false);	
       
   282       } else {
       
   283 	UndirEdge edge = Parent::findEdge(target, source, prev);
       
   284 	if (edge != INVALID) return direct(edge, false);	      
       
   285       }
       
   286       return INVALID;
       
   287     }
       
   288 
       
   289     UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
       
   290       if (prev == INVALID) {
       
   291 	UndirEdge edge = Parent::findEdge(source, target);
       
   292 	if (edge != INVALID) return edge;
       
   293 	edge = Parent::findEdge(target, source);
       
   294 	if (edge != INVALID) return edge;
       
   295       } else if (Parent::source(prev) == source) {
       
   296 	UndirEdge edge = Parent::findEdge(source, target, prev);
       
   297 	if (edge != INVALID) return edge;
       
   298 	edge = Parent::findEdge(target, source);
       
   299 	if (edge != INVALID) return edge;	
       
   300       } else {
       
   301 	UndirEdge edge = Parent::findEdge(target, source, prev);
       
   302 	if (edge != INVALID) return edge;	      
       
   303       }
       
   304       return INVALID;
       
   305     }
       
   306 
   269   };
   307   };
   270 
   308 
   271 }
   309 }
   272 
   310 
   273 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H
   311 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H