# Changeset 1267:bd24650d5cd2 in lemon

Ignore:
Timestamp:
08/09/13 14:01:24 (7 years ago)
Branch:
1.1
Parents:
1258:bdfc038f364c (diff), 1266:70b199792735 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge bugfix #439 to branch 1.1

Files:
4 edited

Unmodified
Removed
• ## lemon/connectivity.h

 r1081 /// /// This function checks whether the given undirected graph is /// bi-node-connected, i.e. any two edges are on same circle. /// bi-node-connected, i.e. a connected graph without articulation /// node. /// /// \return \c true if the graph bi-node-connected. /// \note By definition, the empty graph is bi-node-connected. /// /// \note By definition, /// \li a graph consisting of zero or one node is bi-node-connected, /// \li a graph consisting of two isolated nodes /// is \e not bi-node-connected and /// \li a graph consisting of two nodes connected by an edge /// is bi-node-connected. /// /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() template bool biNodeConnected(const Graph& graph) { bool hasNonIsolated = false, hasIsolated = false; for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { if (typename Graph::OutArcIt(graph, n) == INVALID) { if (hasIsolated || hasNonIsolated) { return false; } else { hasIsolated = true; } } else { if (hasIsolated) { return false; } else { hasNonIsolated = true; } } } return countBiNodeConnectedComponents(graph) <= 1; }
• ## lemon/connectivity.h

 r1266 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \return \c true if the digraph is strongly connected. /// \note By definition, the empty digraph is strongly connected. /// /// /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() /// \see connected() /// \ingroup graph_properties /// /// \brief Count the number of strongly connected components of a /// \brief Count the number of strongly connected components of a /// directed graph /// /// \ingroup graph_properties /// /// \brief Count the number of bi-node-connected components of an /// \brief Count the number of bi-node-connected components of an /// undirected graph. /// /// \retval compMap A writable edge map. The values will be set from 0 /// to the number of the bi-node-connected components minus one. Each /// value of the map will be set exactly once, and the values of a /// value of the map will be set exactly once, and the values of a /// certain component will be set continuously. /// \return The number of bi-node-connected components. /// /// \param graph The undirected graph. /// \retval cutMap A writable node map. The values will be set to /// \retval cutMap A writable node map. The values will be set to /// \c true for the nodes that separate two or more components /// (exactly once for each cut node), and will not be changed for /// \brief Check whether an undirected graph is bi-edge-connected. /// /// This function checks whether the given undirected graph is /// This function checks whether the given undirected graph is /// bi-edge-connected, i.e. any two nodes are connected with at least /// two edge-disjoint paths. /// /// This function finds the bi-edge-connected cut edges in the given /// undirected graph. /// undirected graph. /// /// The bi-edge-connected components are the classes of an equivalence /// \param digraph The digraph. /// \retval order A readable and writable node map. The values will be /// set from 0 to the number of the nodes in the digraph minus one. /// set from 0 to the number of the nodes in the digraph minus one. /// Each value of the map will be set exactly once, and the values will /// be set descending order.
• ## test/connectivity_test.cc

 r1258 check(simpleGraph(g), "This graph is simple."); } { ListGraph g; ListGraph::NodeMap map(g); ListGraph::Node n1 = g.addNode(); ListGraph::Node n2 = g.addNode(); ListGraph::Edge e1 = g.addEdge(n1, n2); ::lemon::ignore_unused_variable_warning(e1); check(biNodeConnected(g), "Graph is bi-node-connected"); ListGraph::Node n3 = g.addNode(); ::lemon::ignore_unused_variable_warning(n3); check(!biNodeConnected(g), "Graph is not bi-node-connected"); } {