COIN-OR::LEMON - Graph Library

Changeset 1091:9eac00ea588f in lemon-main


Ignore:
Timestamp:
08/09/13 14:07:27 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1088:4000b7ef4e01 (diff), 1090: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

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/connectivity.h

    r877 r1091  
    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

    r1090 r1091  
    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.
  • test/connectivity_test.cc

    r1084 r1091  
    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  {
  • test/connectivity_test.cc

    r1089 r1091  
    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).
     
    3030  typedef ListDigraph Digraph;
    3131  typedef Undirector<Digraph> Graph;
    32  
     32
    3333  {
    3434    Digraph d;
    3535    Digraph::NodeMap<int> order(d);
    3636    Graph g(d);
    37    
     37
    3838    check(stronglyConnected(d), "The empty digraph is strongly connected");
    3939    check(countStronglyConnectedComponents(d) == 0,
     
    4949    check(countBiEdgeConnectedComponents(g) == 0,
    5050          "The empty graph has 0 bi-edge-connected component");
    51          
     51
    5252    check(dag(d), "The empty digraph is DAG.");
    5353    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
     
    8484    check(countBiEdgeConnectedComponents(g) == 1,
    8585          "This graph has 1 bi-edge-connected component");
    86          
     86
    8787    check(dag(d), "This digraph is DAG.");
    8888    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
     
    120120    Digraph::NodeMap<int> order(d);
    121121    Graph g(d);
    122    
     122
    123123    Digraph::Node n1 = d.addNode();
    124124    Digraph::Node n2 = d.addNode();
     
    127127    Digraph::Node n5 = d.addNode();
    128128    Digraph::Node n6 = d.addNode();
    129    
     129
    130130    d.addArc(n1, n3);
    131131    d.addArc(n3, n2);
     
    155155    check(!parallelFree(g), "This graph is not parallel-free.");
    156156    check(!simpleGraph(g), "This graph is not simple.");
    157    
     157
    158158    d.addArc(n3, n3);
    159    
     159
    160160    check(!loopFree(d), "This digraph is not loop-free.");
    161161    check(!loopFree(g), "This graph is not loop-free.");
    162162    check(!simpleGraph(d), "This digraph is not simple.");
    163    
     163
    164164    d.addArc(n3, n2);
    165    
     165
    166166    check(!parallelFree(d), "This digraph is not parallel-free.");
    167167  }
    168  
     168
    169169  {
    170170    Digraph d;
    171171    Digraph::ArcMap<bool> cutarcs(d, false);
    172172    Graph g(d);
    173    
     173
    174174    Digraph::Node n1 = d.addNode();
    175175    Digraph::Node n2 = d.addNode();
     
    191191    d.addArc(n6, n7);
    192192    d.addArc(n7, n6);
    193    
     193
    194194    check(!stronglyConnected(d), "This digraph is not strongly connected");
    195195    check(countStronglyConnectedComponents(d) == 3,
     
    254254    Digraph d;
    255255    Digraph::NodeMap<int> order(d);
    256    
     256
    257257    Digraph::Node belt = d.addNode();
    258258    Digraph::Node trousers = d.addNode();
     
    275275    d.addArc(shirt, necktie);
    276276    d.addArc(necktie, coat);
    277    
     277
    278278    check(dag(d), "This digraph is DAG.");
    279279    topologicalSort(d, order);
     
    287287    ListGraph g;
    288288    ListGraph::NodeMap<bool> map(g);
    289    
     289
    290290    ListGraph::Node n1 = g.addNode();
    291291    ListGraph::Node n2 = g.addNode();
     
    303303    g.addEdge(n4, n7);
    304304    g.addEdge(n5, n7);
    305    
     305
    306306    check(bipartite(g), "This graph is bipartite");
    307307    check(bipartitePartitions(g, map), "This graph is bipartite");
    308    
     308
    309309    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
    310310          "Wrong bipartitePartitions()");
Note: See TracChangeset for help on using the changeset viewer.