1.1 --- a/demo/topology_demo.cc Tue Nov 21 17:28:08 2006 +0000
1.2 +++ b/demo/topology_demo.cc Tue Nov 21 18:22:08 2006 +0000
1.3 @@ -36,6 +36,7 @@
1.4 /// \include topology_demo.cc
1.5
1.6 using namespace lemon;
1.7 +using namespace lemon::dim2;
1.8 using namespace std;
1.9
1.10
1.11 @@ -49,7 +50,7 @@
1.12 typedef Graph::Node Node;
1.13
1.14 Graph graph;
1.15 - Graph::NodeMap<dim2::Point<double> > coords(graph);
1.16 + Graph::NodeMap<Point<double> > coords(graph);
1.17
1.18 UGraphReader<Graph>("u_components.lgf", graph).
1.19 readNodeMap("coordinates_x", xMap(coords)).
1.20 @@ -63,7 +64,6 @@
1.21
1.22 graphToEps(graph, "connected_components.eps").undirected().
1.23 coords(coords).scaleToA4().enableParallel().
1.24 - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
1.25 nodeColors(composeMap(palette, compMap)).run();
1.26
1.27 std::cout << "Result: connected_components.eps" << std::endl;
1.28 @@ -74,7 +74,7 @@
1.29 typedef Graph::Node Node;
1.30
1.31 Graph graph;
1.32 - Graph::NodeMap<dim2::Point<double> > coords(graph);
1.33 + Graph::NodeMap<Point<double> > coords(graph);
1.34
1.35 GraphReader<Graph>("dir_components.lgf", graph).
1.36 readNodeMap("coordinates_x", xMap(coords)).
1.37 @@ -89,9 +89,7 @@
1.38 stronglyConnectedCutEdges(graph, cutMap);
1.39
1.40 graphToEps(graph, "strongly_connected_components.eps").
1.41 - coords(coords).scaleToA4().enableParallel().
1.42 - drawArrows().arrowWidth(10.0).arrowLength(10.0).
1.43 - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
1.44 + coords(coords).scaleToA4().enableParallel().drawArrows().
1.45 nodeColors(composeMap(palette, compMap)).
1.46 edgeColors(composeMap(functorMap(&color), cutMap)).run();
1.47
1.48 @@ -104,7 +102,7 @@
1.49 typedef Graph::UEdge UEdge;
1.50
1.51 Graph graph;
1.52 - Graph::NodeMap<dim2::Point<double> > coords(graph);
1.53 + Graph::NodeMap<Point<double> > coords(graph);
1.54
1.55 UGraphReader<Graph>("u_components.lgf", graph).
1.56 readNodeMap("coordinates_x", xMap(coords)).
1.57 @@ -120,7 +118,6 @@
1.58
1.59 graphToEps(graph, "bi_node_connected_components.eps").undirected().
1.60 coords(coords).scaleToA4().enableParallel().
1.61 - parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
1.62 edgeColors(composeMap(palette, compMap)).
1.63 nodeColors(composeMap(functorMap(&color), cutMap)).
1.64 run();
1.65 @@ -134,7 +131,7 @@
1.66 typedef Graph::UEdge UEdge;
1.67
1.68 Graph graph;
1.69 - Graph::NodeMap<dim2::Point<double> > coords(graph);
1.70 + Graph::NodeMap<Point<double> > coords(graph);
1.71
1.72 UGraphReader<Graph>("u_components.lgf", graph).
1.73 readNodeMap("coordinates_x", xMap(coords)).
1.74 @@ -150,7 +147,6 @@
1.75
1.76 graphToEps(graph, "bi_edge_connected_components.eps").undirected().
1.77 coords(coords).scaleToA4().enableParallel().
1.78 - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
1.79 nodeColors(composeMap(palette, compMap)).
1.80 edgeColors(composeMap(functorMap(&color), cutMap)).run();
1.81
1.82 @@ -163,7 +159,7 @@
1.83 typedef Graph::UEdge UEdge;
1.84
1.85 Graph graph;
1.86 - Graph::NodeMap<dim2::Point<double> > coords(graph);
1.87 + Graph::NodeMap<Point<double> > coords(graph);
1.88
1.89 UGraphReader<Graph>("partitions.lgf", graph).
1.90 readNodeMap("coordinates_x", xMap(coords)).
1.91 @@ -177,7 +173,6 @@
1.92
1.93 graphToEps(graph, "bipartite_partitions.eps").undirected().
1.94 coords(coords).scaleToA4().enableParallel().
1.95 - parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
1.96 nodeColors(composeMap(functorMap(&color), partMap)).run();
1.97
1.98 std::cout << "Result: bipartite_partitions.eps" << std::endl;
2.1 --- a/lemon/bfs.h Tue Nov 21 17:28:08 2006 +0000
2.2 +++ b/lemon/bfs.h Tue Nov 21 18:22:08 2006 +0000
2.3 @@ -587,9 +587,9 @@
2.4 while ( !emptyQueue() ) processNextNode();
2.5 }
2.6
2.7 - ///Executes the algorithm until \c dest is reached.
2.8 + ///Executes the algorithm until \c dest is the next node to processed.
2.9
2.10 - ///Executes the algorithm until \c dest is reached.
2.11 + ///Executes the algorithm until \c dest is the next node to processed.
2.12 ///
2.13 ///\pre init() must be called and at least one node should be added
2.14 ///with addSource() before using this function.
2.15 @@ -614,8 +614,9 @@
2.16 ///\pre init() must be called and at least one node should be added
2.17 ///with addSource() before using this function.
2.18 ///
2.19 - ///\param nm must be a bool (or convertible) node map. The algorithm
2.20 - ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
2.21 + ///\param nm must be a bool (or convertible) node map. The
2.22 + ///algorithm will stop when for the next processable node \c v is
2.23 + ///<tt>nm[v]</tt> true.
2.24 ///\todo query the reached target
2.25 template<class NM>
2.26 void start(const NM &nm)
2.27 @@ -633,11 +634,11 @@
2.28 ///- The shortest path tree.
2.29 ///- The distance of each node from the root.
2.30 ///
2.31 - ///\note d.run(s) is just a shortcut of the following code.
2.32 + ///\note b.run(s) is just a shortcut of the following code.
2.33 ///\code
2.34 - /// d.init();
2.35 - /// d.addSource(s);
2.36 - /// d.start();
2.37 + /// b.init();
2.38 + /// b.addSource(s);
2.39 + /// b.start();
2.40 ///\endcode
2.41 void run(Node s) {
2.42 init();
2.43 @@ -651,12 +652,12 @@
2.44 ///
2.45 ///\return The length of the shortest s---t path if there exists one,
2.46 ///0 otherwise.
2.47 - ///\note Apart from the return value, d.run(s) is
2.48 + ///\note Apart from the return value, b.run(s) is
2.49 ///just a shortcut of the following code.
2.50 ///\code
2.51 - /// d.init();
2.52 - /// d.addSource(s);
2.53 - /// d.start(t);
2.54 + /// b.init();
2.55 + /// b.addSource(s);
2.56 + /// b.start(t);
2.57 ///\endcode
2.58 int run(Node s,Node t) {
2.59 init();
2.60 @@ -671,7 +672,7 @@
2.61 ///The result of the %BFS algorithm can be obtained using these
2.62 ///functions.\n
2.63 ///Before the use of these functions,
2.64 - ///either run() or start() must be called.
2.65 + ///either run() or start() must be calleb.
2.66
2.67 ///@{
2.68
2.69 @@ -943,7 +944,7 @@
2.70 ///The type of the map that stores the dists of the nodes.
2.71 typedef typename TR::DistMap DistMap;
2.72
2.73 -public:
2.74 + public:
2.75 /// Constructor.
2.76 BfsWizard() : TR() {}
2.77
2.78 @@ -1104,6 +1105,495 @@
2.79 return BfsWizard<BfsWizardBase<GR> >(g,s);
2.80 }
2.81
2.82 +#ifdef DOXYGEN
2.83 + /// \brief Visitor class for bfs.
2.84 + ///
2.85 + /// It gives a simple interface for a functional interface for bfs
2.86 + /// traversal. The traversal on a linear data structure.
2.87 + template <typename _Graph>
2.88 + struct BfsVisitor {
2.89 + typedef _Graph Graph;
2.90 + typedef typename Graph::Edge Edge;
2.91 + typedef typename Graph::Node Node;
2.92 + /// \brief Called when the edge reach a node.
2.93 + ///
2.94 + /// It is called when the bfs find an edge which target is not
2.95 + /// reached yet.
2.96 + void discover(const Edge& edge) {}
2.97 + /// \brief Called when the node reached first time.
2.98 + ///
2.99 + /// It is Called when the node reached first time.
2.100 + void reach(const Node& node) {}
2.101 + /// \brief Called when the edge examined but target of the edge
2.102 + /// already discovered.
2.103 + ///
2.104 + /// It called when the edge examined but the target of the edge
2.105 + /// already discovered.
2.106 + void examine(const Edge& edge) {}
2.107 + /// \brief Called for the source node of the bfs.
2.108 + ///
2.109 + /// It is called for the source node of the bfs.
2.110 + void start(const Node& node) {}
2.111 + /// \brief Called when the node processed.
2.112 + ///
2.113 + /// It is Called when the node processed.
2.114 + void process(const Node& node) {}
2.115 + };
2.116 +#else
2.117 + template <typename _Graph>
2.118 + struct BfsVisitor {
2.119 + typedef _Graph Graph;
2.120 + typedef typename Graph::Edge Edge;
2.121 + typedef typename Graph::Node Node;
2.122 + void discover(const Edge&) {}
2.123 + void reach(const Node&) {}
2.124 + void examine(const Edge&) {}
2.125 + void start(const Node&) {}
2.126 + void process(const Node&) {}
2.127 +
2.128 + template <typename _Visitor>
2.129 + struct Constraints {
2.130 + void constraints() {
2.131 + Edge edge;
2.132 + Node node;
2.133 + visitor.discover(edge);
2.134 + visitor.reach(node);
2.135 + visitor.examine(edge);
2.136 + visitor.start(node);
2.137 + visitor.process(node);
2.138 + }
2.139 + _Visitor& visitor;
2.140 + };
2.141 + };
2.142 +#endif
2.143 +
2.144 + /// \brief Default traits class of BfsVisit class.
2.145 + ///
2.146 + /// Default traits class of BfsVisit class.
2.147 + /// \param _Graph Graph type.
2.148 + template<class _Graph>
2.149 + struct BfsVisitDefaultTraits {
2.150 +
2.151 + /// \brief The graph type the algorithm runs on.
2.152 + typedef _Graph Graph;
2.153 +
2.154 + /// \brief The type of the map that indicates which nodes are reached.
2.155 + ///
2.156 + /// The type of the map that indicates which nodes are reached.
2.157 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.158 + /// \todo named parameter to set this type, function to read and write.
2.159 + typedef typename Graph::template NodeMap<bool> ReachedMap;
2.160 +
2.161 + /// \brief Instantiates a ReachedMap.
2.162 + ///
2.163 + /// This function instantiates a \ref ReachedMap.
2.164 + /// \param graph is the graph, to which
2.165 + /// we would like to define the \ref ReachedMap.
2.166 + static ReachedMap *createReachedMap(const Graph &graph) {
2.167 + return new ReachedMap(graph);
2.168 + }
2.169 +
2.170 + };
2.171 +
2.172 + /// %BFS Visit algorithm class.
2.173 +
2.174 + /// \ingroup flowalgs
2.175 + /// This class provides an efficient implementation of the %BFS algorithm
2.176 + /// with visitor interface.
2.177 + ///
2.178 + /// The %BfsVisit class provides an alternative interface to the Bfs
2.179 + /// class. It works with callback mechanism, the BfsVisit object calls
2.180 + /// on every bfs event the \c Visitor class member functions.
2.181 + ///
2.182 + /// \param _Graph The graph type the algorithm runs on. The default value is
2.183 + /// \ref ListGraph. The value of _Graph is not used directly by Bfs, it
2.184 + /// is only passed to \ref BfsDefaultTraits.
2.185 + /// \param _Visitor The Visitor object for the algorithm. The
2.186 + /// \ref BfsVisitor "BfsVisitor<_Graph>" is an empty Visitor which
2.187 + /// does not observe the Bfs events. If you want to observe the bfs
2.188 + /// events you should implement your own Visitor class.
2.189 + /// \param _Traits Traits class to set various data types used by the
2.190 + /// algorithm. The default traits class is
2.191 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Graph>".
2.192 + /// See \ref BfsVisitDefaultTraits for the documentation of
2.193 + /// a Bfs visit traits class.
2.194 + ///
2.195 + /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
2.196 +#ifdef DOXYGEN
2.197 + template <typename _Graph, typename _Visitor, typename _Traits>
2.198 +#else
2.199 + template <typename _Graph = ListGraph,
2.200 + typename _Visitor = BfsVisitor<_Graph>,
2.201 + typename _Traits = BfsDefaultTraits<_Graph> >
2.202 +#endif
2.203 + class BfsVisit {
2.204 + public:
2.205 +
2.206 + /// \brief \ref Exception for uninitialized parameters.
2.207 + ///
2.208 + /// This error represents problems in the initialization
2.209 + /// of the parameters of the algorithms.
2.210 + class UninitializedParameter : public lemon::UninitializedParameter {
2.211 + public:
2.212 + virtual const char* what() const throw()
2.213 + {
2.214 + return "lemon::BfsVisit::UninitializedParameter";
2.215 + }
2.216 + };
2.217 +
2.218 + typedef _Traits Traits;
2.219 +
2.220 + typedef typename Traits::Graph Graph;
2.221 +
2.222 + typedef _Visitor Visitor;
2.223 +
2.224 + ///The type of the map indicating which nodes are reached.
2.225 + typedef typename Traits::ReachedMap ReachedMap;
2.226 +
2.227 + private:
2.228 +
2.229 + typedef typename Graph::Node Node;
2.230 + typedef typename Graph::NodeIt NodeIt;
2.231 + typedef typename Graph::Edge Edge;
2.232 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.233 +
2.234 + /// Pointer to the underlying graph.
2.235 + const Graph *_graph;
2.236 + /// Pointer to the visitor object.
2.237 + Visitor *_visitor;
2.238 + ///Pointer to the map of reached status of the nodes.
2.239 + ReachedMap *_reached;
2.240 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
2.241 + bool local_reached;
2.242 +
2.243 + std::vector<typename Graph::Node> _list;
2.244 + int _list_front, _list_back;
2.245 +
2.246 + /// \brief Creates the maps if necessary.
2.247 + ///
2.248 + /// Creates the maps if necessary.
2.249 + void create_maps() {
2.250 + if(!_reached) {
2.251 + local_reached = true;
2.252 + _reached = Traits::createReachedMap(*_graph);
2.253 + }
2.254 + }
2.255 +
2.256 + protected:
2.257 +
2.258 + BfsVisit() {}
2.259 +
2.260 + public:
2.261 +
2.262 + typedef BfsVisit Create;
2.263 +
2.264 + /// \name Named template parameters
2.265 +
2.266 + ///@{
2.267 + template <class T>
2.268 + struct DefReachedMapTraits : public Traits {
2.269 + typedef T ReachedMap;
2.270 + static ReachedMap *createReachedMap(const Graph &graph) {
2.271 + throw UninitializedParameter();
2.272 + }
2.273 + };
2.274 + /// \brief \ref named-templ-param "Named parameter" for setting
2.275 + /// ReachedMap type
2.276 + ///
2.277 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type
2.278 + template <class T>
2.279 + struct DefReachedMap : public BfsVisit< Graph, Visitor,
2.280 + DefReachedMapTraits<T> > {
2.281 + typedef BfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
2.282 + };
2.283 + ///@}
2.284 +
2.285 + public:
2.286 +
2.287 + /// \brief Constructor.
2.288 + ///
2.289 + /// Constructor.
2.290 + ///
2.291 + /// \param graph the graph the algorithm will run on.
2.292 + /// \param visitor The visitor of the algorithm.
2.293 + ///
2.294 + BfsVisit(const Graph& graph, Visitor& visitor)
2.295 + : _graph(&graph), _visitor(&visitor),
2.296 + _reached(0), local_reached(false) {}
2.297 +
2.298 + /// \brief Destructor.
2.299 + ///
2.300 + /// Destructor.
2.301 + ~BfsVisit() {
2.302 + if(local_reached) delete _reached;
2.303 + }
2.304 +
2.305 + /// \brief Sets the map indicating if a node is reached.
2.306 + ///
2.307 + /// Sets the map indicating if a node is reached.
2.308 + /// If you don't use this function before calling \ref run(),
2.309 + /// it will allocate one. The destuctor deallocates this
2.310 + /// automatically allocated map, of course.
2.311 + /// \return <tt> (*this) </tt>
2.312 + BfsVisit &reachedMap(ReachedMap &m) {
2.313 + if(local_reached) {
2.314 + delete _reached;
2.315 + local_reached = false;
2.316 + }
2.317 + _reached = &m;
2.318 + return *this;
2.319 + }
2.320 +
2.321 + public:
2.322 + /// \name Execution control
2.323 + /// The simplest way to execute the algorithm is to use
2.324 + /// one of the member functions called \c run(...).
2.325 + /// \n
2.326 + /// If you need more control on the execution,
2.327 + /// first you must call \ref init(), then you can adda source node
2.328 + /// with \ref addSource().
2.329 + /// Finally \ref start() will perform the actual path
2.330 + /// computation.
2.331 +
2.332 + /// @{
2.333 + /// \brief Initializes the internal data structures.
2.334 + ///
2.335 + /// Initializes the internal data structures.
2.336 + ///
2.337 + void init() {
2.338 + create_maps();
2.339 + _list.resize(countNodes(*_graph));
2.340 + _list_front = _list_back = -1;
2.341 + for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
2.342 + _reached->set(u, false);
2.343 + }
2.344 + }
2.345 +
2.346 + /// \brief Adds a new source node.
2.347 + ///
2.348 + /// Adds a new source node to the set of nodes to be processed.
2.349 + void addSource(Node s) {
2.350 + if(!(*_reached)[s]) {
2.351 + _reached->set(s,true);
2.352 + _visitor->start(s);
2.353 + _visitor->reach(s);
2.354 + _list[++_list_back] = s;
2.355 + }
2.356 + }
2.357 +
2.358 + /// \brief Processes the next node.
2.359 + ///
2.360 + /// Processes the next node.
2.361 + ///
2.362 + /// \return The processed node.
2.363 + ///
2.364 + /// \pre The queue must not be empty!
2.365 + Node processNextNode() {
2.366 + Node n = _list[++_list_front];
2.367 + _visitor->process(n);
2.368 + Edge e;
2.369 + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
2.370 + Node m = _graph->target(e);
2.371 + if (!(*_reached)[m]) {
2.372 + _visitor->discover(e);
2.373 + _visitor->reach(m);
2.374 + _reached->set(m, true);
2.375 + _list[++_list_back] = m;
2.376 + } else {
2.377 + _visitor->examine(e);
2.378 + }
2.379 + }
2.380 + return n;
2.381 + }
2.382 +
2.383 + /// \brief Processes the next node.
2.384 + ///
2.385 + /// Processes the next node. And checks that the given target node
2.386 + /// is reached. If the target node is reachable from the processed
2.387 + /// node then the reached parameter will be set true. The reached
2.388 + /// parameter should be initially false.
2.389 + ///
2.390 + /// \param target The target node.
2.391 + /// \retval reached Indicates that the target node is reached.
2.392 + /// \return The processed node.
2.393 + ///
2.394 + /// \warning The queue must not be empty!
2.395 + Node processNextNode(Node target, bool& reached) {
2.396 + Node n = _list[++_list_front];
2.397 + _visitor->process(n);
2.398 + Edge e;
2.399 + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
2.400 + Node m = _graph->target(e);
2.401 + if (!(*_reached)[m]) {
2.402 + _visitor->discover(e);
2.403 + _visitor->reach(m);
2.404 + _reached->set(m, true);
2.405 + _list[++_list_back] = m;
2.406 + reached = reached || (target == m);
2.407 + } else {
2.408 + _visitor->examine(e);
2.409 + }
2.410 + }
2.411 + return n;
2.412 + }
2.413 +
2.414 + /// \brief Processes the next node.
2.415 + ///
2.416 + /// Processes the next node. And checks that at least one of
2.417 + /// reached node has true value in the \c nm nodemap. If one node
2.418 + /// with true value is reachable from the processed node then the
2.419 + /// reached parameter will be set true. The reached parameter
2.420 + /// should be initially false.
2.421 + ///
2.422 + /// \param target The nodemaps of possible targets.
2.423 + /// \retval reached Indicates that one of the target nodes is reached.
2.424 + /// \return The processed node.
2.425 + ///
2.426 + /// \warning The queue must not be empty!
2.427 + template <typename NM>
2.428 + Node processNextNode(const NM& nm, bool& reached) {
2.429 + Node n = _list[++_list_front];
2.430 + _visitor->process(n);
2.431 + Edge e;
2.432 + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
2.433 + Node m = _graph->target(e);
2.434 + if (!(*_reached)[m]) {
2.435 + _visitor->discover(e);
2.436 + _visitor->reach(m);
2.437 + _reached->set(m, true);
2.438 + _list[++_list_back] = m;
2.439 + reached = reached || nm[m];
2.440 + } else {
2.441 + _visitor->examine(e);
2.442 + }
2.443 + }
2.444 + return n;
2.445 + }
2.446 +
2.447 + /// \brief Next node to be processed.
2.448 + ///
2.449 + /// Next node to be processed.
2.450 + ///
2.451 + /// \return The next node to be processed or INVALID if the stack is
2.452 + /// empty.
2.453 + Node nextNode() {
2.454 + return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
2.455 + }
2.456 +
2.457 + /// \brief Returns \c false if there are nodes
2.458 + /// to be processed in the queue
2.459 + ///
2.460 + /// Returns \c false if there are nodes
2.461 + /// to be processed in the queue
2.462 + bool emptyQueue() { return _list_front == _list_back; }
2.463 +
2.464 + /// \brief Returns the number of the nodes to be processed.
2.465 + ///
2.466 + /// Returns the number of the nodes to be processed in the queue.
2.467 + int queueSize() { return _list_back - _list_front; }
2.468 +
2.469 + /// \brief Executes the algorithm.
2.470 + ///
2.471 + /// Executes the algorithm.
2.472 + ///
2.473 + /// \pre init() must be called and at least one node should be added
2.474 + /// with addSource() before using this function.
2.475 + void start() {
2.476 + while ( !emptyQueue() ) processNextNode();
2.477 + }
2.478 +
2.479 + /// \brief Executes the algorithm until \c dest will be next processed.
2.480 + ///
2.481 + /// Executes the algorithm until \c dest will be next processed.
2.482 + ///
2.483 + /// \pre init() must be called and at least one node should be added
2.484 + /// with addSource() before using this function.
2.485 + void start(Node dest) {
2.486 + bool reached = false;
2.487 + while (!emptyQueue() && !reached) {
2.488 + processNextNode(dest, reached);
2.489 + }
2.490 + }
2.491 +
2.492 + /// \brief Executes the algorithm until a condition is met.
2.493 + ///
2.494 + /// Executes the algorithm until a condition is met.
2.495 + ///
2.496 + /// \pre init() must be called and at least one node should be added
2.497 + /// with addSource() before using this function.
2.498 + ///
2.499 + ///\param nm must be a bool (or convertible) node map. The
2.500 + ///algorithm will stop when it reaches a node \c v with
2.501 + ///<tt>nm[v]</tt> true.
2.502 + template <typename NM>
2.503 + void start(const NM &nm) {
2.504 + bool reached = false;
2.505 + while (!emptyQueue() && !reached) {
2.506 + processNextNode(nm, reached);
2.507 + }
2.508 + }
2.509 +
2.510 + /// \brief Runs %BFSVisit algorithm from node \c s.
2.511 + ///
2.512 + /// This method runs the %BFS algorithm from a root node \c s.
2.513 + /// \note b.run(s) is just a shortcut of the following code.
2.514 + ///\code
2.515 + /// b.init();
2.516 + /// b.addSource(s);
2.517 + /// b.start();
2.518 + ///\endcode
2.519 + void run(Node s) {
2.520 + init();
2.521 + addSource(s);
2.522 + start();
2.523 + }
2.524 +
2.525 + /// \brief Runs %BFSVisit algorithm to visit all nodes in the graph.
2.526 + ///
2.527 + /// This method runs the %BFS algorithm in order to
2.528 + /// compute the %BFS path to each node. The algorithm computes
2.529 + /// - The %BFS tree.
2.530 + /// - The distance of each node from the root in the %BFS tree.
2.531 + ///
2.532 + ///\note b.run() is just a shortcut of the following code.
2.533 + ///\code
2.534 + /// b.init();
2.535 + /// for (NodeIt it(graph); it != INVALID; ++it) {
2.536 + /// if (!b.reached(it)) {
2.537 + /// b.addSource(it);
2.538 + /// b.start();
2.539 + /// }
2.540 + /// }
2.541 + ///\endcode
2.542 + void run() {
2.543 + init();
2.544 + for (NodeIt it(*_graph); it != INVALID; ++it) {
2.545 + if (!reached(it)) {
2.546 + addSource(it);
2.547 + start();
2.548 + }
2.549 + }
2.550 + }
2.551 + ///@}
2.552 +
2.553 + /// \name Query Functions
2.554 + /// The result of the %BFS algorithm can be obtained using these
2.555 + /// functions.\n
2.556 + /// Before the use of these functions,
2.557 + /// either run() or start() must be called.
2.558 + ///@{
2.559 +
2.560 + /// \brief Checks if a node is reachable from the root.
2.561 + ///
2.562 + /// Returns \c true if \c v is reachable from the root(s).
2.563 + /// \warning The source nodes are inditated as unreachable.
2.564 + /// \pre Either \ref run() or \ref start()
2.565 + /// must be called before using this function.
2.566 + ///
2.567 + bool reached(Node v) { return (*_reached)[v]; }
2.568 + ///@}
2.569 + };
2.570 +
2.571 } //END OF NAMESPACE LEMON
2.572
2.573 #endif
3.1 --- a/lemon/topology.h Tue Nov 21 17:28:08 2006 +0000
3.2 +++ b/lemon/topology.h Tue Nov 21 18:22:08 2006 +0000
3.3 @@ -1389,6 +1389,64 @@
3.4 return true;
3.5 }
3.6
3.7 + namespace _topology_bits {
3.8 +
3.9 + template <typename Graph>
3.10 + class BipartiteVisitor : public BfsVisitor<Graph> {
3.11 + public:
3.12 + typedef typename Graph::Edge Edge;
3.13 + typedef typename Graph::Node Node;
3.14 +
3.15 + BipartiteVisitor(const Graph& graph, bool& bipartite)
3.16 + : _graph(graph), _part(graph), _bipartite(bipartite) {}
3.17 +
3.18 + void start(const Node& node) {
3.19 + _part[node] = true;
3.20 + }
3.21 + void discover(const Edge& edge) {
3.22 + _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
3.23 + }
3.24 + void examine(const Edge& edge) {
3.25 + _bipartite = _bipartite &&
3.26 + _part[_graph.target(edge)] != _part[_graph.source(edge)];
3.27 + }
3.28 +
3.29 + private:
3.30 +
3.31 + const Graph& _graph;
3.32 + typename Graph::template NodeMap<bool> _part;
3.33 + bool& _bipartite;
3.34 + };
3.35 +
3.36 + template <typename Graph, typename PartMap>
3.37 + class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
3.38 + public:
3.39 + typedef typename Graph::Edge Edge;
3.40 + typedef typename Graph::Node Node;
3.41 +
3.42 + BipartitePartitionsVisitor(const Graph& graph,
3.43 + PartMap& part, bool& bipartite)
3.44 + : _graph(graph), _part(part), _bipartite(bipartite) {}
3.45 +
3.46 + void start(const Node& node) {
3.47 + _part.set(node, true);
3.48 + }
3.49 + void discover(const Edge& edge) {
3.50 + _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
3.51 + }
3.52 + void examine(const Edge& edge) {
3.53 + _bipartite = _bipartite &&
3.54 + _part[_graph.target(edge)] != _part[_graph.source(edge)];
3.55 + }
3.56 +
3.57 + private:
3.58 +
3.59 + const Graph& _graph;
3.60 + PartMap& _part;
3.61 + bool& _bipartite;
3.62 + };
3.63 + }
3.64 +
3.65 /// \ingroup topology
3.66 ///
3.67 /// \brief Check if the given undirected graph is bipartite or not
3.68 @@ -1402,21 +1460,29 @@
3.69 /// \author Balazs Attila Mihaly
3.70 template<typename UGraph>
3.71 inline bool bipartite(const UGraph &graph){
3.72 + using namespace _topology_bits;
3.73 +
3.74 checkConcept<concepts::UGraph, UGraph>();
3.75
3.76 typedef typename UGraph::NodeIt NodeIt;
3.77 typedef typename UGraph::EdgeIt EdgeIt;
3.78
3.79 - Bfs<UGraph> bfs(graph);
3.80 + bool bipartite = true;
3.81 +
3.82 + BipartiteVisitor<UGraph>
3.83 + visitor(graph, bipartite);
3.84 + BfsVisit<UGraph, BipartiteVisitor<UGraph> >
3.85 + bfs(graph, visitor);
3.86 bfs.init();
3.87 - for(NodeIt i(graph);i!=INVALID;++i){
3.88 - if(!bfs.reached(i)){
3.89 - bfs.run(i);
3.90 + for(NodeIt it(graph); it != INVALID; ++it) {
3.91 + if(!bfs.reached(it)){
3.92 + bfs.addSource(it);
3.93 + while (!bfs.emptyQueue()) {
3.94 + bfs.processNextNode();
3.95 + if (!bipartite) return false;
3.96 + }
3.97 }
3.98 }
3.99 - for(EdgeIt i(graph);i!=INVALID;++i){
3.100 - if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
3.101 - }
3.102 return true;
3.103 }
3.104
3.105 @@ -1439,25 +1505,80 @@
3.106 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
3.107 template<typename UGraph, typename NodeMap>
3.108 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
3.109 + using namespace _topology_bits;
3.110 +
3.111 checkConcept<concepts::UGraph, UGraph>();
3.112
3.113 typedef typename UGraph::Node Node;
3.114 typedef typename UGraph::NodeIt NodeIt;
3.115 typedef typename UGraph::EdgeIt EdgeIt;
3.116 -
3.117 - Bfs<UGraph> bfs(graph);
3.118 +
3.119 + bool bipartite = true;
3.120 +
3.121 + BipartitePartitionsVisitor<UGraph, NodeMap>
3.122 + visitor(graph, partMap, bipartite);
3.123 + BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> >
3.124 + bfs(graph, visitor);
3.125 bfs.init();
3.126 - for(NodeIt i(graph);i!=INVALID;++i){
3.127 - if(!bfs.reached(i)){
3.128 - bfs.addSource(i);
3.129 - for(Node j=bfs.processNextNode();!bfs.emptyQueue();
3.130 - j=bfs.processNextNode()){
3.131 - partMap.set(j,bfs.dist(j)%2==0);
3.132 - }
3.133 + for(NodeIt it(graph); it != INVALID; ++it) {
3.134 + if(!bfs.reached(it)){
3.135 + bfs.addSource(it);
3.136 + while (!bfs.emptyQueue()) {
3.137 + bfs.processNextNode();
3.138 + if (!bipartite) return false;
3.139 + }
3.140 }
3.141 }
3.142 - for(EdgeIt i(graph);i!=INVALID;++i){
3.143 - if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
3.144 + return true;
3.145 + }
3.146 +
3.147 + /// \brief Returns true when there is not loop edge in the graph.
3.148 + ///
3.149 + /// Returns true when there is not loop edge in the graph.
3.150 + template <typename Graph>
3.151 + bool loopFree(const Graph& graph) {
3.152 + for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
3.153 + if (graph.source(it) == graph.target(it)) return false;
3.154 + }
3.155 + return true;
3.156 + }
3.157 +
3.158 + /// \brief Returns true when there is not parallel edges in the graph.
3.159 + ///
3.160 + /// Returns true when there is not parallel edges in the graph.
3.161 + template <typename Graph>
3.162 + bool parallelFree(const Graph& graph) {
3.163 + typename Graph::template NodeMap<bool> reached(graph, false);
3.164 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
3.165 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
3.166 + if (reached[graph.target(e)]) return false;
3.167 + reached.set(graph.target(e), true);
3.168 + }
3.169 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
3.170 + reached.set(graph.target(e), false);
3.171 + }
3.172 + }
3.173 + return true;
3.174 + }
3.175 +
3.176 + /// \brief Returns true when there is not loop edge and parallel
3.177 + /// edges in the graph.
3.178 + ///
3.179 + /// Returns true when there is not loop edge and parallel edges in
3.180 + /// the graph.
3.181 + template <typename Graph>
3.182 + bool simpleGraph(const Graph& graph) {
3.183 + typename Graph::template NodeMap<bool> reached(graph, false);
3.184 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
3.185 + reached.set(n, true);
3.186 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
3.187 + if (reached[graph.target(e)]) return false;
3.188 + reached.set(graph.target(e), true);
3.189 + }
3.190 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
3.191 + reached.set(graph.target(e), false);
3.192 + }
3.193 + reached.set(n, false);
3.194 }
3.195 return true;
3.196 }