1387 } |
1387 } |
1388 } |
1388 } |
1389 return true; |
1389 return true; |
1390 } |
1390 } |
1391 |
1391 |
|
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 |
1392 /// \ingroup topology |
1450 /// \ingroup topology |
1393 /// |
1451 /// |
1394 /// \brief Check if the given undirected graph is bipartite or not |
1452 /// \brief Check if the given undirected graph is bipartite or not |
1395 /// |
1453 /// |
1396 /// The function checks if the given undirected \c graph graph is bipartite |
1454 /// The function checks if the given undirected \c graph graph is bipartite |
1400 /// \sa bipartitePartitions |
1458 /// \sa bipartitePartitions |
1401 /// |
1459 /// |
1402 /// \author Balazs Attila Mihaly |
1460 /// \author Balazs Attila Mihaly |
1403 template<typename UGraph> |
1461 template<typename UGraph> |
1404 inline bool bipartite(const UGraph &graph){ |
1462 inline bool bipartite(const UGraph &graph){ |
|
1463 using namespace _topology_bits; |
|
1464 |
1405 checkConcept<concepts::UGraph, UGraph>(); |
1465 checkConcept<concepts::UGraph, UGraph>(); |
1406 |
1466 |
1407 typedef typename UGraph::NodeIt NodeIt; |
1467 typedef typename UGraph::NodeIt NodeIt; |
1408 typedef typename UGraph::EdgeIt EdgeIt; |
1468 typedef typename UGraph::EdgeIt EdgeIt; |
1409 |
1469 |
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); |
1411 bfs.init(); |
1476 bfs.init(); |
1412 for(NodeIt i(graph);i!=INVALID;++i){ |
1477 for(NodeIt it(graph); it != INVALID; ++it) { |
1413 if(!bfs.reached(i)){ |
1478 if(!bfs.reached(it)){ |
1414 bfs.run(i); |
1479 bfs.addSource(it); |
1415 } |
1480 while (!bfs.emptyQueue()) { |
1416 } |
1481 bfs.processNextNode(); |
1417 for(EdgeIt i(graph);i!=INVALID;++i){ |
1482 if (!bipartite) return false; |
1418 if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false; |
1483 } |
|
1484 } |
1419 } |
1485 } |
1420 return true; |
1486 return true; |
1421 } |
1487 } |
1422 |
1488 |
1423 /// \ingroup topology |
1489 /// \ingroup topology |
1437 /// |
1503 /// |
1438 /// \image html bipartite_partitions.png |
1504 /// \image html bipartite_partitions.png |
1439 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
1505 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
1440 template<typename UGraph, typename NodeMap> |
1506 template<typename UGraph, typename NodeMap> |
1441 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ |
1507 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ |
|
1508 using namespace _topology_bits; |
|
1509 |
1442 checkConcept<concepts::UGraph, UGraph>(); |
1510 checkConcept<concepts::UGraph, UGraph>(); |
1443 |
1511 |
1444 typedef typename UGraph::Node Node; |
1512 typedef typename UGraph::Node Node; |
1445 typedef typename UGraph::NodeIt NodeIt; |
1513 typedef typename UGraph::NodeIt NodeIt; |
1446 typedef typename UGraph::EdgeIt EdgeIt; |
1514 typedef typename UGraph::EdgeIt EdgeIt; |
1447 |
1515 |
1448 Bfs<UGraph> bfs(graph); |
1516 bool bipartite = true; |
|
1517 |
|
1518 BipartitePartitionsVisitor<UGraph, NodeMap> |
|
1519 visitor(graph, partMap, bipartite); |
|
1520 BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> > |
|
1521 bfs(graph, visitor); |
1449 bfs.init(); |
1522 bfs.init(); |
1450 for(NodeIt i(graph);i!=INVALID;++i){ |
1523 for(NodeIt it(graph); it != INVALID; ++it) { |
1451 if(!bfs.reached(i)){ |
1524 if(!bfs.reached(it)){ |
1452 bfs.addSource(i); |
1525 bfs.addSource(it); |
1453 for(Node j=bfs.processNextNode();!bfs.emptyQueue(); |
1526 while (!bfs.emptyQueue()) { |
1454 j=bfs.processNextNode()){ |
1527 bfs.processNextNode(); |
1455 partMap.set(j,bfs.dist(j)%2==0); |
1528 if (!bipartite) return false; |
1456 } |
1529 } |
1457 } |
1530 } |
1458 } |
1531 } |
1459 for(EdgeIt i(graph);i!=INVALID;++i){ |
1532 return true; |
1460 if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false; |
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); |
1461 } |
1582 } |
1462 return true; |
1583 return true; |
1463 } |
1584 } |
1464 |
1585 |
1465 } //namespace lemon |
1586 } //namespace lemon |