COIN-OR::LEMON - Graph Library

Changeset 1089:552e3d1242c6 in lemon-main


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

Fix biNodeConnected() function (#439)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r648 r1089  
    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  }
  • test/connectivity_test.cc

    r1083 r1089  
    9898    check(simpleGraph(g), "This graph is simple.");
    9999  }
     100
     101  {
     102    ListGraph g;
     103    ListGraph::NodeMap<bool> map(g);
     104
     105    ListGraph::Node n1 = g.addNode();
     106    ListGraph::Node n2 = g.addNode();
     107
     108    ListGraph::Edge e1 = g.addEdge(n1, n2);
     109    ::lemon::ignore_unused_variable_warning(e1);
     110    check(biNodeConnected(g), "Graph is bi-node-connected");
     111
     112    ListGraph::Node n3 = g.addNode();
     113    ::lemon::ignore_unused_variable_warning(n3);
     114    check(!biNodeConnected(g), "Graph is not bi-node-connected");
     115  }
     116
    100117
    101118  {
Note: See TracChangeset for help on using the changeset viewer.