Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/iterable_graph_extender.h
changeset 1909 2d806130e700
parent 1820 22099ef840d7
child 1910 f95eea8c34b0
equal deleted inserted replaced
5:94d8f7d5e86b 6:66a1098c5c83 
    14     /// Indicates that the graph is undirected.
 
    14     /// Indicates that the graph is undirected.
 
    15 
    15 
    16     ///\todo Better name?
 
    16     ///\todo Better name?
 
    17     ///
 
    17     ///
 
    18     ///\bug Should it be here?
 
    18     ///\bug Should it be here?
 
    19     typedef False UndirTag;
 
    19     typedef False UTag;
 
    20 
    20 
    21     typedef _Base Parent;
 
    21     typedef _Base Parent;
 
    22     typedef IterableGraphExtender<_Base> Graph;
 
    22     typedef IterableGraphExtender<_Base> Graph;
 
    23 
    23 
    24     typedef typename Parent::Node Node;
 
    24     typedef typename Parent::Node Node;
 
   172 
   172 
   173 
   173 
   174 
   174 
   175   
   175   
   176   template <typename _Base>
 
   176   template <typename _Base>
 
   177   class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
 
   177   class IterableUGraphExtender : public IterableGraphExtender<_Base> {
 
   178   public:
 
   178   public:
 
   179 
   179 
   180     /// Indicates that the graph is undirected.
 
   180     /// Indicates that the graph is undirected.
 
   181 
   181 
   182     ///\todo Better name?
 
   182     ///\todo Better name?
 
   183     ///
 
   183     ///
 
   184     ///\bug Should it be here?
 
   184     ///\bug Should it be here?
 
   185     ///\bug Should be tested in the concept checker whether it is defined
 
   185     ///\bug Should be tested in the concept checker whether it is defined
 
   186     ///correctly.
 
   186     ///correctly.
 
   187     typedef True UndirTag;
 
   187     typedef True UTag;
 
   188 
   188 
   189     typedef IterableGraphExtender<_Base> Parent;
 
   189     typedef IterableGraphExtender<_Base> Parent;
 
   190     typedef IterableUndirGraphExtender<_Base> Graph;
 
   190     typedef IterableUGraphExtender<_Base> Graph;
 
   191     typedef typename Parent::Node Node;
 
   191     typedef typename Parent::Node Node;
 
   192     typedef typename Parent::Edge Edge;
 
   192     typedef typename Parent::Edge Edge;
 
   193     typedef typename Parent::UndirEdge UndirEdge;
 
   193     typedef typename Parent::UEdge UEdge;
 
   194 
   194 
   195     class UndirEdgeIt : public Parent::UndirEdge { 
   195     class UEdgeIt : public Parent::UEdge { 
   196       const Graph* graph;
 
   196       const Graph* graph;
 
   197     public:
 
   197     public:
 
   198 
   198 
   199       UndirEdgeIt() { }
 
   199       UEdgeIt() { }
 
   200 
   200 
   201       UndirEdgeIt(Invalid i) : UndirEdge(i) { }
 
   201       UEdgeIt(Invalid i) : UEdge(i) { }
 
   202 
   202 
   203       explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
 
   203       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
 
   204 	_graph.first(*static_cast<UndirEdge*>(this));
 
   204 	_graph.first(*static_cast<UEdge*>(this));
 
   205       }
 
   205       }
 
   206 
   206 
   207       UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : 
   207       UEdgeIt(const Graph& _graph, const UEdge& e) : 
   208 	UndirEdge(e), graph(&_graph) { }
 
   208 	UEdge(e), graph(&_graph) { }
 
   209 
   209 
   210       UndirEdgeIt& operator++() { 
   210       UEdgeIt& operator++() { 
   211 	graph->next(*this);
 
   211 	graph->next(*this);
 
   212 	return *this; 
   212 	return *this; 
   213       }
 
   213       }
 
   214 
   214 
   215     };
 
   215     };
 
   216 
   216 
   217     class IncEdgeIt : public Parent::UndirEdge { 
   217     class IncEdgeIt : public Parent::UEdge { 
   218       const Graph* graph;
 
   218       const Graph* graph;
 
   219       bool direction;
 
   219       bool direction;
 
   220       friend class IterableUndirGraphExtender;
 
   220       friend class IterableUGraphExtender;
 
   221     public:
 
   221     public:
 
   222 
   222 
   223       IncEdgeIt() { }
 
   223       IncEdgeIt() { }
 
   224 
   224 
   225       IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
 
   225       IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
 
   226 
   226 
   227       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
 
   227       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
 
   228 	_graph.firstInc(*this, direction, n);
 
   228 	_graph.firstInc(*this, direction, n);
 
   229       }
 
   229       }
 
   230 
   230 
   231       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
 
   231       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
 
   232 	: graph(&_graph), UndirEdge(ue) {
 
   232 	: graph(&_graph), UEdge(ue) {
 
   233 	direction = (_graph.source(ue) == n);
 
   233 	direction = (_graph.source(ue) == n);
 
   234       }
 
   234       }
 
   235 
   235 
   236       IncEdgeIt& operator++() {
 
   236       IncEdgeIt& operator++() {
 
   237 	graph->nextInc(*this, direction);
 
   237 	graph->nextInc(*this, direction);
 
   256     }
 
   256     }
 
   257 
   257 
   258     /// \brief The opposite node on the given undirected edge.
 
   258     /// \brief The opposite node on the given undirected edge.
 
   259     ///
 
   259     ///
 
   260     /// Gives back the opposite on the given undirected edge.
 
   260     /// Gives back the opposite on the given undirected edge.
 
   261     Node oppositeNode(const Node& n, const UndirEdge& e) const {
 
   261     Node oppositeNode(const Node& n, const UEdge& e) const {
 
   262       if (Parent::source(e) == n) {
 
   262       if (Parent::source(e) == n) {
 
   263 	return Parent::target(e);
 
   263 	return Parent::target(e);
 
   264       } else {
 
   264       } else {
 
   265 	return Parent::source(e);
 
   265 	return Parent::source(e);
 
   266       }
 
   266       }
 
   268 
   268 
   269   };
 
   269   };
 
   270 
   270 
   271 
   271 
   272   template <typename _Base>
 
   272   template <typename _Base>
 
   273   class IterableUndirBipartiteGraphExtender : public _Base {
 
   273   class IterableUBipartiteGraphExtender : public _Base {
 
   274   public:
 
   274   public:
 
   275     typedef _Base Parent;
 
   275     typedef _Base Parent;
 
   276     typedef IterableUndirBipartiteGraphExtender Graph;
 
   276     typedef IterableUBipartiteGraphExtender Graph;
 
   277    
   277    
   278     typedef typename Parent::Node Node;
 
   278     typedef typename Parent::Node Node;
 
   279     typedef typename Parent::UpperNode UpperNode;
 
   279     typedef typename Parent::UpperNode UpperNode;
 
   280     typedef typename Parent::LowerNode LowerNode;
 
   280     typedef typename Parent::LowerNode LowerNode;
 
   281     typedef typename Parent::Edge Edge;
 
   281     typedef typename Parent::Edge Edge;
 
   282     typedef typename Parent::UndirEdge UndirEdge;
 
   282     typedef typename Parent::UEdge UEdge;
 
   283   
   283   
   284     class NodeIt : public Node { 
   284     class NodeIt : public Node { 
   285       const Graph* graph;
 
   285       const Graph* graph;
 
   286     public:
 
   286     public:
 
   287     
   287     
   302       }
 
   302       }
 
   303 
   303 
   304     };
 
   304     };
 
   305 
   305 
   306     class UpperNodeIt : public Node { 
   306     class UpperNodeIt : public Node { 
   307       friend class IterableUndirBipartiteGraphExtender;
 
   307       friend class IterableUBipartiteGraphExtender;
 
   308       const Graph* graph;
 
   308       const Graph* graph;
 
   309     public:
 
   309     public:
 
   310     
   310     
   311       UpperNodeIt() { }
 
   311       UpperNodeIt() { }
 
   312     
   312     
   324 	return *this; 
   324 	return *this; 
   325       }
 
   325       }
 
   326     };
 
   326     };
 
   327 
   327 
   328     class LowerNodeIt : public Node { 
   328     class LowerNodeIt : public Node { 
   329       friend class IterableUndirBipartiteGraphExtender;
 
   329       friend class IterableUBipartiteGraphExtender;
 
   330       const Graph* graph;
 
   330       const Graph* graph;
 
   331     public:
 
   331     public:
 
   332     
   332     
   333       LowerNodeIt() { }
 
   333       LowerNodeIt() { }
 
   334     
   334     
   346 	return *this; 
   346 	return *this; 
   347       }
 
   347       }
 
   348     };
 
   348     };
 
   349 
   349 
   350     class EdgeIt : public Edge { 
   350     class EdgeIt : public Edge { 
   351       friend class IterableUndirBipartiteGraphExtender;
 
   351       friend class IterableUBipartiteGraphExtender;
 
   352       const Graph* graph;
 
   352       const Graph* graph;
 
   353     public:
 
   353     public:
 
   354     
   354     
   355       EdgeIt() { }
 
   355       EdgeIt() { }
 
   356     
   356     
   368 	return *this; 
   368 	return *this; 
   369       }
 
   369       }
 
   370 
   370 
   371     };
 
   371     };
 
   372 
   372 
   373     class UndirEdgeIt : public UndirEdge { 
   373     class UEdgeIt : public UEdge { 
   374       friend class IterableUndirBipartiteGraphExtender;
 
   374       friend class IterableUBipartiteGraphExtender;
 
   375       const Graph* graph;
 
   375       const Graph* graph;
 
   376     public:
 
   376     public:
 
   377     
   377     
   378       UndirEdgeIt() { }
 
   378       UEdgeIt() { }
 
   379     
   379     
   380       UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }
 
   380       UEdgeIt(Invalid i) : UEdge(INVALID) { }
 
   381     
   381     
   382       explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
 
   382       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
 
   383 	graph->first(static_cast<UndirEdge&>(*this));
 
   383 	graph->first(static_cast<UEdge&>(*this));
 
   384       }
 
   384       }
 
   385 
   385 
   386       UndirEdgeIt(const Graph& _graph, const UndirEdge& edge) 
   386       UEdgeIt(const Graph& _graph, const UEdge& edge) 
   387 	: UndirEdge(edge), graph(&_graph) { }
 
   387 	: UEdge(edge), graph(&_graph) { }
 
   388     
   388     
   389       UndirEdgeIt& operator++() { 
   389       UEdgeIt& operator++() { 
   390 	graph->next(*this);
 
   390 	graph->next(*this);
 
   391 	return *this; 
   391 	return *this; 
   392       }
 
   392       }
 
   393     };
 
   393     };
 
   394 
   394 
   395     class OutEdgeIt : public Edge { 
   395     class OutEdgeIt : public Edge { 
   396       friend class IterableUndirBipartiteGraphExtender;
 
   396       friend class IterableUBipartiteGraphExtender;
 
   397       const Graph* graph;
 
   397       const Graph* graph;
 
   398     public:
 
   398     public:
 
   399     
   399     
   400       OutEdgeIt() { }
 
   400       OutEdgeIt() { }
 
   401     
   401     
   416 
   416 
   417     };
 
   417     };
 
   418 
   418 
   419 
   419 
   420     class InEdgeIt : public Edge { 
   420     class InEdgeIt : public Edge { 
   421       friend class IterableUndirBipartiteGraphExtender;
 
   421       friend class IterableUBipartiteGraphExtender;
 
   422       const Graph* graph;
 
   422       const Graph* graph;
 
   423     public:
 
   423     public:
 
   424     
   424     
   425       InEdgeIt() { }
 
   425       InEdgeIt() { }
 
   426     
   426     
   467     /// iterator
 
   467     /// iterator
 
   468     Node runningNode(const InEdgeIt &e) const {
 
   468     Node runningNode(const InEdgeIt &e) const {
 
   469       return Parent::source((Edge&)e);
 
   469       return Parent::source((Edge&)e);
 
   470     }
 
   470     }
 
   471   
   471   
   472     class IncEdgeIt : public Parent::UndirEdge { 
   472     class IncEdgeIt : public Parent::UEdge { 
   473       friend class IterableUndirBipartiteGraphExtender;
 
   473       friend class IterableUBipartiteGraphExtender;
 
   474       const Graph* graph;
 
   474       const Graph* graph;
 
   475       bool direction;
 
   475       bool direction;
 
   476     public:
 
   476     public:
 
   477     
   477     
   478       IncEdgeIt() { }
 
   478       IncEdgeIt() { }
 
   479     
   479     
   480       IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }
 
   480       IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
 
   481     
   481     
   482       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
 
   482       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
 
   483 	graph->firstInc(*this, direction, n);
 
   483 	graph->firstInc(*this, direction, n);
 
   484       }
 
   484       }
 
   485 
   485 
   486       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
 
   486       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
 
   487 	: graph(&_graph), UndirEdge(ue) {
 
   487 	: graph(&_graph), UEdge(ue) {
 
   488 	direction = (graph->source(ue) == n);
 
   488 	direction = (graph->source(ue) == n);
 
   489       }
 
   489       }
 
   490 
   490 
   491       IncEdgeIt& operator++() {
 
   491       IncEdgeIt& operator++() {
 
   492 	graph->nextInc(*this, direction);
 
   492 	graph->nextInc(*this, direction);
lemon-0.x