COIN-OR::LEMON - Graph Library

Changeset 1749:c13f6b4aa40e in lemon-0.x


Ignore:
Timestamp:
11/02/05 16:22:28 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2278
Message:

Visitor interface for the dfs algorithm.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dfs.h

    r1710 r1749  
    2828#include <lemon/maps.h>
    2929
     30#include <lemon/concept_check.h>
     31
    3032namespace lemon {
    31 
    3233
    3334 
     
    124125  ///
    125126  ///\author Jacint Szabo and Alpar Juttner
    126   ///\todo A compare object would be nice.
    127 
    128127#ifdef DOXYGEN
    129128  template <typename GR,
     
    276275    ///
    277276    template <class T>
    278     struct DefReachedMap {
     277    struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
    279278      typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
    280279    };
     
    327326      G(&_G),
    328327      _pred(NULL), local_pred(false),
    329 //       _predNode(NULL), local_predNode(false),
    330328      _dist(NULL), local_dist(false),
    331329      _reached(NULL), local_reached(false),
     
    337335    {
    338336      if(local_pred) delete _pred;
    339 //       if(local_predNode) delete _predNode;
    340337      if(local_dist) delete _dist;
    341338      if(local_reached) delete _reached;
     
    359356      return *this;
    360357    }
    361 
    362 //     ///Sets the map storing the predecessor nodes.
    363 
    364 //     ///Sets the map storing the predecessor nodes.
    365 //     ///If you don't use this function before calling \ref run(),
    366 //     ///it will allocate one. The destuctor deallocates this
    367 //     ///automatically allocated map, of course.
    368 //     ///\return <tt> (*this) </tt>
    369 //     Dfs &predNodeMap(PredNodeMap &m)
    370 //     {
    371 //       if(local_predNode) {
    372 //      delete _predNode;
    373 //      local_predNode=false;
    374 //       }
    375 //       _predNode = &m;
    376 //       return *this;
    377 //     }
    378358
    379359    ///Sets the map storing the distances calculated by the algorithm.
     
    469449          _reached->set(s,true);
    470450          _pred->set(s,INVALID);
    471           // _predNode->set(u,INVALID);
    472451          OutEdgeIt e(*G,s);
    473452          if(e!=INVALID) {
     
    496475        _pred->set(m,e);
    497476        _reached->set(m,true);
    498         //        _pred_node->set(m,G->source(e));
    499477        ++_stack_head;
    500478        _stack[_stack_head] = OutEdgeIt(*G, m);
     
    505483        ++_stack[_stack_head];
    506484      }
    507       //'m' is now the (original) source of the _stack[_stack_head]
    508485      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
    509486        _processed->set(m,true);
     
    591568    ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
    592569    ///
    593     ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
     570    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
    594571    ///not a node map.
    595     template<class NM>
    596       void start(const NM &nm)
    597       {
    598         while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
    599       }
    600    
     572    template<class EM>
     573    void start(const EM &em)
     574    {
     575      while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
     576    }
     577
    601578    ///Runs %DFS algorithm from node \c s.
    602579   
     
    726703    const PredMap &predMap() const { return *_pred;}
    727704 
    728 //     ///Returns a reference to the map of nodes of %DFS paths.
    729 
    730 //     ///Returns a reference to the NodeMap of the last but one nodes of the
    731 //     ///%DFS tree.
    732 //     ///\pre \ref run() must be called before using this function.
    733 //     const PredNodeMap &predNodeMap() const { return *_predNode;}
    734 
    735705    ///Checks if a node is reachable from the root.
    736706
     
    775745      return new PredMap();
    776746    }
    777 //     ///\brief The type of the map that stores the last but one
    778 //     ///nodes of the %DFS paths.
    779 //     ///
    780 //     ///The type of the map that stores the last but one
    781 //     ///nodes of the %DFS paths.
    782 //     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    783 //     ///
    784 //     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
    785 //     ///Instantiates a PredNodeMap.
    786    
    787 //     ///This function instantiates a \ref PredNodeMap.
    788 //     ///\param G is the graph, to which
    789 //     ///we would like to define the \ref PredNodeMap
    790 //     static PredNodeMap *createPredNodeMap(const GR &G)
    791 //     {
    792 //       return new PredNodeMap();
    793 //     }
    794747
    795748    ///The type of the map that indicates which nodes are processed.
     
    872825    ///Pointer to the map of predecessors edges.
    873826    void *_pred;
    874 //     ///Pointer to the map of predecessors nodes.
    875 //     void *_predNode;
    876827    ///Pointer to the map of distances.
    877828    void *_dist;
     
    885836    /// all of the attributes to default values (0, INVALID).
    886837    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    887 //                         _predNode(0),
    888838                           _dist(0), _source(INVALID) {}
    889839
     
    897847    DfsWizardBase(const GR &g, Node s=INVALID) :
    898848      _g((void *)&g), _reached(0), _processed(0), _pred(0),
    899 //       _predNode(0),
    900849      _dist(0), _source(s) {}
    901850
     
    946895    ///edges of the %DFS paths.
    947896    typedef typename TR::PredMap PredMap;
    948 //     ///\brief The type of the map that stores the last but one
    949 //     ///nodes of the %DFS paths.
    950 //     typedef typename TR::PredNodeMap PredNodeMap;
    951897    ///The type of the map that stores the distances of the nodes.
    952898    typedef typename TR::DistMap DistMap;
     
    979925      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
    980926      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
    981 //       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
    982927      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
    983928      alg.run(Base::_source);
     
    10561001    }
    10571002   
    1058 
    1059 //     template<class T>
    1060 //     struct DefPredNodeMapBase : public Base {
    1061 //       typedef T PredNodeMap;
    1062 //       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
    1063 //       DefPredNodeMapBase(const TR &b) : TR(b) {}
    1064 //     };
    1065    
    1066 //     ///\brief \ref named-templ-param "Named parameter"
    1067 //     ///function for setting PredNodeMap type
    1068 //     ///
    1069 //     /// \ref named-templ-param "Named parameter"
    1070 //     ///function for setting PredNodeMap type
    1071 //     ///
    1072 //     template<class T>
    1073 //     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
    1074 //     {
    1075 //       Base::_predNode=(void *)&t;
    1076 //       return DfsWizard<DefPredNodeMapBase<T> >(*this);
    1077 //     }
    1078    
    10791003    template<class T>
    10801004    struct DefDistMapBase : public Base {
     
    11331057  }
    11341058
     1059  /// \brief Visitor class for dfs.
     1060  /// 
     1061  /// It gives a simple interface for a functional interface for dfs
     1062  /// traversal. The traversal on a linear data structure.
     1063  template <typename _Graph>
     1064  struct DfsVisitor {
     1065    typedef _Graph Graph;
     1066    typedef typename Graph::Edge Edge;
     1067    typedef typename Graph::Node Node;
     1068    /// \brief Called when the edge reach a node.
     1069    ///
     1070    /// It is called when the dfs find an edge which target is not
     1071    /// reached yet.
     1072    void discover(const Edge& edge) {}
     1073    /// \brief Called when the node reached first time.
     1074    ///
     1075    /// It is Called when the node reached first time.
     1076    void reach(const Node& node) {}
     1077    /// \brief Called when we step back on an edge.
     1078    ///
     1079    /// It is called when the dfs should step back on the edge.
     1080    void backtrack(const Edge& edge) {}
     1081    /// \brief Called when we step back from the node.
     1082    ///
     1083    /// It is called when we step back from the node.
     1084    void leave(const Node& node) {}
     1085    /// \brief Called when the edge examined but target of the edge
     1086    /// already discovered.
     1087    ///
     1088    /// It called when the edge examined but the target of the edge
     1089    /// already discovered.
     1090    void examine(const Edge& edge) {}
     1091    /// \brief Called for the source node of the dfs.
     1092    ///
     1093    /// It is called for the source node of the dfs.
     1094    void start(const Node&) {}
     1095    /// \brief Called when we leave the source node of the dfs.
     1096    ///
     1097    /// It is called when we leave the source node of the dfs.
     1098    void stop(const Node&) {}
     1099
     1100    template <typename _Visitor>
     1101    struct Constraints {
     1102      void constraints() {
     1103        Edge edge;
     1104        Node node;
     1105        visitor.discover(edge);
     1106        visitor.reach(node);
     1107        visitor.backtrack(edge);
     1108        visitor.leave(node);
     1109        visitor.examine(edge);
     1110        visitor.start(node);
     1111        visitor.stop(edge);
     1112      }
     1113      _Visitor& visitor;
     1114    };
     1115  };
     1116
     1117  /// \brief Default traits class of DfsVisit class.
     1118  ///
     1119  /// Default traits class of DfsVisit class.
     1120  /// \param _Graph Graph type.
     1121  template<class _Graph>
     1122  struct DfsVisitDefaultTraits {
     1123
     1124    /// \brief The graph type the algorithm runs on.
     1125    typedef _Graph Graph;
     1126
     1127    /// \brief The type of the map that indicates which nodes are reached.
     1128    ///
     1129    /// The type of the map that indicates which nodes are reached.
     1130    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
     1131    /// \todo named parameter to set this type, function to read and write.
     1132    typedef typename Graph::template NodeMap<bool> ReachedMap;
     1133
     1134    /// \brief Instantiates a ReachedMap.
     1135    ///
     1136    /// This function instantiates a \ref ReachedMap.
     1137    /// \param G is the graph, to which
     1138    /// we would like to define the \ref ReachedMap.
     1139    static ReachedMap *createReachedMap(const Graph &graph) {
     1140      return new ReachedMap(graph);
     1141    }
     1142
     1143  };
     1144 
     1145  /// %DFS Visit algorithm class.
     1146 
     1147  /// \ingroup flowalgs
     1148  /// This class provides an efficient implementation of the %DFS algorithm
     1149  /// with visitor interface.
     1150  ///
     1151  /// The %DfsVisit class provides an alternative interface to the Dfs
     1152  /// class. It works with callback mechanism, the DfsVisit object calls
     1153  /// on every dfs event the \c Visitor class member functions.
     1154  ///
     1155  /// \param _Graph The graph type the algorithm runs on. The default value is
     1156  /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
     1157  /// is only passed to \ref DfsDefaultTraits.
     1158  /// \param _Visitor The Visitor object for the algorithm. The
     1159  /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
     1160  /// does not observe the Dfs events. If you want to observe the dfs
     1161  /// events you should implement your own Visitor class.
     1162  /// \param _Traits Traits class to set various data types used by the
     1163  /// algorithm. The default traits class is
     1164  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
     1165  /// See \ref DfsVisitDefaultTraits for the documentation of
     1166  /// a Dfs visit traits class.
     1167  ///
     1168  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
     1169#ifdef DOXYGEN
     1170  template <typename _Graph, typename _Visitor, typename _Traits>
     1171#else
     1172  template <typename _Graph = ListGraph,
     1173            typename _Visitor = DfsVisitor<_Graph>,
     1174            typename _Traits = DfsDefaultTraits<_Graph> >
     1175#endif
     1176  class DfsVisit {
     1177  public:
     1178   
     1179    /// \brief \ref Exception for uninitialized parameters.
     1180    ///
     1181    /// This error represents problems in the initialization
     1182    /// of the parameters of the algorithms.
     1183    class UninitializedParameter : public lemon::UninitializedParameter {
     1184    public:
     1185      virtual const char* exceptionName() const {
     1186        return "lemon::DfsVisit::UninitializedParameter";
     1187      }
     1188    };
     1189
     1190    typedef _Traits Traits;
     1191
     1192    typedef typename Traits::Graph Graph;
     1193
     1194    typedef _Visitor Visitor;
     1195
     1196    ///The type of the map indicating which nodes are reached.
     1197    typedef typename Traits::ReachedMap ReachedMap;
     1198
     1199  private:
     1200
     1201    typedef typename Graph::Node Node;
     1202    typedef typename Graph::NodeIt NodeIt;
     1203    typedef typename Graph::Edge Edge;
     1204    typedef typename Graph::OutEdgeIt OutEdgeIt;
     1205
     1206    /// Pointer to the underlying graph.
     1207    const Graph *_graph;
     1208    /// Pointer to the visitor object.
     1209    Visitor *_visitor;
     1210    ///Pointer to the map of reached status of the nodes.
     1211    ReachedMap *_reached;
     1212    ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1213    bool local_reached;
     1214
     1215    std::vector<typename Graph::Edge> _stack;
     1216    int _stack_head;
     1217
     1218    /// \brief Creates the maps if necessary.
     1219    ///
     1220    /// Creates the maps if necessary.
     1221    void create_maps() {
     1222      if(!_reached) {
     1223        local_reached = true;
     1224        _reached = Traits::createReachedMap(*_graph);
     1225      }
     1226    }
     1227
     1228  protected:
     1229
     1230    DfsVisit() {}
     1231   
     1232  public:
     1233
     1234    typedef DfsVisit Create;
     1235
     1236    /// \name Named template parameters
     1237
     1238    ///@{
     1239    template <class T>
     1240    struct DefReachedMapTraits : public Traits {
     1241      typedef T ReachedMap;
     1242      static ReachedMap *createReachedMap(const Graph &graph) {
     1243        throw UninitializedParameter();
     1244      }
     1245    };
     1246    /// \brief \ref named-templ-param "Named parameter" for setting
     1247    /// ReachedMap type
     1248    ///
     1249    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1250    template <class T>
     1251    struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
     1252      typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
     1253    };
     1254    ///@}
     1255
     1256  public:     
     1257   
     1258    /// \brief Constructor.
     1259    ///
     1260    /// Constructor.
     1261    ///
     1262    /// \param graph the graph the algorithm will run on.
     1263    /// \param visitor The visitor of the algorithm.
     1264    ///
     1265    DfsVisit(const Graph& graph, Visitor& visitor)
     1266      : _graph(&graph), _visitor(&visitor),
     1267        _reached(0), local_reached(false) {}
     1268   
     1269    /// \brief Destructor.
     1270    ///
     1271    /// Destructor.
     1272    ~DfsVisit() {
     1273      if(local_reached) delete _reached;
     1274    }
     1275
     1276    /// \brief Sets the map indicating if a node is reached.
     1277    ///
     1278    /// Sets the map indicating if a node is reached.
     1279    /// If you don't use this function before calling \ref run(),
     1280    /// it will allocate one. The destuctor deallocates this
     1281    /// automatically allocated map, of course.
     1282    /// \return <tt> (*this) </tt>
     1283    DfsVisit &reachedMap(ReachedMap &m) {
     1284      if(local_reached) {
     1285        delete _reached;
     1286        local_reached=false;
     1287      }
     1288      _reached = &m;
     1289      return *this;
     1290    }
     1291
     1292  public:
     1293    /// \name Execution control
     1294    /// The simplest way to execute the algorithm is to use
     1295    /// one of the member functions called \c run(...).
     1296    /// \n
     1297    /// If you need more control on the execution,
     1298    /// first you must call \ref init(), then you can add several source nodes
     1299    /// with \ref addSource().
     1300    /// Finally \ref start() will perform the actual path
     1301    /// computation.
     1302
     1303    /// @{
     1304    /// \brief Initializes the internal data structures.
     1305    ///
     1306    /// Initializes the internal data structures.
     1307    ///
     1308    void init() {
     1309      create_maps();
     1310      _stack.resize(countNodes(*_graph));
     1311      _stack_head = -1;
     1312      for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
     1313        _reached->set(u, false);
     1314      }
     1315    }
     1316   
     1317    /// \brief Adds a new source node.
     1318    ///
     1319    /// Adds a new source node to the set of nodes to be processed.
     1320    void addSource(Node s) {
     1321      if(!(*_reached)[s]) {
     1322          _reached->set(s,true);
     1323          _visitor->start(s);
     1324          _visitor->reach(s);
     1325          Edge e;
     1326          _graph->firstOut(e, s);
     1327          if (e != INVALID) {
     1328            _stack[++_stack_head] = e;
     1329          } else {
     1330            _visitor->leave(s);
     1331          }
     1332        }
     1333    }
     1334   
     1335    /// \brief Processes the next edge.
     1336    ///
     1337    /// Processes the next edge.
     1338    ///
     1339    /// \return The processed edge.
     1340    ///
     1341    /// \pre The stack must not be empty!
     1342    Edge processNextEdge() {
     1343      Edge e = _stack[_stack_head];
     1344      Node m = _graph->target(e);
     1345      if(!(*_reached)[m]) {
     1346        _visitor->discover(e);
     1347        _visitor->reach(m);
     1348        _reached->set(m, true);
     1349        _graph->firstOut(_stack[++_stack_head], m);
     1350      } else {
     1351        _visitor->examine(e);
     1352        m = _graph->source(e);
     1353        _graph->nextOut(_stack[_stack_head]);
     1354      }
     1355      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
     1356        _visitor->leave(m);
     1357        --_stack_head;
     1358        if (_stack_head >= 0) {
     1359          _visitor->backtrack(_stack[_stack_head]);
     1360          m = _graph->source(_stack[_stack_head]);
     1361          _graph->nextOut(_stack[_stack_head]);
     1362        } else {
     1363          _visitor->stop(m);     
     1364        }
     1365      }
     1366      return e;
     1367    }
     1368
     1369    /// \brief Next edge to be processed.
     1370    ///
     1371    /// Next edge to be processed.
     1372    ///
     1373    /// \return The next edge to be processed or INVALID if the stack is
     1374    /// empty.
     1375    Edge nextEdge() {
     1376      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
     1377    }
     1378
     1379    /// \brief Returns \c false if there are nodes
     1380    /// to be processed in the queue
     1381    ///
     1382    /// Returns \c false if there are nodes
     1383    /// to be processed in the queue
     1384    ///
     1385    /// \todo This should be called emptyStack() or some "neutral" name.
     1386    bool emptyQueue() { return _stack_head < 0; }
     1387
     1388    /// \brief Returns the number of the nodes to be processed.
     1389    ///
     1390    /// Returns the number of the nodes to be processed in the queue.
     1391    ///
     1392    ///\todo This should be called stackSize() or some "neutral" name.
     1393    int queueSize() { return _stack_head + 1; }
     1394   
     1395    /// \brief Executes the algorithm.
     1396    ///
     1397    /// Executes the algorithm.
     1398    ///
     1399    /// \pre init() must be called and at least one node should be added
     1400    /// with addSource() before using this function.
     1401    void start() {
     1402      while ( !emptyQueue() ) processNextEdge();
     1403    }
     1404   
     1405    /// \brief Executes the algorithm until \c dest is reached.
     1406    ///
     1407    /// Executes the algorithm until \c dest is reached.
     1408    ///
     1409    /// \pre init() must be called and at least one node should be added
     1410    /// with addSource() before using this function.
     1411    void start(Node dest) {
     1412      while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest)
     1413        processNextEdge();
     1414    }
     1415   
     1416    /// \brief Executes the algorithm until a condition is met.
     1417    ///
     1418    /// Executes the algorithm until a condition is met.
     1419    ///
     1420    /// \pre init() must be called and at least one node should be added
     1421    /// with addSource() before using this function.
     1422    ///
     1423    /// \param nm must be a bool (or convertible) edge map. The algorithm
     1424    /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
     1425    ///
     1426    /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
     1427    /// not a node map.
     1428    template <typename EM>
     1429    void start(const EM &em) {
     1430      while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
     1431    }
     1432
     1433    /// \brief Runs %DFS algorithm from node \c s.
     1434    ///
     1435    /// This method runs the %DFS algorithm from a root node \c s.
     1436    /// \note d.run(s) is just a shortcut of the following code.
     1437    /// \code
     1438    ///   d.init();
     1439    ///   d.addSource(s);
     1440    ///   d.start();
     1441    /// \endcode
     1442    void run(Node s) {
     1443      init();
     1444      addSource(s);
     1445      start();
     1446    }
     1447    ///@}
     1448
     1449    /// \name Query Functions
     1450    /// The result of the %DFS algorithm can be obtained using these
     1451    /// functions.\n
     1452    /// Before the use of these functions,
     1453    /// either run() or start() must be called.
     1454    ///@{
     1455    /// \brief Checks if a node is reachable from the root.
     1456    ///
     1457    /// Returns \c true if \c v is reachable from the root(s).
     1458    /// \warning The source nodes are inditated as unreachable.
     1459    /// \pre Either \ref run() or \ref start()
     1460    /// must be called before using this function.
     1461    ///
     1462    bool reached(Node v) { return (*_reached)[v]; }
     1463    ///@}
     1464  };
     1465
     1466
    11351467} //END OF NAMESPACE LEMON
    11361468
Note: See TracChangeset for help on using the changeset viewer.