1368 bool tree(const Graph& graph) { |
1368 bool tree(const Graph& graph) { |
1369 checkConcept<concepts::Graph, Graph>(); |
1369 checkConcept<concepts::Graph, Graph>(); |
1370 typedef typename Graph::Node Node; |
1370 typedef typename Graph::Node Node; |
1371 typedef typename Graph::NodeIt NodeIt; |
1371 typedef typename Graph::NodeIt NodeIt; |
1372 typedef typename Graph::Arc Arc; |
1372 typedef typename Graph::Arc Arc; |
|
1373 if (NodeIt(graph) == INVALID) return true; |
1373 Dfs<Graph> dfs(graph); |
1374 Dfs<Graph> dfs(graph); |
1374 dfs.init(); |
1375 dfs.init(); |
1375 dfs.addSource(NodeIt(graph)); |
1376 dfs.addSource(NodeIt(graph)); |
1376 while (!dfs.emptyQueue()) { |
1377 while (!dfs.emptyQueue()) { |
1377 Arc edge = dfs.nextArc(); |
1378 Arc edge = dfs.nextArc(); |
1543 } |
1544 } |
1544 |
1545 |
1545 /// \brief Returns true when there are not parallel edges in the graph. |
1546 /// \brief Returns true when there are not parallel edges in the graph. |
1546 /// |
1547 /// |
1547 /// Returns true when there are not parallel edges in the graph. |
1548 /// Returns true when there are not parallel edges in the graph. |
1548 template <typename Digraph> |
1549 template <typename Graph> |
1549 bool parallelFree(const Digraph& digraph) { |
1550 bool parallelFree(const Graph& graph) { |
1550 typename Digraph::template NodeMap<bool> reached(digraph, false); |
1551 typename Graph::template NodeMap<int> reached(graph, 0); |
1551 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { |
1552 int cnt = 1; |
1552 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { |
1553 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { |
1553 if (reached[digraph.target(a)]) return false; |
1554 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { |
1554 reached.set(digraph.target(a), true); |
1555 if (reached[graph.target(a)] == cnt) return false; |
1555 } |
1556 reached[graph.target(a)] = cnt; |
1556 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { |
1557 } |
1557 reached.set(digraph.target(a), false); |
1558 ++cnt; |
1558 } |
|
1559 } |
1559 } |
1560 return true; |
1560 return true; |
1561 } |
1561 } |
1562 |
1562 |
1563 /// \brief Returns true when there are not loop edges and parallel |
1563 /// \brief Returns true when there are not loop edges and parallel |
1564 /// edges in the graph. |
1564 /// edges in the graph. |
1565 /// |
1565 /// |
1566 /// Returns true when there are not loop edges and parallel edges in |
1566 /// Returns true when there are not loop edges and parallel edges in |
1567 /// the graph. |
1567 /// the graph. |
1568 template <typename Digraph> |
1568 template <typename Graph> |
1569 bool simpleDigraph(const Digraph& digraph) { |
1569 bool simpleGraph(const Graph& graph) { |
1570 typename Digraph::template NodeMap<bool> reached(digraph, false); |
1570 typename Graph::template NodeMap<int> reached(graph, 0); |
1571 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { |
1571 int cnt = 1; |
1572 reached.set(n, true); |
1572 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { |
1573 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { |
1573 reached[n] = cnt; |
1574 if (reached[digraph.target(a)]) return false; |
1574 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { |
1575 reached.set(digraph.target(a), true); |
1575 if (reached[graph.target(a)] == cnt) return false; |
1576 } |
1576 reached[graph.target(a)] = cnt; |
1577 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { |
1577 } |
1578 reached.set(digraph.target(a), false); |
1578 ++cnt; |
1579 } |
|
1580 reached.set(n, false); |
|
1581 } |
1579 } |
1582 return true; |
1580 return true; |
1583 } |
1581 } |
1584 |
1582 |
1585 } //namespace lemon |
1583 } //namespace lemon |