# HG changeset patch # User deba # Date 1164133328 0 # Node ID 42cce226b87b4460ef4293a84c311fef67072817 # Parent 4a2236cc98a03a1f2b37a09f3e53a7f0d60f6ebc BfsVisitor Bipartite partitions based on visitors topology_demo.cc => scaleToA4 works without extra parameters diff -r 4a2236cc98a0 -r 42cce226b87b demo/topology_demo.cc --- a/demo/topology_demo.cc Tue Nov 21 17:28:08 2006 +0000 +++ b/demo/topology_demo.cc Tue Nov 21 18:22:08 2006 +0000 @@ -36,6 +36,7 @@ /// \include topology_demo.cc using namespace lemon; +using namespace lemon::dim2; using namespace std; @@ -49,7 +50,7 @@ typedef Graph::Node Node; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("u_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -63,7 +64,6 @@ graphToEps(graph, "connected_components.eps").undirected(). coords(coords).scaleToA4().enableParallel(). - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). nodeColors(composeMap(palette, compMap)).run(); std::cout << "Result: connected_components.eps" << std::endl; @@ -74,7 +74,7 @@ typedef Graph::Node Node; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); GraphReader("dir_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -89,9 +89,7 @@ stronglyConnectedCutEdges(graph, cutMap); graphToEps(graph, "strongly_connected_components.eps"). - coords(coords).scaleToA4().enableParallel(). - drawArrows().arrowWidth(10.0).arrowLength(10.0). - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). + coords(coords).scaleToA4().enableParallel().drawArrows(). nodeColors(composeMap(palette, compMap)). edgeColors(composeMap(functorMap(&color), cutMap)).run(); @@ -104,7 +102,7 @@ typedef Graph::UEdge UEdge; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("u_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -120,7 +118,6 @@ graphToEps(graph, "bi_node_connected_components.eps").undirected(). coords(coords).scaleToA4().enableParallel(). - parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0). edgeColors(composeMap(palette, compMap)). nodeColors(composeMap(functorMap(&color), cutMap)). run(); @@ -134,7 +131,7 @@ typedef Graph::UEdge UEdge; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("u_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -150,7 +147,6 @@ graphToEps(graph, "bi_edge_connected_components.eps").undirected(). coords(coords).scaleToA4().enableParallel(). - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). nodeColors(composeMap(palette, compMap)). edgeColors(composeMap(functorMap(&color), cutMap)).run(); @@ -163,7 +159,7 @@ typedef Graph::UEdge UEdge; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("partitions.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -177,7 +173,6 @@ graphToEps(graph, "bipartite_partitions.eps").undirected(). coords(coords).scaleToA4().enableParallel(). - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). nodeColors(composeMap(functorMap(&color), partMap)).run(); std::cout << "Result: bipartite_partitions.eps" << std::endl; diff -r 4a2236cc98a0 -r 42cce226b87b lemon/bfs.h --- a/lemon/bfs.h Tue Nov 21 17:28:08 2006 +0000 +++ b/lemon/bfs.h Tue Nov 21 18:22:08 2006 +0000 @@ -587,9 +587,9 @@ while ( !emptyQueue() ) processNextNode(); } - ///Executes the algorithm until \c dest is reached. + ///Executes the algorithm until \c dest is the next node to processed. - ///Executes the algorithm until \c dest is reached. + ///Executes the algorithm until \c dest is the next node to processed. /// ///\pre init() must be called and at least one node should be added ///with addSource() before using this function. @@ -614,8 +614,9 @@ ///\pre init() must be called and at least one node should be added ///with addSource() before using this function. /// - ///\param nm must be a bool (or convertible) node map. The algorithm - ///will stop when it reaches a node \c v with nm[v]==true. + ///\param nm must be a bool (or convertible) node map. The + ///algorithm will stop when for the next processable node \c v is + ///nm[v] true. ///\todo query the reached target template void start(const NM &nm) @@ -633,11 +634,11 @@ ///- The shortest path tree. ///- The distance of each node from the root. /// - ///\note d.run(s) is just a shortcut of the following code. + ///\note b.run(s) is just a shortcut of the following code. ///\code - /// d.init(); - /// d.addSource(s); - /// d.start(); + /// b.init(); + /// b.addSource(s); + /// b.start(); ///\endcode void run(Node s) { init(); @@ -651,12 +652,12 @@ /// ///\return The length of the shortest s---t path if there exists one, ///0 otherwise. - ///\note Apart from the return value, d.run(s) is + ///\note Apart from the return value, b.run(s) is ///just a shortcut of the following code. ///\code - /// d.init(); - /// d.addSource(s); - /// d.start(t); + /// b.init(); + /// b.addSource(s); + /// b.start(t); ///\endcode int run(Node s,Node t) { init(); @@ -671,7 +672,7 @@ ///The result of the %BFS algorithm can be obtained using these ///functions.\n ///Before the use of these functions, - ///either run() or start() must be called. + ///either run() or start() must be calleb. ///@{ @@ -943,7 +944,7 @@ ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; -public: + public: /// Constructor. BfsWizard() : TR() {} @@ -1104,6 +1105,495 @@ return BfsWizard >(g,s); } +#ifdef DOXYGEN + /// \brief Visitor class for bfs. + /// + /// It gives a simple interface for a functional interface for bfs + /// traversal. The traversal on a linear data structure. + template + struct BfsVisitor { + typedef _Graph Graph; + typedef typename Graph::Edge Edge; + typedef typename Graph::Node Node; + /// \brief Called when the edge reach a node. + /// + /// It is called when the bfs find an edge which target is not + /// reached yet. + void discover(const Edge& edge) {} + /// \brief Called when the node reached first time. + /// + /// It is Called when the node reached first time. + void reach(const Node& node) {} + /// \brief Called when the edge examined but target of the edge + /// already discovered. + /// + /// It called when the edge examined but the target of the edge + /// already discovered. + void examine(const Edge& edge) {} + /// \brief Called for the source node of the bfs. + /// + /// It is called for the source node of the bfs. + void start(const Node& node) {} + /// \brief Called when the node processed. + /// + /// It is Called when the node processed. + void process(const Node& node) {} + }; +#else + template + struct BfsVisitor { + typedef _Graph Graph; + typedef typename Graph::Edge Edge; + typedef typename Graph::Node Node; + void discover(const Edge&) {} + void reach(const Node&) {} + void examine(const Edge&) {} + void start(const Node&) {} + void process(const Node&) {} + + template + struct Constraints { + void constraints() { + Edge edge; + Node node; + visitor.discover(edge); + visitor.reach(node); + visitor.examine(edge); + visitor.start(node); + visitor.process(node); + } + _Visitor& visitor; + }; + }; +#endif + + /// \brief Default traits class of BfsVisit class. + /// + /// Default traits class of BfsVisit class. + /// \param _Graph Graph type. + template + struct BfsVisitDefaultTraits { + + /// \brief The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that indicates which nodes are reached. + /// + /// The type of the map that indicates which nodes are reached. + /// It must meet the \ref concepts::WriteMap "WriteMap" concept. + /// \todo named parameter to set this type, function to read and write. + typedef typename Graph::template NodeMap ReachedMap; + + /// \brief Instantiates a ReachedMap. + /// + /// This function instantiates a \ref ReachedMap. + /// \param graph is the graph, to which + /// we would like to define the \ref ReachedMap. + static ReachedMap *createReachedMap(const Graph &graph) { + return new ReachedMap(graph); + } + + }; + + /// %BFS Visit algorithm class. + + /// \ingroup flowalgs + /// This class provides an efficient implementation of the %BFS algorithm + /// with visitor interface. + /// + /// The %BfsVisit class provides an alternative interface to the Bfs + /// class. It works with callback mechanism, the BfsVisit object calls + /// on every bfs event the \c Visitor class member functions. + /// + /// \param _Graph The graph type the algorithm runs on. The default value is + /// \ref ListGraph. The value of _Graph is not used directly by Bfs, it + /// is only passed to \ref BfsDefaultTraits. + /// \param _Visitor The Visitor object for the algorithm. The + /// \ref BfsVisitor "BfsVisitor<_Graph>" is an empty Visitor which + /// does not observe the Bfs events. If you want to observe the bfs + /// events you should implement your own Visitor class. + /// \param _Traits Traits class to set various data types used by the + /// algorithm. The default traits class is + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Graph>". + /// See \ref BfsVisitDefaultTraits for the documentation of + /// a Bfs visit traits class. + /// + /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso +#ifdef DOXYGEN + template +#else + template , + typename _Traits = BfsDefaultTraits<_Graph> > +#endif + class BfsVisit { + public: + + /// \brief \ref Exception for uninitialized parameters. + /// + /// This error represents problems in the initialization + /// of the parameters of the algorithms. + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* what() const throw() + { + return "lemon::BfsVisit::UninitializedParameter"; + } + }; + + typedef _Traits Traits; + + typedef typename Traits::Graph Graph; + + typedef _Visitor Visitor; + + ///The type of the map indicating which nodes are reached. + typedef typename Traits::ReachedMap ReachedMap; + + private: + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + /// Pointer to the underlying graph. + const Graph *_graph; + /// Pointer to the visitor object. + Visitor *_visitor; + ///Pointer to the map of reached status of the nodes. + ReachedMap *_reached; + ///Indicates if \ref _reached is locally allocated (\c true) or not. + bool local_reached; + + std::vector _list; + int _list_front, _list_back; + + /// \brief Creates the maps if necessary. + /// + /// Creates the maps if necessary. + void create_maps() { + if(!_reached) { + local_reached = true; + _reached = Traits::createReachedMap(*_graph); + } + } + + protected: + + BfsVisit() {} + + public: + + typedef BfsVisit Create; + + /// \name Named template parameters + + ///@{ + template + struct DefReachedMapTraits : public Traits { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &graph) { + throw UninitializedParameter(); + } + }; + /// \brief \ref named-templ-param "Named parameter" for setting + /// ReachedMap type + /// + /// \ref named-templ-param "Named parameter" for setting ReachedMap type + template + struct DefReachedMap : public BfsVisit< Graph, Visitor, + DefReachedMapTraits > { + typedef BfsVisit< Graph, Visitor, DefReachedMapTraits > Create; + }; + ///@} + + public: + + /// \brief Constructor. + /// + /// Constructor. + /// + /// \param graph the graph the algorithm will run on. + /// \param visitor The visitor of the algorithm. + /// + BfsVisit(const Graph& graph, Visitor& visitor) + : _graph(&graph), _visitor(&visitor), + _reached(0), local_reached(false) {} + + /// \brief Destructor. + /// + /// Destructor. + ~BfsVisit() { + if(local_reached) delete _reached; + } + + /// \brief Sets the map indicating if a node is reached. + /// + /// Sets the map indicating if a node is reached. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return (*this) + BfsVisit &reachedMap(ReachedMap &m) { + if(local_reached) { + delete _reached; + local_reached = false; + } + _reached = &m; + return *this; + } + + public: + /// \name Execution control + /// The simplest way to execute the algorithm is to use + /// one of the member functions called \c run(...). + /// \n + /// If you need more control on the execution, + /// first you must call \ref init(), then you can adda source node + /// with \ref addSource(). + /// Finally \ref start() will perform the actual path + /// computation. + + /// @{ + /// \brief Initializes the internal data structures. + /// + /// Initializes the internal data structures. + /// + void init() { + create_maps(); + _list.resize(countNodes(*_graph)); + _list_front = _list_back = -1; + for (NodeIt u(*_graph) ; u != INVALID ; ++u) { + _reached->set(u, false); + } + } + + /// \brief Adds a new source node. + /// + /// Adds a new source node to the set of nodes to be processed. + void addSource(Node s) { + if(!(*_reached)[s]) { + _reached->set(s,true); + _visitor->start(s); + _visitor->reach(s); + _list[++_list_back] = s; + } + } + + /// \brief Processes the next node. + /// + /// Processes the next node. + /// + /// \return The processed node. + /// + /// \pre The queue must not be empty! + Node processNextNode() { + Node n = _list[++_list_front]; + _visitor->process(n); + Edge e; + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) { + Node m = _graph->target(e); + if (!(*_reached)[m]) { + _visitor->discover(e); + _visitor->reach(m); + _reached->set(m, true); + _list[++_list_back] = m; + } else { + _visitor->examine(e); + } + } + return n; + } + + /// \brief Processes the next node. + /// + /// Processes the next node. And checks that the given target node + /// is reached. If the target node is reachable from the processed + /// node then the reached parameter will be set true. The reached + /// parameter should be initially false. + /// + /// \param target The target node. + /// \retval reached Indicates that the target node is reached. + /// \return The processed node. + /// + /// \warning The queue must not be empty! + Node processNextNode(Node target, bool& reached) { + Node n = _list[++_list_front]; + _visitor->process(n); + Edge e; + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) { + Node m = _graph->target(e); + if (!(*_reached)[m]) { + _visitor->discover(e); + _visitor->reach(m); + _reached->set(m, true); + _list[++_list_back] = m; + reached = reached || (target == m); + } else { + _visitor->examine(e); + } + } + return n; + } + + /// \brief Processes the next node. + /// + /// Processes the next node. And checks that at least one of + /// reached node has true value in the \c nm nodemap. If one node + /// with true value is reachable from the processed node then the + /// reached parameter will be set true. The reached parameter + /// should be initially false. + /// + /// \param target The nodemaps of possible targets. + /// \retval reached Indicates that one of the target nodes is reached. + /// \return The processed node. + /// + /// \warning The queue must not be empty! + template + Node processNextNode(const NM& nm, bool& reached) { + Node n = _list[++_list_front]; + _visitor->process(n); + Edge e; + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) { + Node m = _graph->target(e); + if (!(*_reached)[m]) { + _visitor->discover(e); + _visitor->reach(m); + _reached->set(m, true); + _list[++_list_back] = m; + reached = reached || nm[m]; + } else { + _visitor->examine(e); + } + } + return n; + } + + /// \brief Next node to be processed. + /// + /// Next node to be processed. + /// + /// \return The next node to be processed or INVALID if the stack is + /// empty. + Node nextNode() { + return _list_front != _list_back ? _list[_list_front + 1] : INVALID; + } + + /// \brief Returns \c false if there are nodes + /// to be processed in the queue + /// + /// Returns \c false if there are nodes + /// to be processed in the queue + bool emptyQueue() { return _list_front == _list_back; } + + /// \brief Returns the number of the nodes to be processed. + /// + /// Returns the number of the nodes to be processed in the queue. + int queueSize() { return _list_back - _list_front; } + + /// \brief Executes the algorithm. + /// + /// Executes the algorithm. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + void start() { + while ( !emptyQueue() ) processNextNode(); + } + + /// \brief Executes the algorithm until \c dest will be next processed. + /// + /// Executes the algorithm until \c dest will be next processed. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + void start(Node dest) { + bool reached = false; + while (!emptyQueue() && !reached) { + processNextNode(dest, reached); + } + } + + /// \brief Executes the algorithm until a condition is met. + /// + /// Executes the algorithm until a condition is met. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + /// + ///\param nm must be a bool (or convertible) node map. The + ///algorithm will stop when it reaches a node \c v with + ///nm[v] true. + template + void start(const NM &nm) { + bool reached = false; + while (!emptyQueue() && !reached) { + processNextNode(nm, reached); + } + } + + /// \brief Runs %BFSVisit algorithm from node \c s. + /// + /// This method runs the %BFS algorithm from a root node \c s. + /// \note b.run(s) is just a shortcut of the following code. + ///\code + /// b.init(); + /// b.addSource(s); + /// b.start(); + ///\endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + /// \brief Runs %BFSVisit algorithm to visit all nodes in the graph. + /// + /// This method runs the %BFS algorithm in order to + /// compute the %BFS path to each node. The algorithm computes + /// - The %BFS tree. + /// - The distance of each node from the root in the %BFS tree. + /// + ///\note b.run() is just a shortcut of the following code. + ///\code + /// b.init(); + /// for (NodeIt it(graph); it != INVALID; ++it) { + /// if (!b.reached(it)) { + /// b.addSource(it); + /// b.start(); + /// } + /// } + ///\endcode + void run() { + init(); + for (NodeIt it(*_graph); it != INVALID; ++it) { + if (!reached(it)) { + addSource(it); + start(); + } + } + } + ///@} + + /// \name Query Functions + /// The result of the %BFS algorithm can be obtained using these + /// functions.\n + /// Before the use of these functions, + /// either run() or start() must be called. + ///@{ + + /// \brief Checks if a node is reachable from the root. + /// + /// Returns \c true if \c v is reachable from the root(s). + /// \warning The source nodes are inditated as unreachable. + /// \pre Either \ref run() or \ref start() + /// must be called before using this function. + /// + bool reached(Node v) { return (*_reached)[v]; } + ///@} + }; + } //END OF NAMESPACE LEMON #endif diff -r 4a2236cc98a0 -r 42cce226b87b lemon/topology.h --- a/lemon/topology.h Tue Nov 21 17:28:08 2006 +0000 +++ b/lemon/topology.h Tue Nov 21 18:22:08 2006 +0000 @@ -1389,6 +1389,64 @@ return true; } + namespace _topology_bits { + + template + class BipartiteVisitor : public BfsVisitor { + public: + typedef typename Graph::Edge Edge; + typedef typename Graph::Node Node; + + BipartiteVisitor(const Graph& graph, bool& bipartite) + : _graph(graph), _part(graph), _bipartite(bipartite) {} + + void start(const Node& node) { + _part[node] = true; + } + void discover(const Edge& edge) { + _part.set(_graph.target(edge), !_part[_graph.source(edge)]); + } + void examine(const Edge& edge) { + _bipartite = _bipartite && + _part[_graph.target(edge)] != _part[_graph.source(edge)]; + } + + private: + + const Graph& _graph; + typename Graph::template NodeMap _part; + bool& _bipartite; + }; + + template + class BipartitePartitionsVisitor : public BfsVisitor { + public: + typedef typename Graph::Edge Edge; + typedef typename Graph::Node Node; + + BipartitePartitionsVisitor(const Graph& graph, + PartMap& part, bool& bipartite) + : _graph(graph), _part(part), _bipartite(bipartite) {} + + void start(const Node& node) { + _part.set(node, true); + } + void discover(const Edge& edge) { + _part.set(_graph.target(edge), !_part[_graph.source(edge)]); + } + void examine(const Edge& edge) { + _bipartite = _bipartite && + _part[_graph.target(edge)] != _part[_graph.source(edge)]; + } + + private: + + const Graph& _graph; + PartMap& _part; + bool& _bipartite; + }; + } + /// \ingroup topology /// /// \brief Check if the given undirected graph is bipartite or not @@ -1402,21 +1460,29 @@ /// \author Balazs Attila Mihaly template inline bool bipartite(const UGraph &graph){ + using namespace _topology_bits; + checkConcept(); typedef typename UGraph::NodeIt NodeIt; typedef typename UGraph::EdgeIt EdgeIt; - Bfs bfs(graph); + bool bipartite = true; + + BipartiteVisitor + visitor(graph, bipartite); + BfsVisit > + bfs(graph, visitor); bfs.init(); - for(NodeIt i(graph);i!=INVALID;++i){ - if(!bfs.reached(i)){ - bfs.run(i); + for(NodeIt it(graph); it != INVALID; ++it) { + if(!bfs.reached(it)){ + bfs.addSource(it); + while (!bfs.emptyQueue()) { + bfs.processNextNode(); + if (!bipartite) return false; + } } } - for(EdgeIt i(graph);i!=INVALID;++i){ - if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false; - } return true; } @@ -1439,25 +1505,80 @@ /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth template inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ + using namespace _topology_bits; + checkConcept(); typedef typename UGraph::Node Node; typedef typename UGraph::NodeIt NodeIt; typedef typename UGraph::EdgeIt EdgeIt; - - Bfs bfs(graph); + + bool bipartite = true; + + BipartitePartitionsVisitor + visitor(graph, partMap, bipartite); + BfsVisit > + bfs(graph, visitor); bfs.init(); - for(NodeIt i(graph);i!=INVALID;++i){ - if(!bfs.reached(i)){ - bfs.addSource(i); - for(Node j=bfs.processNextNode();!bfs.emptyQueue(); - j=bfs.processNextNode()){ - partMap.set(j,bfs.dist(j)%2==0); - } + for(NodeIt it(graph); it != INVALID; ++it) { + if(!bfs.reached(it)){ + bfs.addSource(it); + while (!bfs.emptyQueue()) { + bfs.processNextNode(); + if (!bipartite) return false; + } } } - for(EdgeIt i(graph);i!=INVALID;++i){ - if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false; + return true; + } + + /// \brief Returns true when there is not loop edge in the graph. + /// + /// Returns true when there is not loop edge in the graph. + template + bool loopFree(const Graph& graph) { + for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) { + if (graph.source(it) == graph.target(it)) return false; + } + return true; + } + + /// \brief Returns true when there is not parallel edges in the graph. + /// + /// Returns true when there is not parallel edges in the graph. + template + bool parallelFree(const Graph& graph) { + typename Graph::template NodeMap reached(graph, false); + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { + if (reached[graph.target(e)]) return false; + reached.set(graph.target(e), true); + } + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { + reached.set(graph.target(e), false); + } + } + return true; + } + + /// \brief Returns true when there is not loop edge and parallel + /// edges in the graph. + /// + /// Returns true when there is not loop edge and parallel edges in + /// the graph. + template + bool simpleGraph(const Graph& graph) { + typename Graph::template NodeMap reached(graph, false); + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { + reached.set(n, true); + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { + if (reached[graph.target(e)]) return false; + reached.set(graph.target(e), true); + } + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { + reached.set(graph.target(e), false); + } + reached.set(n, false); } return true; }