COIN-OR::LEMON - Graph Library

Changeset 1800:d391ea416aa0 in lemon-0.x for lemon/topology.h


Ignore:
Timestamp:
11/16/05 10:10:24 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2343
Message:

bipartite by szakall

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/topology.h

    r1793 r1800  
    481481   
    482482    template <typename Graph>
    483     class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     483    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
    484484    public:
    485485      typedef typename Graph::Node Node;
     
    487487      typedef typename Graph::UndirEdge UndirEdge;
    488488
    489       CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
     489      CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
    490490        : _graph(graph), _compNum(compNum),
    491491          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     
    539539
    540540    template <typename Graph, typename EdgeMap>
    541     class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     541    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
    542542    public:
    543543      typedef typename Graph::Node Node;
     
    545545      typedef typename Graph::UndirEdge UndirEdge;
    546546
    547       NodeBiconnectedComponentsVisitor(const Graph& graph,
     547      BiNodeConnectedComponentsVisitor(const Graph& graph,
    548548                                       EdgeMap& compMap, int &compNum)
    549549        : _graph(graph), _compMap(compMap), _compNum(compNum),
     
    619619
    620620    template <typename Graph, typename NodeMap>
    621     class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
     621    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
    622622    public:
    623623      typedef typename Graph::Node Node;
     
    625625      typedef typename Graph::UndirEdge UndirEdge;
    626626
    627       NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
     627      BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
    628628                                     int& cutNum)
    629629        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
     
    697697
    698698  template <typename UndirGraph>
    699   int countNodeBiconnectedComponents(const UndirGraph& graph);
     699  int countBiNodeConnectedComponents(const UndirGraph& graph);
    700700
    701701  /// \ingroup topology
     
    712712  template <typename UndirGraph>
    713713  bool biNodeConnected(const UndirGraph& graph) {
    714     return countNodeBiconnectedComponents(graph) == 1;
     714    return countBiNodeConnectedComponents(graph) == 1;
    715715  }
    716716
     
    727727  /// \return The number of components.
    728728  template <typename UndirGraph>
    729   int countNodeBiconnectedComponents(const UndirGraph& graph) {
     729  int countBiNodeConnectedComponents(const UndirGraph& graph) {
    730730    checkConcept<concept::UndirGraph, UndirGraph>();
    731731    typedef typename UndirGraph::NodeIt NodeIt;
     
    733733    using namespace _topology_bits;
    734734
    735     typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
     735    typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
    736736
    737737    int compNum = 0;
     
    779779    using namespace _topology_bits;
    780780
    781     typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
     781    typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
    782782   
    783783    int compNum = 0;
     
    819819    using namespace _topology_bits;
    820820
    821     typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
     821    typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
    822822   
    823823    int cutNum = 0;
     
    839839   
    840840    template <typename Graph>
    841     class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     841    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
    842842    public:
    843843      typedef typename Graph::Node Node;
     
    845845      typedef typename Graph::UndirEdge UndirEdge;
    846846
    847       CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
     847      CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
    848848        : _graph(graph), _compNum(compNum),
    849849          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
     
    895895
    896896    template <typename Graph, typename NodeMap>
    897     class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
     897    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
    898898    public:
    899899      typedef typename Graph::Node Node;
     
    901901      typedef typename Graph::UndirEdge UndirEdge;
    902902
    903       EdgeBiconnectedComponentsVisitor(const Graph& graph,
     903      BiEdgeConnectedComponentsVisitor(const Graph& graph,
    904904                                       NodeMap& compMap, int &compNum)
    905905        : _graph(graph), _compMap(compMap), _compNum(compNum),
     
    962962
    963963    template <typename Graph, typename EdgeMap>
    964     class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
     964    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
    965965    public:
    966966      typedef typename Graph::Node Node;
     
    968968      typedef typename Graph::UndirEdge UndirEdge;
    969969
    970       EdgeBiconnectedCutEdgesVisitor(const Graph& graph,
     970      BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
    971971                                     EdgeMap& cutMap, int &cutNum)
    972972        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
     
    10241024
    10251025  template <typename UndirGraph>
    1026   int countEdgeBiconnectedComponents(const UndirGraph& graph);
     1026  int countbiEdgeConnectedComponents(const UndirGraph& graph);
    10271027
    10281028  /// \ingroup topology
     
    10391039  template <typename UndirGraph>
    10401040  bool biEdgeConnected(const UndirGraph& graph) {
    1041     return countEdgeBiconnectedComponents(graph) == 1;
     1041    return countBiEdgeConnectedComponents(graph) == 1;
    10421042  }
    10431043
     
    10541054  /// \return The number of components.
    10551055  template <typename UndirGraph>
    1056   int countEdgeBiconnectedComponents(const UndirGraph& graph) {
     1056  int countBiEdgeConnectedComponents(const UndirGraph& graph) {
    10571057    checkConcept<concept::UndirGraph, UndirGraph>();
    10581058    typedef typename UndirGraph::NodeIt NodeIt;
     
    10601060    using namespace _topology_bits;
    10611061
    1062     typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
     1062    typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
    10631063   
    10641064    int compNum = 0;
     
    11051105    using namespace _topology_bits;
    11061106
    1107     typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
     1107    typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
    11081108   
    11091109    int compNum = 0;
     
    11461146    using namespace _topology_bits;
    11471147
    1148     typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
     1148    typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
    11491149   
    11501150    int cutNum = 0;
     
    13891389  /// \ingroup topology
    13901390  ///
    1391   /// \brief Check that the given undirected graph is bipartite.
    1392   ///
    1393   /// Check that the given undirected graph is bipartite.
     1391  /// \brief Check if the given undirected graph is bipartite or not
     1392  ///
     1393  /// The function checks if the given undirected \c graph graph is bipartite
     1394  /// or not. The \ref Bfs algorithm is used to calculate the result.
    13941395  /// \param graph The undirected graph.
    1395   /// \return %True when the nodes can be separated into two sets that
    1396   /// there are not connected nodes in neither sets.
    1397   template <typename UndirGraph>
    1398   bool bipartite(const UndirGraph& graph) {
     1396  /// \return %True if \c graph is bipartite, %false otherwise.
     1397  /// \sa bipartitePartitions
     1398  ///
     1399  /// \author Balazs Attila Mihaly 
     1400  template<typename UndirGraph>
     1401  inline bool bipartite(const UndirGraph &graph){
    13991402    checkConcept<concept::UndirGraph, UndirGraph>();
     1403   
     1404    typedef typename UndirGraph::NodeIt NodeIt;
     1405    typedef typename UndirGraph::EdgeIt EdgeIt;
     1406   
     1407    Bfs<UndirGraph> bfs(graph);
     1408    bfs.init();
     1409    for(NodeIt i(graph);i!=INVALID;++i){
     1410      if(!bfs.reached(i)){
     1411        bfs.run(i);
     1412      }
     1413    }
     1414    for(EdgeIt i(graph);i!=INVALID;++i){
     1415      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
     1416    }
     1417    return true;
     1418  };
     1419 
     1420  /// \ingroup topology
     1421  ///
     1422  /// \brief Check if the given undirected graph is bipartite or not
     1423  ///
     1424  /// The function checks if the given undirected graph is bipartite
     1425  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
     1426  /// During the execution, the \c partMap will be set as the two
     1427  /// partitions of the graph.
     1428  /// \param graph The undirected graph.
     1429  /// \retval partMap A writeable bool map of nodes. It will be set as the
     1430  /// two partitions of the graph.
     1431  /// \return %True if \c graph is bipartite, %false otherwise.
     1432  ///
     1433  /// \author Balazs Attila Mihaly 
     1434  ///
     1435  /// \image html bipartite_partitions.png
     1436  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
     1437  template<typename UndirGraph, typename NodeMap>
     1438  inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
     1439    checkConcept<concept::UndirGraph, UndirGraph>();
     1440   
    14001441    typedef typename UndirGraph::Node Node;
    14011442    typedef typename UndirGraph::NodeIt NodeIt;
    1402     typedef typename UndirGraph::Edge Edge;
    1403     if (NodeIt(graph) == INVALID) return false;
    1404     Dfs<UndirGraph> dfs(graph);
    1405     dfs.init();
    1406     typename UndirGraph::template NodeMap<bool> red(graph);
    1407     for (NodeIt it(graph); it != INVALID; ++it) {
    1408       if (!dfs.reached(it)) {
    1409         dfs.addSource(it);
    1410         red[it] = true;
    1411         while (!dfs.emptyQueue()) {
    1412           Edge edge = dfs.nextEdge();
    1413           Node source = graph.source(edge);
    1414           Node target = graph.target(edge);
    1415           if (dfs.reached(target) && red[source] == red[target]) {
    1416             return false;
    1417           } else {
    1418             red[target] = !red[source];
    1419           }
    1420           dfs.processNextEdge();
    1421         }
    1422       }
     1443    typedef typename UndirGraph::EdgeIt EdgeIt;
     1444 
     1445    Bfs<UndirGraph> bfs(graph);
     1446    bfs.init();
     1447    for(NodeIt i(graph);i!=INVALID;++i){
     1448      if(!bfs.reached(i)){
     1449        bfs.addSource(i);
     1450        for(Node j=bfs.processNextNode();!bfs.emptyQueue();
     1451            j=bfs.processNextNode()){
     1452          partMap.set(j,bfs.dist(j)%2==0);
     1453        }
     1454      }
     1455    }
     1456    for(EdgeIt i(graph);i!=INVALID;++i){
     1457      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
    14231458    }
    14241459    return true;
    1425   }
     1460  };
    14261461   
    14271462} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.