Changeset 1284:ad40f7d32846 in lemon for lemon
- Timestamp:
- 08/11/13 15:28:12 (11 years ago)
- Branch:
- default
- Parents:
- 1266:70b199792735 (diff), 1260:a337a0dd3f75 (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
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r956 r1268 746 746 /// 747 747 /// This function checks whether the given undirected graph is 748 /// bi-node-connected, i.e. any two edges are on same circle. 748 /// bi-node-connected, i.e. a connected graph without articulation 749 /// node. 749 750 /// 750 751 /// \return \c true if the graph bi-node-connected. 751 /// \note By definition, the empty graph is bi-node-connected. 752 /// 753 /// \note By definition, 754 /// \li a graph consisting of zero or one node is bi-node-connected, 755 /// \li a graph consisting of two isolated nodes 756 /// is \e not bi-node-connected and 757 /// \li a graph consisting of two nodes connected by an edge 758 /// is bi-node-connected. 752 759 /// 753 760 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() 754 761 template <typename Graph> 755 762 bool biNodeConnected(const Graph& graph) { 763 bool hasNonIsolated = false, hasIsolated = false; 764 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 765 if (typename Graph::OutArcIt(graph, n) == INVALID) { 766 if (hasIsolated || hasNonIsolated) { 767 return false; 768 } else { 769 hasIsolated = true; 770 } 771 } else { 772 if (hasIsolated) { 773 return false; 774 } else { 775 hasNonIsolated = true; 776 } 777 } 778 } 756 779 return countBiNodeConnectedComponents(graph) <= 1; 757 780 } -
lemon/connectivity.h
r1266 r1268 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 259 259 /// \return \c true if the digraph is strongly connected. 260 260 /// \note By definition, the empty digraph is strongly connected. 261 /// 261 /// 262 262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() 263 263 /// \see connected() … … 311 311 /// \ingroup graph_properties 312 312 /// 313 /// \brief Count the number of strongly connected components of a 313 /// \brief Count the number of strongly connected components of a 314 314 /// directed graph 315 315 /// … … 782 782 /// \ingroup graph_properties 783 783 /// 784 /// \brief Count the number of bi-node-connected components of an 784 /// \brief Count the number of bi-node-connected components of an 785 785 /// undirected graph. 786 786 /// … … 836 836 /// \retval compMap A writable edge map. The values will be set from 0 837 837 /// to the number of the bi-node-connected components minus one. Each 838 /// value of the map will be set exactly once, and the values of a 838 /// value of the map will be set exactly once, and the values of a 839 839 /// certain component will be set continuously. 840 840 /// \return The number of bi-node-connected components. … … 882 882 /// 883 883 /// \param graph The undirected graph. 884 /// \retval cutMap A writable node map. The values will be set to 884 /// \retval cutMap A writable node map. The values will be set to 885 885 /// \c true for the nodes that separate two or more components 886 886 /// (exactly once for each cut node), and will not be changed for … … 1109 1109 /// \brief Check whether an undirected graph is bi-edge-connected. 1110 1110 /// 1111 /// This function checks whether the given undirected graph is 1111 /// This function checks whether the given undirected graph is 1112 1112 /// bi-edge-connected, i.e. any two nodes are connected with at least 1113 1113 /// two edge-disjoint paths. … … 1216 1216 /// 1217 1217 /// This function finds the bi-edge-connected cut edges in the given 1218 /// undirected graph. 1218 /// undirected graph. 1219 1219 /// 1220 1220 /// The bi-edge-connected components are the classes of an equivalence … … 1373 1373 /// \param digraph The digraph. 1374 1374 /// \retval order A readable and writable node map. The values will be 1375 /// set from 0 to the number of the nodes in the digraph minus one. 1375 /// set from 0 to the number of the nodes in the digraph minus one. 1376 1376 /// Each value of the map will be set exactly once, and the values will 1377 1377 /// be set descending order.
Note: See TracChangeset
for help on using the changeset viewer.