Changeset - r694:dcba640438c7
« 693:e01957
695:4ff804 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Bug fixes in connectivity.h (#285) - Bug fix in tree(). - Rename simpleDigraph() to simpleGraph() (it works for both directed and undirected graphs). - Possibly faster implementation for parallelFree() and simpleGraph().
0 1 0
default
1 file changed with 20 insertions and 22 deletions:
lemon/connectivity.h
20
22
↑ Collapse diff ↑
lemon/connectivity.h
Ignore white space 6 line context
... ... 
@@ -1370,6 +1370,7 @@
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));
... ... 
@@ -1545,17 +1546,16 @@
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 
        reached.set(digraph.target(a), true);
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 
  }
... ... 
@@ -1565,19 +1565,17 @@
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 
  }
0 comments (0 inline)