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