COIN-OR::LEMON - Graph Library

Changeset 2306:42cce226b87b in lemon-0.x


Ignore:
Timestamp:
11/21/06 19:22:08 (13 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

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • demo/topology_demo.cc

    r2242 r2306  
    3737
    3838using namespace lemon;
     39using namespace lemon::dim2;
    3940using namespace std;
    4041
     
    5051
    5152  Graph graph;
    52   Graph::NodeMap<dim2::Point<double> > coords(graph);
     53  Graph::NodeMap<Point<double> > coords(graph);
    5354
    5455  UGraphReader<Graph>("u_components.lgf", graph).
     
    6465  graphToEps(graph, "connected_components.eps").undirected().
    6566    coords(coords).scaleToA4().enableParallel().
    66     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
    6767    nodeColors(composeMap(palette, compMap)).run();
    6868
     
    7575
    7676  Graph graph;
    77   Graph::NodeMap<dim2::Point<double> > coords(graph);
     77  Graph::NodeMap<Point<double> > coords(graph);
    7878
    7979  GraphReader<Graph>("dir_components.lgf", graph).
     
    9090
    9191  graphToEps(graph, "strongly_connected_components.eps").
    92     coords(coords).scaleToA4().enableParallel().
    93     drawArrows().arrowWidth(10.0).arrowLength(10.0).
    94     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
     92    coords(coords).scaleToA4().enableParallel().drawArrows().
    9593    nodeColors(composeMap(palette, compMap)).
    9694    edgeColors(composeMap(functorMap(&color), cutMap)).run();
     
    105103
    106104  Graph graph;
    107   Graph::NodeMap<dim2::Point<double> > coords(graph);
     105  Graph::NodeMap<Point<double> > coords(graph);
    108106
    109107  UGraphReader<Graph>("u_components.lgf", graph).
     
    121119  graphToEps(graph, "bi_node_connected_components.eps").undirected().
    122120    coords(coords).scaleToA4().enableParallel().
    123     parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
    124121    edgeColors(composeMap(palette, compMap)).
    125122    nodeColors(composeMap(functorMap(&color), cutMap)).
     
    135132
    136133  Graph graph;
    137   Graph::NodeMap<dim2::Point<double> > coords(graph);
     134  Graph::NodeMap<Point<double> > coords(graph);
    138135
    139136  UGraphReader<Graph>("u_components.lgf", graph).
     
    151148  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
    152149    coords(coords).scaleToA4().enableParallel().
    153     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
    154150    nodeColors(composeMap(palette, compMap)).
    155151    edgeColors(composeMap(functorMap(&color), cutMap)).run();
     
    164160
    165161  Graph graph;
    166   Graph::NodeMap<dim2::Point<double> > coords(graph);
     162  Graph::NodeMap<Point<double> > coords(graph);
    167163
    168164  UGraphReader<Graph>("partitions.lgf", graph).
     
    178174  graphToEps(graph, "bipartite_partitions.eps").undirected().
    179175    coords(coords).scaleToA4().enableParallel().
    180     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
    181176    nodeColors(composeMap(functorMap(&color), partMap)).run();
    182177 
  • lemon/bfs.h

    r2300 r2306  
    588588    }
    589589   
    590     ///Executes the algorithm until \c dest is reached.
    591 
    592     ///Executes the algorithm until \c dest is reached.
     590    ///Executes the algorithm until \c dest is the next node to processed.
     591
     592    ///Executes the algorithm until \c dest is the next node to processed.
    593593    ///
    594594    ///\pre init() must be called and at least one node should be added
     
    615615    ///with addSource() before using this function.
    616616    ///
    617     ///\param nm must be a bool (or convertible) node map. The algorithm
    618     ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     617    ///\param nm must be a bool (or convertible) node map. The
     618    ///algorithm will stop when for the next processable node \c v is
     619    ///<tt>nm[v]</tt> true.
    619620    ///\todo query the reached target
    620621    template<class NM>
     
    634635    ///- The distance of each node from the root.
    635636    ///
    636     ///\note d.run(s) is just a shortcut of the following code.
     637    ///\note b.run(s) is just a shortcut of the following code.
    637638    ///\code
    638     ///  d.init();
    639     ///  d.addSource(s);
    640     ///  d.start();
     639    ///  b.init();
     640    ///  b.addSource(s);
     641    ///  b.start();
    641642    ///\endcode
    642643    void run(Node s) {
     
    652653    ///\return The length of the shortest s---t path if there exists one,
    653654    ///0 otherwise.
    654     ///\note Apart from the return value, d.run(s) is
     655    ///\note Apart from the return value, b.run(s) is
    655656    ///just a shortcut of the following code.
    656657    ///\code
    657     ///  d.init();
    658     ///  d.addSource(s);
    659     ///  d.start(t);
     658    ///  b.init();
     659    ///  b.addSource(s);
     660    ///  b.start(t);
    660661    ///\endcode
    661662    int run(Node s,Node t) {
     
    672673    ///functions.\n
    673674    ///Before the use of these functions,
    674     ///either run() or start() must be called.
     675    ///either run() or start() must be calleb.
    675676   
    676677    ///@{
     
    944945    typedef typename TR::DistMap DistMap;
    945946
    946 public:
     947  public:
    947948    /// Constructor.
    948949    BfsWizard() : TR() {}
     
    11051106  }
    11061107
     1108#ifdef DOXYGEN
     1109  /// \brief Visitor class for bfs.
     1110  /// 
     1111  /// It gives a simple interface for a functional interface for bfs
     1112  /// traversal. The traversal on a linear data structure.
     1113  template <typename _Graph>
     1114  struct BfsVisitor {
     1115    typedef _Graph Graph;
     1116    typedef typename Graph::Edge Edge;
     1117    typedef typename Graph::Node Node;
     1118    /// \brief Called when the edge reach a node.
     1119    ///
     1120    /// It is called when the bfs find an edge which target is not
     1121    /// reached yet.
     1122    void discover(const Edge& edge) {}
     1123    /// \brief Called when the node reached first time.
     1124    ///
     1125    /// It is Called when the node reached first time.
     1126    void reach(const Node& node) {}
     1127    /// \brief Called when the edge examined but target of the edge
     1128    /// already discovered.
     1129    ///
     1130    /// It called when the edge examined but the target of the edge
     1131    /// already discovered.
     1132    void examine(const Edge& edge) {}
     1133    /// \brief Called for the source node of the bfs.
     1134    ///
     1135    /// It is called for the source node of the bfs.
     1136    void start(const Node& node) {}
     1137    /// \brief Called when the node processed.
     1138    ///
     1139    /// It is Called when the node processed.
     1140    void process(const Node& node) {}
     1141  };
     1142#else
     1143  template <typename _Graph>
     1144  struct BfsVisitor {
     1145    typedef _Graph Graph;
     1146    typedef typename Graph::Edge Edge;
     1147    typedef typename Graph::Node Node;
     1148    void discover(const Edge&) {}
     1149    void reach(const Node&) {}
     1150    void examine(const Edge&) {}
     1151    void start(const Node&) {}
     1152    void process(const Node&) {}
     1153
     1154    template <typename _Visitor>
     1155    struct Constraints {
     1156      void constraints() {
     1157        Edge edge;
     1158        Node node;
     1159        visitor.discover(edge);
     1160        visitor.reach(node);
     1161        visitor.examine(edge);
     1162        visitor.start(node);
     1163        visitor.process(node);
     1164      }
     1165      _Visitor& visitor;
     1166    };
     1167  };
     1168#endif
     1169
     1170  /// \brief Default traits class of BfsVisit class.
     1171  ///
     1172  /// Default traits class of BfsVisit class.
     1173  /// \param _Graph Graph type.
     1174  template<class _Graph>
     1175  struct BfsVisitDefaultTraits {
     1176
     1177    /// \brief The graph type the algorithm runs on.
     1178    typedef _Graph Graph;
     1179
     1180    /// \brief The type of the map that indicates which nodes are reached.
     1181    ///
     1182    /// The type of the map that indicates which nodes are reached.
     1183    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
     1184    /// \todo named parameter to set this type, function to read and write.
     1185    typedef typename Graph::template NodeMap<bool> ReachedMap;
     1186
     1187    /// \brief Instantiates a ReachedMap.
     1188    ///
     1189    /// This function instantiates a \ref ReachedMap.
     1190    /// \param graph is the graph, to which
     1191    /// we would like to define the \ref ReachedMap.
     1192    static ReachedMap *createReachedMap(const Graph &graph) {
     1193      return new ReachedMap(graph);
     1194    }
     1195
     1196  };
     1197 
     1198  /// %BFS Visit algorithm class.
     1199 
     1200  /// \ingroup flowalgs
     1201  /// This class provides an efficient implementation of the %BFS algorithm
     1202  /// with visitor interface.
     1203  ///
     1204  /// The %BfsVisit class provides an alternative interface to the Bfs
     1205  /// class. It works with callback mechanism, the BfsVisit object calls
     1206  /// on every bfs event the \c Visitor class member functions.
     1207  ///
     1208  /// \param _Graph The graph type the algorithm runs on. The default value is
     1209  /// \ref ListGraph. The value of _Graph is not used directly by Bfs, it
     1210  /// is only passed to \ref BfsDefaultTraits.
     1211  /// \param _Visitor The Visitor object for the algorithm. The
     1212  /// \ref BfsVisitor "BfsVisitor<_Graph>" is an empty Visitor which
     1213  /// does not observe the Bfs events. If you want to observe the bfs
     1214  /// events you should implement your own Visitor class.
     1215  /// \param _Traits Traits class to set various data types used by the
     1216  /// algorithm. The default traits class is
     1217  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Graph>".
     1218  /// See \ref BfsVisitDefaultTraits for the documentation of
     1219  /// a Bfs visit traits class.
     1220  ///
     1221  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
     1222#ifdef DOXYGEN
     1223  template <typename _Graph, typename _Visitor, typename _Traits>
     1224#else
     1225  template <typename _Graph = ListGraph,
     1226            typename _Visitor = BfsVisitor<_Graph>,
     1227            typename _Traits = BfsDefaultTraits<_Graph> >
     1228#endif
     1229  class BfsVisit {
     1230  public:
     1231   
     1232    /// \brief \ref Exception for uninitialized parameters.
     1233    ///
     1234    /// This error represents problems in the initialization
     1235    /// of the parameters of the algorithms.
     1236    class UninitializedParameter : public lemon::UninitializedParameter {
     1237    public:
     1238      virtual const char* what() const throw()
     1239      {
     1240        return "lemon::BfsVisit::UninitializedParameter";
     1241      }
     1242    };
     1243
     1244    typedef _Traits Traits;
     1245
     1246    typedef typename Traits::Graph Graph;
     1247
     1248    typedef _Visitor Visitor;
     1249
     1250    ///The type of the map indicating which nodes are reached.
     1251    typedef typename Traits::ReachedMap ReachedMap;
     1252
     1253  private:
     1254
     1255    typedef typename Graph::Node Node;
     1256    typedef typename Graph::NodeIt NodeIt;
     1257    typedef typename Graph::Edge Edge;
     1258    typedef typename Graph::OutEdgeIt OutEdgeIt;
     1259
     1260    /// Pointer to the underlying graph.
     1261    const Graph *_graph;
     1262    /// Pointer to the visitor object.
     1263    Visitor *_visitor;
     1264    ///Pointer to the map of reached status of the nodes.
     1265    ReachedMap *_reached;
     1266    ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1267    bool local_reached;
     1268
     1269    std::vector<typename Graph::Node> _list;
     1270    int _list_front, _list_back;
     1271
     1272    /// \brief Creates the maps if necessary.
     1273    ///
     1274    /// Creates the maps if necessary.
     1275    void create_maps() {
     1276      if(!_reached) {
     1277        local_reached = true;
     1278        _reached = Traits::createReachedMap(*_graph);
     1279      }
     1280    }
     1281
     1282  protected:
     1283
     1284    BfsVisit() {}
     1285   
     1286  public:
     1287
     1288    typedef BfsVisit Create;
     1289
     1290    /// \name Named template parameters
     1291
     1292    ///@{
     1293    template <class T>
     1294    struct DefReachedMapTraits : public Traits {
     1295      typedef T ReachedMap;
     1296      static ReachedMap *createReachedMap(const Graph &graph) {
     1297        throw UninitializedParameter();
     1298      }
     1299    };
     1300    /// \brief \ref named-templ-param "Named parameter" for setting
     1301    /// ReachedMap type
     1302    ///
     1303    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1304    template <class T>
     1305    struct DefReachedMap : public BfsVisit< Graph, Visitor,
     1306                                            DefReachedMapTraits<T> > {
     1307      typedef BfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
     1308    };
     1309    ///@}
     1310
     1311  public:     
     1312   
     1313    /// \brief Constructor.
     1314    ///
     1315    /// Constructor.
     1316    ///
     1317    /// \param graph the graph the algorithm will run on.
     1318    /// \param visitor The visitor of the algorithm.
     1319    ///
     1320    BfsVisit(const Graph& graph, Visitor& visitor)
     1321      : _graph(&graph), _visitor(&visitor),
     1322        _reached(0), local_reached(false) {}
     1323   
     1324    /// \brief Destructor.
     1325    ///
     1326    /// Destructor.
     1327    ~BfsVisit() {
     1328      if(local_reached) delete _reached;
     1329    }
     1330
     1331    /// \brief Sets the map indicating if a node is reached.
     1332    ///
     1333    /// Sets the map indicating if a node is reached.
     1334    /// If you don't use this function before calling \ref run(),
     1335    /// it will allocate one. The destuctor deallocates this
     1336    /// automatically allocated map, of course.
     1337    /// \return <tt> (*this) </tt>
     1338    BfsVisit &reachedMap(ReachedMap &m) {
     1339      if(local_reached) {
     1340        delete _reached;
     1341        local_reached = false;
     1342      }
     1343      _reached = &m;
     1344      return *this;
     1345    }
     1346
     1347  public:
     1348    /// \name Execution control
     1349    /// The simplest way to execute the algorithm is to use
     1350    /// one of the member functions called \c run(...).
     1351    /// \n
     1352    /// If you need more control on the execution,
     1353    /// first you must call \ref init(), then you can adda source node
     1354    /// with \ref addSource().
     1355    /// Finally \ref start() will perform the actual path
     1356    /// computation.
     1357
     1358    /// @{
     1359    /// \brief Initializes the internal data structures.
     1360    ///
     1361    /// Initializes the internal data structures.
     1362    ///
     1363    void init() {
     1364      create_maps();
     1365      _list.resize(countNodes(*_graph));
     1366      _list_front = _list_back = -1;
     1367      for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
     1368        _reached->set(u, false);
     1369      }
     1370    }
     1371   
     1372    /// \brief Adds a new source node.
     1373    ///
     1374    /// Adds a new source node to the set of nodes to be processed.
     1375    void addSource(Node s) {
     1376      if(!(*_reached)[s]) {
     1377          _reached->set(s,true);
     1378          _visitor->start(s);
     1379          _visitor->reach(s);
     1380          _list[++_list_back] = s;
     1381        }
     1382    }
     1383   
     1384    /// \brief Processes the next node.
     1385    ///
     1386    /// Processes the next node.
     1387    ///
     1388    /// \return The processed node.
     1389    ///
     1390    /// \pre The queue must not be empty!
     1391    Node processNextNode() {
     1392      Node n = _list[++_list_front];
     1393      _visitor->process(n);
     1394      Edge e;
     1395      for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
     1396        Node m = _graph->target(e);
     1397        if (!(*_reached)[m]) {
     1398          _visitor->discover(e);
     1399          _visitor->reach(m);
     1400          _reached->set(m, true);
     1401          _list[++_list_back] = m;
     1402        } else {
     1403          _visitor->examine(e);
     1404        }
     1405      }
     1406      return n;
     1407    }
     1408
     1409    /// \brief Processes the next node.
     1410    ///
     1411    /// Processes the next node. And checks that the given target node
     1412    /// is reached. If the target node is reachable from the processed
     1413    /// node then the reached parameter will be set true. The reached
     1414    /// parameter should be initially false.
     1415    ///
     1416    /// \param target The target node.
     1417    /// \retval reached Indicates that the target node is reached.
     1418    /// \return The processed node.
     1419    ///
     1420    /// \warning The queue must not be empty!
     1421    Node processNextNode(Node target, bool& reached) {
     1422      Node n = _list[++_list_front];
     1423      _visitor->process(n);
     1424      Edge e;
     1425      for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
     1426        Node m = _graph->target(e);
     1427        if (!(*_reached)[m]) {
     1428          _visitor->discover(e);
     1429          _visitor->reach(m);
     1430          _reached->set(m, true);
     1431          _list[++_list_back] = m;
     1432          reached = reached || (target == m);
     1433        } else {
     1434          _visitor->examine(e);
     1435        }
     1436      }
     1437      return n;
     1438    }
     1439
     1440    /// \brief Processes the next node.
     1441    ///
     1442    /// Processes the next node. And checks that at least one of
     1443    /// reached node has true value in the \c nm nodemap. If one node
     1444    /// with true value is reachable from the processed node then the
     1445    /// reached parameter will be set true. The reached parameter
     1446    /// should be initially false.
     1447    ///
     1448    /// \param target The nodemaps of possible targets.
     1449    /// \retval reached Indicates that one of the target nodes is reached.
     1450    /// \return The processed node.
     1451    ///
     1452    /// \warning The queue must not be empty!
     1453    template <typename NM>
     1454    Node processNextNode(const NM& nm, bool& reached) {
     1455      Node n = _list[++_list_front];
     1456      _visitor->process(n);
     1457      Edge e;
     1458      for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
     1459        Node m = _graph->target(e);
     1460        if (!(*_reached)[m]) {
     1461          _visitor->discover(e);
     1462          _visitor->reach(m);
     1463          _reached->set(m, true);
     1464          _list[++_list_back] = m;
     1465          reached = reached || nm[m];
     1466        } else {
     1467          _visitor->examine(e);
     1468        }
     1469      }
     1470      return n;
     1471    }
     1472
     1473    /// \brief Next node to be processed.
     1474    ///
     1475    /// Next node to be processed.
     1476    ///
     1477    /// \return The next node to be processed or INVALID if the stack is
     1478    /// empty.
     1479    Node nextNode() {
     1480      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
     1481    }
     1482
     1483    /// \brief Returns \c false if there are nodes
     1484    /// to be processed in the queue
     1485    ///
     1486    /// Returns \c false if there are nodes
     1487    /// to be processed in the queue
     1488    bool emptyQueue() { return _list_front == _list_back; }
     1489
     1490    /// \brief Returns the number of the nodes to be processed.
     1491    ///
     1492    /// Returns the number of the nodes to be processed in the queue.
     1493    int queueSize() { return _list_back - _list_front; }
     1494   
     1495    /// \brief Executes the algorithm.
     1496    ///
     1497    /// Executes the algorithm.
     1498    ///
     1499    /// \pre init() must be called and at least one node should be added
     1500    /// with addSource() before using this function.
     1501    void start() {
     1502      while ( !emptyQueue() ) processNextNode();
     1503    }
     1504   
     1505    /// \brief Executes the algorithm until \c dest will be next processed.
     1506    ///
     1507    /// Executes the algorithm until \c dest will be next processed.
     1508    ///
     1509    /// \pre init() must be called and at least one node should be added
     1510    /// with addSource() before using this function.
     1511    void start(Node dest) {
     1512      bool reached = false;
     1513      while (!emptyQueue() && !reached) {
     1514        processNextNode(dest, reached);
     1515      }
     1516    }
     1517   
     1518    /// \brief Executes the algorithm until a condition is met.
     1519    ///
     1520    /// Executes the algorithm until a condition is met.
     1521    ///
     1522    /// \pre init() must be called and at least one node should be added
     1523    /// with addSource() before using this function.
     1524    ///
     1525    ///\param nm must be a bool (or convertible) node map. The
     1526    ///algorithm will stop when it reaches a node \c v with
     1527    ///<tt>nm[v]</tt> true.
     1528    template <typename NM>
     1529    void start(const NM &nm) {
     1530      bool reached = false;
     1531      while (!emptyQueue() && !reached) {
     1532        processNextNode(nm, reached);
     1533      }
     1534    }
     1535
     1536    /// \brief Runs %BFSVisit algorithm from node \c s.
     1537    ///
     1538    /// This method runs the %BFS algorithm from a root node \c s.
     1539    /// \note b.run(s) is just a shortcut of the following code.
     1540    ///\code
     1541    ///   b.init();
     1542    ///   b.addSource(s);
     1543    ///   b.start();
     1544    ///\endcode
     1545    void run(Node s) {
     1546      init();
     1547      addSource(s);
     1548      start();
     1549    }
     1550
     1551    /// \brief Runs %BFSVisit algorithm to visit all nodes in the graph.
     1552    ///   
     1553    /// This method runs the %BFS algorithm in order to
     1554    /// compute the %BFS path to each node. The algorithm computes
     1555    /// - The %BFS tree.
     1556    /// - The distance of each node from the root in the %BFS tree.
     1557    ///
     1558    ///\note b.run() is just a shortcut of the following code.
     1559    ///\code
     1560    ///  b.init();
     1561    ///  for (NodeIt it(graph); it != INVALID; ++it) {
     1562    ///    if (!b.reached(it)) {
     1563    ///      b.addSource(it);
     1564    ///      b.start();
     1565    ///    }
     1566    ///  }
     1567    ///\endcode
     1568    void run() {
     1569      init();
     1570      for (NodeIt it(*_graph); it != INVALID; ++it) {
     1571        if (!reached(it)) {
     1572          addSource(it);
     1573          start();
     1574        }
     1575      }
     1576    }
     1577    ///@}
     1578
     1579    /// \name Query Functions
     1580    /// The result of the %BFS algorithm can be obtained using these
     1581    /// functions.\n
     1582    /// Before the use of these functions,
     1583    /// either run() or start() must be called.
     1584    ///@{
     1585
     1586    /// \brief Checks if a node is reachable from the root.
     1587    ///
     1588    /// Returns \c true if \c v is reachable from the root(s).
     1589    /// \warning The source nodes are inditated as unreachable.
     1590    /// \pre Either \ref run() or \ref start()
     1591    /// must be called before using this function.
     1592    ///
     1593    bool reached(Node v) { return (*_reached)[v]; }
     1594    ///@}
     1595  };
     1596
    11071597} //END OF NAMESPACE LEMON
    11081598
  • lemon/topology.h

    r2260 r2306  
    13901390  }
    13911391
     1392  namespace _topology_bits {
     1393
     1394    template <typename Graph>
     1395    class BipartiteVisitor : public BfsVisitor<Graph> {
     1396    public:
     1397      typedef typename Graph::Edge Edge;
     1398      typedef typename Graph::Node Node;
     1399
     1400      BipartiteVisitor(const Graph& graph, bool& bipartite)
     1401        : _graph(graph), _part(graph), _bipartite(bipartite) {}
     1402     
     1403      void start(const Node& node) {
     1404        _part[node] = true;
     1405      }
     1406      void discover(const Edge& edge) {
     1407        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
     1408      }
     1409      void examine(const Edge& edge) {
     1410        _bipartite = _bipartite &&
     1411          _part[_graph.target(edge)] != _part[_graph.source(edge)];
     1412      }
     1413
     1414    private:
     1415
     1416      const Graph& _graph;
     1417      typename Graph::template NodeMap<bool> _part;
     1418      bool& _bipartite;
     1419    };
     1420
     1421    template <typename Graph, typename PartMap>
     1422    class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
     1423    public:
     1424      typedef typename Graph::Edge Edge;
     1425      typedef typename Graph::Node Node;
     1426
     1427      BipartitePartitionsVisitor(const Graph& graph,
     1428                                 PartMap& part, bool& bipartite)
     1429        : _graph(graph), _part(part), _bipartite(bipartite) {}
     1430     
     1431      void start(const Node& node) {
     1432        _part.set(node, true);
     1433      }
     1434      void discover(const Edge& edge) {
     1435        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
     1436      }
     1437      void examine(const Edge& edge) {
     1438        _bipartite = _bipartite &&
     1439          _part[_graph.target(edge)] != _part[_graph.source(edge)];
     1440      }
     1441
     1442    private:
     1443
     1444      const Graph& _graph;
     1445      PartMap& _part;
     1446      bool& _bipartite;
     1447    };
     1448  }
     1449
    13921450  /// \ingroup topology
    13931451  ///
     
    14031461  template<typename UGraph>
    14041462  inline bool bipartite(const UGraph &graph){
     1463    using namespace _topology_bits;
     1464
    14051465    checkConcept<concepts::UGraph, UGraph>();
    14061466   
     
    14081468    typedef typename UGraph::EdgeIt EdgeIt;
    14091469   
    1410     Bfs<UGraph> bfs(graph);
     1470    bool bipartite = true;
     1471
     1472    BipartiteVisitor<UGraph>
     1473      visitor(graph, bipartite);
     1474    BfsVisit<UGraph, BipartiteVisitor<UGraph> >
     1475      bfs(graph, visitor);
    14111476    bfs.init();
    1412     for(NodeIt i(graph);i!=INVALID;++i){
    1413       if(!bfs.reached(i)){
    1414         bfs.run(i);
    1415       }
    1416     }
    1417     for(EdgeIt i(graph);i!=INVALID;++i){
    1418       if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
     1477    for(NodeIt it(graph); it != INVALID; ++it) {
     1478      if(!bfs.reached(it)){
     1479        bfs.addSource(it);
     1480        while (!bfs.emptyQueue()) {
     1481          bfs.processNextNode();
     1482          if (!bipartite) return false;
     1483        }
     1484      }
    14191485    }
    14201486    return true;
     
    14401506  template<typename UGraph, typename NodeMap>
    14411507  inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
     1508    using namespace _topology_bits;
     1509
    14421510    checkConcept<concepts::UGraph, UGraph>();
    14431511   
     
    14451513    typedef typename UGraph::NodeIt NodeIt;
    14461514    typedef typename UGraph::EdgeIt EdgeIt;
    1447  
    1448     Bfs<UGraph> bfs(graph);
     1515
     1516    bool bipartite = true;
     1517
     1518    BipartitePartitionsVisitor<UGraph, NodeMap>
     1519      visitor(graph, partMap, bipartite);
     1520    BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> >
     1521      bfs(graph, visitor);
    14491522    bfs.init();
    1450     for(NodeIt i(graph);i!=INVALID;++i){
    1451       if(!bfs.reached(i)){
    1452         bfs.addSource(i);
    1453         for(Node j=bfs.processNextNode();!bfs.emptyQueue();
    1454             j=bfs.processNextNode()){
    1455           partMap.set(j,bfs.dist(j)%2==0);
    1456         }
    1457       }
    1458     }
    1459     for(EdgeIt i(graph);i!=INVALID;++i){
    1460       if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
     1523    for(NodeIt it(graph); it != INVALID; ++it) {
     1524      if(!bfs.reached(it)){
     1525        bfs.addSource(it);
     1526        while (!bfs.emptyQueue()) {
     1527          bfs.processNextNode();
     1528          if (!bipartite) return false;
     1529        }
     1530      }
     1531    }
     1532    return true;
     1533  }
     1534
     1535  /// \brief Returns true when there is not loop edge in the graph.
     1536  ///
     1537  /// Returns true when there is not loop edge in the graph.
     1538  template <typename Graph>
     1539  bool loopFree(const Graph& graph) {
     1540    for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
     1541      if (graph.source(it) == graph.target(it)) return false;
     1542    }
     1543    return true;
     1544  }
     1545
     1546  /// \brief Returns true when there is not parallel edges in the graph.
     1547  ///
     1548  /// Returns true when there is not parallel edges in the graph.
     1549  template <typename Graph>
     1550  bool parallelFree(const Graph& graph) {
     1551    typename Graph::template NodeMap<bool> reached(graph, false);
     1552    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     1553      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
     1554        if (reached[graph.target(e)]) return false;
     1555        reached.set(graph.target(e), true);
     1556      }
     1557      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
     1558        reached.set(graph.target(e), false);
     1559      }
     1560    }
     1561    return true;
     1562  }
     1563
     1564  /// \brief Returns true when there is not loop edge and parallel
     1565  /// edges in the graph.
     1566  ///
     1567  /// Returns true when there is not loop edge and parallel edges in
     1568  /// the graph.
     1569  template <typename Graph>
     1570  bool simpleGraph(const Graph& graph) {
     1571    typename Graph::template NodeMap<bool> reached(graph, false);
     1572    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     1573      reached.set(n, true);
     1574      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
     1575        if (reached[graph.target(e)]) return false;
     1576        reached.set(graph.target(e), true);
     1577      }
     1578      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
     1579        reached.set(graph.target(e), false);
     1580      }
     1581      reached.set(n, false);
    14611582    }
    14621583    return true;
Note: See TracChangeset for help on using the changeset viewer.