Changeset 2306:42cce226b87b in lemon-0.x for lemon

Timestamp:

11/21/06 19:22:08 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3081

Message:

BfsVisitor?
Bipartite partitions based on visitors

topology_demo.cc => scaleToA4 works without extra parameters

Location:

lemon

Files:

• bfs.h (modified) (7 diffs)
• topology.h (modified) (5 diffs)

lemon/bfs.h

@@ -588 +588 @@
     }
     
-    ///Executes the algorithm until \c dest is reached.
-
-    ///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 the next node to processed.
     ///
     ///\pre init() must be called and at least one node should be added
@@ -615 +615 @@
     ///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 <tt>nm[v]==true</tt>.
+    ///\param nm must be a bool (or convertible) node map. The
+    ///algorithm will stop when for the next processable node \c v is
+    ///<tt>nm[v]</tt> true.
     ///\todo query the reached target
     template<class NM>
@@ -634 +635 @@
     ///- 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) {
@@ -652 +653 @@
     ///\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) {
@@ -672 +673 @@
     ///functions.\n
     ///Before the use of these functions,
-    ///either run() or start() must be called.
+    ///either run() or start() must be calleb.
     
     ///@{
@@ -944 +945 @@
     typedef typename TR::DistMap DistMap;
 
-public:
+  public:
     /// Constructor.
     BfsWizard() : TR() {}
@@ -1105 +1106 @@
   }
 
+#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 <typename _Graph>
+  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 <typename _Graph>
+  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 <typename _Visitor>
+    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<class _Graph>
+  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<bool> 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 <typename _Graph, typename _Visitor, typename _Traits>
+#else
+  template <typename _Graph = ListGraph,
+            typename _Visitor = BfsVisitor<_Graph>,
+            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<typename Graph::Node> _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 <class T>
+    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 <class T>
+    struct DefReachedMap : public BfsVisit< Graph, Visitor,
+                                            DefReachedMapTraits<T> > {
+      typedef BfsVisit< Graph, Visitor, DefReachedMapTraits<T> > 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 <tt> (*this) </tt>
+    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 <typename NM>
+    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
+    ///<tt>nm[v]</tt> true.
+    template <typename NM>
+    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
 

lemon/topology.h

@@ -1390 +1390 @@
   }
 
+  namespace _topology_bits {
+
+    template <typename Graph>
+    class BipartiteVisitor : public BfsVisitor<Graph> {
+    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<bool> _part;
+      bool& _bipartite;
+    };
+
+    template <typename Graph, typename PartMap>
+    class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
+    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
   ///
@@ -1403 +1461 @@
   template<typename UGraph>
   inline bool bipartite(const UGraph &graph){
+    using namespace _topology_bits;
+
     checkConcept<concepts::UGraph, UGraph>();
     
@@ -1408 +1468 @@
     typedef typename UGraph::EdgeIt EdgeIt;
     
-    Bfs<UGraph> bfs(graph);
+    bool bipartite = true;
+
+    BipartiteVisitor<UGraph> 
+      visitor(graph, bipartite);
+    BfsVisit<UGraph, BipartiteVisitor<UGraph> > 
+      bfs(graph, visitor);
     bfs.init();
-    for(NodeIt i(graph);i!=INVALID;++i){
-      if(!bfs.reached(i)){
-        bfs.run(i);
-      }
-    }
-    for(EdgeIt i(graph);i!=INVALID;++i){
-      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
+    for(NodeIt it(graph); it != INVALID; ++it) {
+      if(!bfs.reached(it)){
+        bfs.addSource(it);
+        while (!bfs.emptyQueue()) {
+          bfs.processNextNode();
+          if (!bipartite) return false;
+        }
+      }
     }
     return true;
@@ -1440 +1506 @@
   template<typename UGraph, typename NodeMap>
   inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
+    using namespace _topology_bits;
+
     checkConcept<concepts::UGraph, UGraph>();
     
@@ -1445 +1513 @@
     typedef typename UGraph::NodeIt NodeIt;
     typedef typename UGraph::EdgeIt EdgeIt;
-  
-    Bfs<UGraph> bfs(graph);
+
+    bool bipartite = true;
+
+    BipartitePartitionsVisitor<UGraph, NodeMap> 
+      visitor(graph, partMap, bipartite);
+    BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> > 
+      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(EdgeIt i(graph);i!=INVALID;++i){
-      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
+    for(NodeIt it(graph); it != INVALID; ++it) {
+      if(!bfs.reached(it)){
+        bfs.addSource(it);
+        while (!bfs.emptyQueue()) {
+          bfs.processNextNode();
+          if (!bipartite) 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 <typename Graph>
+  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 <typename Graph>
+  bool parallelFree(const Graph& graph) {
+    typename Graph::template NodeMap<bool> 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 <typename Graph>
+  bool simpleGraph(const Graph& graph) {
+    typename Graph::template NodeMap<bool> 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;