COIN-OR::LEMON - Graph Library

Changeset 1268:19087d4f215d in lemon for lemon


Ignore:
Timestamp:
08/09/13 14:05:29 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.2
Parents:
1263:b9887ae63df0 (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.2

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r956 r1268  
    746746  ///
    747747  /// 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.
    749750  ///
    750751  /// \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.
    752759  ///
    753760  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
    754761  template <typename Graph>
    755762  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    }
    756779    return countBiNodeConnectedComponents(graph) <= 1;
    757780  }
  • lemon/connectivity.h

    r1266 r1268  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    259259  /// \return \c true if the digraph is strongly connected.
    260260  /// \note By definition, the empty digraph is strongly connected.
    261   /// 
     261  ///
    262262  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
    263263  /// \see connected()
     
    311311  /// \ingroup graph_properties
    312312  ///
    313   /// \brief Count the number of strongly connected components of a 
     313  /// \brief Count the number of strongly connected components of a
    314314  /// directed graph
    315315  ///
     
    782782  /// \ingroup graph_properties
    783783  ///
    784   /// \brief Count the number of bi-node-connected components of an 
     784  /// \brief Count the number of bi-node-connected components of an
    785785  /// undirected graph.
    786786  ///
     
    836836  /// \retval compMap A writable edge map. The values will be set from 0
    837837  /// 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
    839839  /// certain component will be set continuously.
    840840  /// \return The number of bi-node-connected components.
     
    882882  ///
    883883  /// \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
    885885  /// \c true for the nodes that separate two or more components
    886886  /// (exactly once for each cut node), and will not be changed for
     
    11091109  /// \brief Check whether an undirected graph is bi-edge-connected.
    11101110  ///
    1111   /// This function checks whether the given undirected graph is 
     1111  /// This function checks whether the given undirected graph is
    11121112  /// bi-edge-connected, i.e. any two nodes are connected with at least
    11131113  /// two edge-disjoint paths.
     
    12161216  ///
    12171217  /// This function finds the bi-edge-connected cut edges in the given
    1218   /// undirected graph. 
     1218  /// undirected graph.
    12191219  ///
    12201220  /// The bi-edge-connected components are the classes of an equivalence
     
    13731373  /// \param digraph The digraph.
    13741374  /// \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.
    13761376  /// Each value of the map will be set exactly once, and the values will
    13771377  /// be set descending order.
Note: See TracChangeset for help on using the changeset viewer.