COIN-OR::LEMON - Graph Library

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


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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.