# Changeset 988:19087d4f215d in lemon-1.2

Ignore:
Timestamp:
08/09/13 14:05:29 (6 years ago)
Branch:
1.2
Parents:
985:b9887ae63df0 (diff), 987: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:
4 edited

Unmodified
Added
Removed
• ## lemon/connectivity.h

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

 r987 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * 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

 r983 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"); } {
• ## test/connectivity_test.cc

 r986 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). typedef ListDigraph Digraph; typedef Undirector Graph; { Digraph d; Digraph::NodeMap order(d); Graph g(d); check(stronglyConnected(d), "The empty digraph is strongly connected"); check(countStronglyConnectedComponents(d) == 0, check(countBiEdgeConnectedComponents(g) == 0, "The empty graph has 0 bi-edge-connected component"); check(dag(d), "The empty digraph is DAG."); check(checkedTopologicalSort(d, order), "The empty digraph is DAG."); check(countBiEdgeConnectedComponents(g) == 1, "This graph has 1 bi-edge-connected component"); check(dag(d), "This digraph is DAG."); check(checkedTopologicalSort(d, order), "This digraph is DAG."); Digraph::NodeMap order(d); Graph g(d); Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); Digraph::Node n5 = d.addNode(); Digraph::Node n6 = d.addNode(); d.addArc(n1, n3); d.addArc(n3, n2); check(!parallelFree(g), "This graph is not parallel-free."); check(!simpleGraph(g), "This graph is not simple."); d.addArc(n3, n3); check(!loopFree(d), "This digraph is not loop-free."); check(!loopFree(g), "This graph is not loop-free."); check(!simpleGraph(d), "This digraph is not simple."); d.addArc(n3, n2); check(!parallelFree(d), "This digraph is not parallel-free."); } { Digraph d; Digraph::ArcMap cutarcs(d, false); Graph g(d); Digraph::Node n1 = d.addNode(); Digraph::Node n2 = d.addNode(); d.addArc(n6, n7); d.addArc(n7, n6); check(!stronglyConnected(d), "This digraph is not strongly connected"); check(countStronglyConnectedComponents(d) == 3, Digraph d; Digraph::NodeMap order(d); Digraph::Node belt = d.addNode(); Digraph::Node trousers = d.addNode(); d.addArc(shirt, necktie); d.addArc(necktie, coat); check(dag(d), "This digraph is DAG."); topologicalSort(d, order); ListGraph g; ListGraph::NodeMap map(g); ListGraph::Node n1 = g.addNode(); ListGraph::Node n2 = g.addNode(); g.addEdge(n4, n7); g.addEdge(n5, n7); check(bipartite(g), "This graph is bipartite"); check(bipartitePartitions(g, map), "This graph is bipartite"); check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], "Wrong bipartitePartitions()");
Note: See TracChangeset for help on using the changeset viewer.