COIN-OR::LEMON - Graph Library

Changeset 1265:552e3d1242c6 in lemon for lemon


Ignore:
Timestamp:
08/08/13 22:56:10 (7 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Fix biNodeConnected() function (#439)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r695 r1265  
    745745  /// \brief Check whether an undirected graph is bi-node-connected.
    746746  ///
    747   /// This function checks whether the given undirected graph is
    748   /// bi-node-connected, i.e. any two edges are on same circle.
     747  /// This function checks whether the given undirected graph is
     748  /// bi-node-connected, i.e. a connected graph without articulation
     749  /// node.
    749750  ///
    750751  /// \return \c true if the graph bi-node-connected.
     
    754755  template <typename Graph>
    755756  bool biNodeConnected(const Graph& graph) {
     757    bool hasNonIsolated = false, hasIsolated = false;
     758    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     759      if (typename Graph::OutArcIt(graph, n) == INVALID) {
     760        if (hasIsolated || hasNonIsolated) {
     761          return false;
     762        } else {
     763          hasIsolated = true;
     764        }
     765      } else {
     766        if (hasIsolated) {
     767          return false;
     768        } else {
     769          hasNonIsolated = true;
     770        }
     771      }
     772    }
    756773    return countBiNodeConnectedComponents(graph) <= 1;
    757774  }
Note: See TracChangeset for help on using the changeset viewer.