COIN-OR::LEMON - Graph Library

Changeset 647:dcba640438c7 in lemon-main


Ignore:
Timestamp:
05/06/09 14:37:44 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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().
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r586 r647  
    13711371    typedef typename Graph::NodeIt NodeIt;
    13721372    typedef typename Graph::Arc Arc;
     1373    if (NodeIt(graph) == INVALID) return true;
    13731374    Dfs<Graph> dfs(graph);
    13741375    dfs.init();
     
    15461547  ///
    15471548  /// 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;
    15591559    }
    15601560    return true;
     
    15661566  /// Returns true when there are not loop edges and parallel edges in
    15671567  /// 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;
    15811579    }
    15821580    return true;
Note: See TracChangeset for help on using the changeset viewer.