Changeset 694:dcba640438c7 in lemon
- Timestamp:
- 05/06/09 14:37:44 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r633 r694 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(); … … 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 reached.set(digraph.target(a), true); 1555 } 1556 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1557 reached.set(digraph.target(a), false); 1558 } 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; 1557 } 1558 ++cnt; 1559 1559 } 1560 1560 return true; … … 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); 1576 } 1577 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1578 reached.set(digraph.target(a), false); 1579 } 1580 reached.set(n, false); 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; 1577 } 1578 ++cnt; 1581 1579 } 1582 1580 return true;
Note: See TracChangeset
for help on using the changeset viewer.