# HG changeset patch # User Alpar Juttner # Date 2009-05-07 13:19:41 # Node ID e2f99a47399864505dab1ea721acb866c5c006e2 # Parent 3adf5e2d1e62e87e255185722497c068d6fa93c0 # Parent 76cbcb3e9bbb2d7e8c2d873a401747965f84aadc Merge diff --git a/lemon/connectivity.h b/lemon/connectivity.h --- a/lemon/connectivity.h +++ b/lemon/connectivity.h @@ -42,12 +42,16 @@ /// \ingroup graph_properties /// - /// \brief Check whether the given undirected graph is connected. + /// \brief Check whether an undirected graph is connected. /// - /// Check whether the given undirected graph is connected. - /// \param graph The undirected graph. - /// \return \c true when there is path between any two nodes in the graph. + /// This function checks whether the given undirected graph is connected, + /// i.e. there is a path between any two nodes in the graph. + /// + /// \return \c true if the graph is connected. /// \note By definition, the empty graph is connected. + /// + /// \see countConnectedComponents(), connectedComponents() + /// \see stronglyConnected() template bool connected(const Graph& graph) { checkConcept(); @@ -67,12 +71,18 @@ /// /// \brief Count the number of connected components of an undirected graph /// - /// Count the number of connected components of an undirected graph + /// This function counts the number of connected components of the given + /// undirected graph. /// - /// \param graph The graph. It must be undirected. - /// \return The number of components + /// The connected components are the classes of an equivalence relation + /// on the nodes of an undirected graph. Two nodes are in the same class + /// if they are connected with a path. + /// + /// \return The number of connected components. /// \note By definition, the empty graph consists /// of zero connected components. + /// + /// \see connected(), connectedComponents() template int countConnectedComponents(const Graph &graph) { checkConcept(); @@ -109,17 +119,26 @@ /// /// \brief Find the connected components of an undirected graph /// - /// Find the connected components of an undirected graph. + /// This function finds the connected components of the given undirected + /// graph. + /// + /// The connected components are the classes of an equivalence relation + /// on the nodes of an undirected graph. Two nodes are in the same class + /// if they are connected with a path. /// /// \image html connected_components.png /// \image latex connected_components.eps "Connected components" width=\textwidth /// - /// \param graph The graph. It must be undirected. + /// \param graph The undirected graph. /// \retval compMap A writable node map. The values will be set from 0 to - /// the number of the connected components minus one. Each values of the map - /// will be set exactly once, the values of a certain component will be + /// the number of the connected components minus one. Each value of the map + /// will be set exactly once, and the values of a certain component will be /// set continuously. - /// \return The number of components + /// \return The number of connected components. + /// \note By definition, the empty graph consists + /// of zero connected components. + /// + /// \see connected(), countConnectedComponents() template int connectedComponents(const Graph &graph, NodeMap &compMap) { checkConcept(); @@ -231,15 +250,17 @@ /// \ingroup graph_properties /// - /// \brief Check whether the given directed graph is strongly connected. + /// \brief Check whether a directed graph is strongly connected. /// - /// Check whether the given directed graph is strongly connected. The - /// graph is strongly connected when any two nodes of the graph are + /// This function checks whether the given directed graph is strongly + /// connected, i.e. any two nodes of the digraph are /// connected with directed paths in both direction. - /// \return \c false when the graph is not strongly connected. - /// \see connected /// - /// \note By definition, the empty graph is strongly connected. + /// \return \c true if the digraph is strongly connected. + /// \note By definition, the empty digraph is strongly connected. + /// + /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() + /// \see connected() template bool stronglyConnected(const Digraph& digraph) { checkConcept(); @@ -270,7 +291,7 @@ typedef typename RDigraph::NodeIt RNodeIt; RDigraph rdigraph(digraph); - typedef DfsVisitor RVisitor; + typedef DfsVisitor RVisitor; RVisitor rvisitor; DfsVisit rdfs(rdigraph, rvisitor); @@ -289,18 +310,22 @@ /// \ingroup graph_properties /// - /// \brief Count the strongly connected components of a directed graph + /// \brief Count the number of strongly connected components of a + /// directed graph /// - /// Count the strongly connected components of a directed graph. + /// This function counts the number of strongly connected components of + /// the given directed graph. + /// /// The strongly connected components are the classes of an - /// equivalence relation on the nodes of the graph. Two nodes are in + /// equivalence relation on the nodes of a digraph. Two nodes are in /// the same class if they are connected with directed paths in both /// direction. /// - /// \param digraph The graph. - /// \return The number of components - /// \note By definition, the empty graph has zero + /// \return The number of strongly connected components. + /// \note By definition, the empty digraph has zero /// strongly connected components. + /// + /// \see stronglyConnected(), stronglyConnectedComponents() template int countStronglyConnectedComponents(const Digraph& digraph) { checkConcept(); @@ -355,13 +380,15 @@ /// /// \brief Find the strongly connected components of a directed graph /// - /// Find the strongly connected components of a directed graph. The - /// strongly connected components are the classes of an equivalence - /// relation on the nodes of the graph. Two nodes are in - /// relationship when there are directed paths between them in both - /// direction. In addition, the numbering of components will satisfy - /// that there is no arc going from a higher numbered component to - /// a lower. + /// This function finds the strongly connected components of the given + /// directed graph. In addition, the numbering of the components will + /// satisfy that there is no arc going from a higher numbered component + /// to a lower one (i.e. it provides a topological order of the components). + /// + /// The strongly connected components are the classes of an + /// equivalence relation on the nodes of a digraph. Two nodes are in + /// the same class if they are connected with directed paths in both + /// direction. /// /// \image html strongly_connected_components.png /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth @@ -369,9 +396,13 @@ /// \param digraph The digraph. /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the strongly connected components minus one. Each value - /// of the map will be set exactly once, the values of a certain component - /// will be set continuously. - /// \return The number of components + /// of the map will be set exactly once, and the values of a certain + /// component will be set continuously. + /// \return The number of strongly connected components. + /// \note By definition, the empty digraph has zero + /// strongly connected components. + /// + /// \see stronglyConnected(), countStronglyConnectedComponents() template int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { checkConcept(); @@ -424,19 +455,24 @@ /// /// \brief Find the cut arcs of the strongly connected components. /// - /// Find the cut arcs of the strongly connected components. - /// The strongly connected components are the classes of an equivalence - /// relation on the nodes of the graph. Two nodes are in relationship - /// when there are directed paths between them in both direction. + /// This function finds the cut arcs of the strongly connected components + /// of the given digraph. + /// + /// The strongly connected components are the classes of an + /// equivalence relation on the nodes of a digraph. Two nodes are in + /// the same class if they are connected with directed paths in both + /// direction. /// The strongly connected components are separated by the cut arcs. /// - /// \param graph The graph. - /// \retval cutMap A writable node map. The values will be set true when the - /// arc is a cut arc. + /// \param digraph The digraph. + /// \retval cutMap A writable arc map. The values will be set to \c true + /// for the cut arcs (exactly once for each cut arc), and will not be + /// changed for other arcs. + /// \return The number of cut arcs. /// - /// \return The number of cut arcs + /// \see stronglyConnected(), stronglyConnectedComponents() template - int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) { + int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) { checkConcept(); typedef typename Digraph::Node Node; typedef typename Digraph::Arc Arc; @@ -448,13 +484,13 @@ typedef std::vector Container; typedef typename Container::iterator Iterator; - Container nodes(countNodes(graph)); + Container nodes(countNodes(digraph)); typedef LeaveOrderVisitor Visitor; Visitor visitor(nodes.begin()); - DfsVisit dfs(graph, visitor); + DfsVisit dfs(digraph, visitor); dfs.init(); - for (NodeIt it(graph); it != INVALID; ++it) { + for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); @@ -464,14 +500,14 @@ typedef typename Container::reverse_iterator RIterator; typedef ReverseDigraph RDigraph; - RDigraph rgraph(graph); + RDigraph rdigraph(digraph); int cutNum = 0; typedef StronglyConnectedCutArcsVisitor RVisitor; - RVisitor rvisitor(rgraph, cutMap, cutNum); + RVisitor rvisitor(rdigraph, cutMap, cutNum); - DfsVisit rdfs(rgraph, rvisitor); + DfsVisit rdfs(rdigraph, rvisitor); rdfs.init(); for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { @@ -706,14 +742,15 @@ /// \ingroup graph_properties /// - /// \brief Checks the graph is bi-node-connected. + /// \brief Check whether an undirected graph is bi-node-connected. /// - /// This function checks that the undirected graph is bi-node-connected - /// graph. The graph is bi-node-connected if any two undirected edge is - /// on same circle. + /// This function checks whether the given undirected graph is + /// bi-node-connected, i.e. any two edges are on same circle. /// - /// \param graph The graph. - /// \return \c true when the graph bi-node-connected. + /// \return \c true if the graph bi-node-connected. + /// \note By definition, the empty graph is bi-node-connected. + /// + /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() template bool biNodeConnected(const Graph& graph) { return countBiNodeConnectedComponents(graph) <= 1; @@ -721,15 +758,19 @@ /// \ingroup graph_properties /// - /// \brief Count the biconnected components. + /// \brief Count the number of bi-node-connected components of an + /// undirected graph. /// - /// This function finds the bi-node-connected components in an undirected - /// graph. The biconnected components are the classes of an equivalence - /// relation on the undirected edges. Two undirected edge is in relationship - /// when they are on same circle. + /// This function counts the number of bi-node-connected components of + /// the given undirected graph. /// - /// \param graph The graph. - /// \return The number of components. + /// The bi-node-connected components are the classes of an equivalence + /// relation on the edges of a undirected graph. Two edges are in the + /// same class if they are on same circle. + /// + /// \return The number of bi-node-connected components. + /// + /// \see biNodeConnected(), biNodeConnectedComponents() template int countBiNodeConnectedComponents(const Graph& graph) { checkConcept(); @@ -756,22 +797,26 @@ /// \ingroup graph_properties /// - /// \brief Find the bi-node-connected components. + /// \brief Find the bi-node-connected components of an undirected graph. /// - /// This function finds the bi-node-connected components in an undirected - /// graph. The bi-node-connected components are the classes of an equivalence - /// relation on the undirected edges. Two undirected edge are in relationship - /// when they are on same circle. + /// This function finds the bi-node-connected components of the given + /// undirected graph. + /// + /// The bi-node-connected components are the classes of an equivalence + /// relation on the edges of a undirected graph. Two edges are in the + /// same class if they are on same circle. /// /// \image html node_biconnected_components.png /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth /// - /// \param graph The graph. - /// \retval compMap A writable uedge map. The values will be set from 0 - /// to the number of the biconnected components minus one. Each values - /// of the map will be set exactly once, the values of a certain component - /// will be set continuously. - /// \return The number of components. + /// \param graph The 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 + /// certain component will be set continuously. + /// \return The number of bi-node-connected components. + /// + /// \see biNodeConnected(), countBiNodeConnectedComponents() template int biNodeConnectedComponents(const Graph& graph, EdgeMap& compMap) { @@ -801,18 +846,25 @@ /// \ingroup graph_properties /// - /// \brief Find the bi-node-connected cut nodes. + /// \brief Find the bi-node-connected cut nodes in an undirected graph. /// - /// This function finds the bi-node-connected cut nodes in an undirected - /// graph. The bi-node-connected components are the classes of an equivalence - /// relation on the undirected edges. Two undirected edges are in - /// relationship when they are on same circle. The biconnected components - /// are separted by nodes which are the cut nodes of the components. + /// This function finds the bi-node-connected cut nodes in the given + /// undirected graph. /// - /// \param graph The graph. - /// \retval cutMap A writable edge map. The values will be set true when - /// the node separate two or more components. + /// The bi-node-connected components are the classes of an equivalence + /// relation on the edges of a undirected graph. Two edges are in the + /// same class if they are on same circle. + /// The bi-node-connected components are separted by the cut nodes of + /// the components. + /// + /// \param graph The undirected graph. + /// \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 + /// other nodes. /// \return The number of the cut nodes. + /// + /// \see biNodeConnected(), biNodeConnectedComponents() template int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { checkConcept(); @@ -1031,14 +1083,16 @@ /// \ingroup graph_properties /// - /// \brief Checks that the graph is bi-edge-connected. + /// \brief Check whether an undirected graph is bi-edge-connected. /// - /// This function checks that the graph is bi-edge-connected. The undirected - /// graph is bi-edge-connected when any two nodes are connected with two - /// edge-disjoint paths. + /// 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. /// - /// \param graph The undirected graph. - /// \return The number of components. + /// \return \c true if the graph is bi-edge-connected. + /// \note By definition, the empty graph is bi-edge-connected. + /// + /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() template bool biEdgeConnected(const Graph& graph) { return countBiEdgeConnectedComponents(graph) <= 1; @@ -1046,15 +1100,20 @@ /// \ingroup graph_properties /// - /// \brief Count the bi-edge-connected components. + /// \brief Count the number of bi-edge-connected components of an + /// undirected graph. /// - /// This function count the bi-edge-connected components in an undirected - /// graph. The bi-edge-connected components are the classes of an equivalence - /// relation on the nodes. Two nodes are in relationship when they are - /// connected with at least two edge-disjoint paths. + /// This function counts the number of bi-edge-connected components of + /// the given undirected graph. /// - /// \param graph The undirected graph. - /// \return The number of components. + /// The bi-edge-connected components are the classes of an equivalence + /// relation on the nodes of an undirected graph. Two nodes are in the + /// same class if they are connected with at least two edge-disjoint + /// paths. + /// + /// \return The number of bi-edge-connected components. + /// + /// \see biEdgeConnected(), biEdgeConnectedComponents() template int countBiEdgeConnectedComponents(const Graph& graph) { checkConcept(); @@ -1081,22 +1140,27 @@ /// \ingroup graph_properties /// - /// \brief Find the bi-edge-connected components. + /// \brief Find the bi-edge-connected components of an undirected graph. /// - /// This function finds the bi-edge-connected components in an undirected - /// graph. The bi-edge-connected components are the classes of an equivalence - /// relation on the nodes. Two nodes are in relationship when they are - /// connected at least two edge-disjoint paths. + /// This function finds the bi-edge-connected components of the given + /// undirected graph. + /// + /// The bi-edge-connected components are the classes of an equivalence + /// relation on the nodes of an undirected graph. Two nodes are in the + /// same class if they are connected with at least two edge-disjoint + /// paths. /// /// \image html edge_biconnected_components.png /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth /// - /// \param graph The graph. + /// \param graph The undirected graph. /// \retval compMap A writable node map. The values will be set from 0 to - /// the number of the biconnected components minus one. Each values - /// of the map will be set exactly once, the values of a certain component - /// will be set continuously. - /// \return The number of components. + /// the number of the bi-edge-connected components minus one. Each 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-edge-connected components. + /// + /// \see biEdgeConnected(), countBiEdgeConnectedComponents() template int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { checkConcept(); @@ -1125,19 +1189,25 @@ /// \ingroup graph_properties /// - /// \brief Find the bi-edge-connected cut edges. + /// \brief Find the bi-edge-connected cut edges in an undirected graph. /// - /// This function finds the bi-edge-connected components in an undirected - /// graph. The bi-edge-connected components are the classes of an equivalence - /// relation on the nodes. Two nodes are in relationship when they are - /// connected with at least two edge-disjoint paths. The bi-edge-connected - /// components are separted by edges which are the cut edges of the - /// components. + /// This function finds the bi-edge-connected cut edges in the given + /// undirected graph. /// - /// \param graph The graph. - /// \retval cutMap A writable node map. The values will be set true when the - /// edge is a cut edge. + /// The bi-edge-connected components are the classes of an equivalence + /// relation on the nodes of an undirected graph. Two nodes are in the + /// same class if they are connected with at least two edge-disjoint + /// paths. + /// The bi-edge-connected components are separted by the cut edges of + /// the components. + /// + /// \param graph The undirected graph. + /// \retval cutMap A writable edge map. The values will be set to \c true + /// for the cut edges (exactly once for each cut edge), and will not be + /// changed for other edges. /// \return The number of cut edges. + /// + /// \see biEdgeConnected(), biEdgeConnectedComponents() template int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { checkConcept(); @@ -1189,19 +1259,62 @@ /// \ingroup graph_properties /// + /// \brief Check whether a digraph is DAG. + /// + /// This function checks whether the given digraph is DAG, i.e. + /// \e Directed \e Acyclic \e Graph. + /// \return \c true if there is no directed cycle in the digraph. + /// \see acyclic() + template + bool dag(const Digraph& digraph) { + + checkConcept(); + + typedef typename Digraph::Node Node; + typedef typename Digraph::NodeIt NodeIt; + typedef typename Digraph::Arc Arc; + + typedef typename Digraph::template NodeMap ProcessedMap; + + typename Dfs::template SetProcessedMap:: + Create dfs(digraph); + + ProcessedMap processed(digraph); + dfs.processedMap(processed); + + dfs.init(); + for (NodeIt it(digraph); it != INVALID; ++it) { + if (!dfs.reached(it)) { + dfs.addSource(it); + while (!dfs.emptyQueue()) { + Arc arc = dfs.nextArc(); + Node target = digraph.target(arc); + if (dfs.reached(target) && !processed[target]) { + return false; + } + dfs.processNextArc(); + } + } + } + return true; + } + + /// \ingroup graph_properties + /// /// \brief Sort the nodes of a DAG into topolgical order. /// - /// Sort the nodes of a DAG into topolgical order. + /// This function sorts the nodes of the given acyclic digraph (DAG) + /// into topolgical order. /// - /// \param graph The graph. It must be directed and acyclic. + /// \param digraph The digraph, which must be DAG. /// \retval order A writable node map. The values will be set from 0 to - /// the number of the nodes in the graph minus one. Each values of the map - /// will be set exactly once, the values will be set descending order. + /// 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. /// - /// \see checkedTopologicalSort - /// \see dag + /// \see dag(), checkedTopologicalSort() template - void topologicalSort(const Digraph& graph, NodeMap& order) { + void topologicalSort(const Digraph& digraph, NodeMap& order) { using namespace _connectivity_bits; checkConcept(); @@ -1212,13 +1325,13 @@ typedef typename Digraph::Arc Arc; TopologicalSortVisitor - visitor(order, countNodes(graph)); + visitor(order, countNodes(digraph)); DfsVisit > - dfs(graph, visitor); + dfs(digraph, visitor); dfs.init(); - for (NodeIt it(graph); it != INVALID; ++it) { + for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); dfs.start(); @@ -1230,18 +1343,18 @@ /// /// \brief Sort the nodes of a DAG into topolgical order. /// - /// Sort the nodes of a DAG into topolgical order. It also checks - /// that the given graph is DAG. + /// This function sorts the nodes of the given acyclic digraph (DAG) + /// into topolgical order and also checks whether the given digraph + /// is DAG. /// - /// \param digraph The graph. It must be directed and acyclic. - /// \retval order A readable - writable node map. The values will be set - /// from 0 to the number of the nodes in the graph minus one. Each values - /// of the map will be set exactly once, the values will be set descending - /// order. - /// \return \c false when the graph is not DAG. + /// \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. + /// Each value of the map will be set exactly once, and the values will + /// be set descending order. + /// \return \c false if the digraph is not DAG. /// - /// \see topologicalSort - /// \see dag + /// \see dag(), topologicalSort() template bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { using namespace _connectivity_bits; @@ -1283,54 +1396,11 @@ /// \ingroup graph_properties /// - /// \brief Check that the given directed graph is a DAG. + /// \brief Check whether an undirected graph is acyclic. /// - /// Check that the given directed graph is a DAG. The DAG is - /// an Directed Acyclic Digraph. - /// \return \c false when the graph is not DAG. - /// \see acyclic - template - bool dag(const Digraph& digraph) { - - checkConcept(); - - typedef typename Digraph::Node Node; - typedef typename Digraph::NodeIt NodeIt; - typedef typename Digraph::Arc Arc; - - typedef typename Digraph::template NodeMap ProcessedMap; - - typename Dfs::template SetProcessedMap:: - Create dfs(digraph); - - ProcessedMap processed(digraph); - dfs.processedMap(processed); - - dfs.init(); - for (NodeIt it(digraph); it != INVALID; ++it) { - if (!dfs.reached(it)) { - dfs.addSource(it); - while (!dfs.emptyQueue()) { - Arc edge = dfs.nextArc(); - Node target = digraph.target(edge); - if (dfs.reached(target) && !processed[target]) { - return false; - } - dfs.processNextArc(); - } - } - } - return true; - } - - /// \ingroup graph_properties - /// - /// \brief Check that the given undirected graph is acyclic. - /// - /// Check that the given undirected graph acyclic. - /// \param graph The undirected graph. - /// \return \c true when there is no circle in the graph. - /// \see dag + /// This function checks whether the given undirected graph is acyclic. + /// \return \c true if there is no cycle in the graph. + /// \see dag() template bool acyclic(const Graph& graph) { checkConcept(); @@ -1343,11 +1413,11 @@ if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { - Arc edge = dfs.nextArc(); - Node source = graph.source(edge); - Node target = graph.target(edge); + Arc arc = dfs.nextArc(); + Node source = graph.source(arc); + Node target = graph.target(arc); if (dfs.reached(target) && - dfs.predArc(source) != graph.oppositeArc(edge)) { + dfs.predArc(source) != graph.oppositeArc(arc)) { return false; } dfs.processNextArc(); @@ -1359,26 +1429,27 @@ /// \ingroup graph_properties /// - /// \brief Check that the given undirected graph is tree. + /// \brief Check whether an undirected graph is tree. /// - /// Check that the given undirected graph is tree. - /// \param graph The undirected graph. - /// \return \c true when the graph is acyclic and connected. + /// This function checks whether the given undirected graph is tree. + /// \return \c true if the graph is acyclic and connected. + /// \see acyclic(), connected() template bool tree(const Graph& graph) { checkConcept(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Arc Arc; + if (NodeIt(graph) == INVALID) return true; Dfs dfs(graph); dfs.init(); dfs.addSource(NodeIt(graph)); while (!dfs.emptyQueue()) { - Arc edge = dfs.nextArc(); - Node source = graph.source(edge); - Node target = graph.target(edge); + Arc arc = dfs.nextArc(); + Node source = graph.source(arc); + Node target = graph.target(arc); if (dfs.reached(target) && - dfs.predArc(source) != graph.oppositeArc(edge)) { + dfs.predArc(source) != graph.oppositeArc(arc)) { return false; } dfs.processNextArc(); @@ -1451,15 +1522,14 @@ /// \ingroup graph_properties /// - /// \brief Check if the given undirected graph is bipartite or not + /// \brief Check whether an undirected graph is bipartite. /// - /// The function checks if the given undirected \c graph graph is bipartite - /// or not. The \ref Bfs algorithm is used to calculate the result. - /// \param graph The undirected graph. - /// \return \c true if \c graph is bipartite, \c false otherwise. - /// \sa bipartitePartitions + /// The function checks whether the given undirected graph is bipartite. + /// \return \c true if the graph is bipartite. + /// + /// \see bipartitePartitions() template - inline bool bipartite(const Graph &graph){ + bool bipartite(const Graph &graph){ using namespace _connectivity_bits; checkConcept(); @@ -1488,25 +1558,27 @@ /// \ingroup graph_properties /// - /// \brief Check if the given undirected graph is bipartite or not + /// \brief Find the bipartite partitions of an undirected graph. /// - /// The function checks if the given undirected graph is bipartite - /// or not. The \ref Bfs algorithm is used to calculate the result. - /// During the execution, the \c partMap will be set as the two - /// partitions of the graph. + /// This function checks whether the given undirected graph is bipartite + /// and gives back the bipartite partitions. /// /// \image html bipartite_partitions.png /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth /// /// \param graph The undirected graph. - /// \retval partMap A writable bool map of nodes. It will be set as the - /// two partitions of the graph. - /// \return \c true if \c graph is bipartite, \c false otherwise. + /// \retval partMap A writable node map of \c bool (or convertible) value + /// type. The values will be set to \c true for one component and + /// \c false for the other one. + /// \return \c true if the graph is bipartite, \c false otherwise. + /// + /// \see bipartite() template - inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ + bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ using namespace _connectivity_bits; checkConcept(); + checkConcept, NodeMap>(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; @@ -1531,53 +1603,59 @@ return true; } - /// \brief Returns true when there are not loop edges in the graph. + /// \ingroup graph_properties /// - /// Returns true when there are not loop edges in the graph. - template - bool loopFree(const Digraph& digraph) { - for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { - if (digraph.source(it) == digraph.target(it)) return false; + /// \brief Check whether the given graph contains no loop arcs/edges. + /// + /// This function returns \c true if there are no loop arcs/edges in + /// the given graph. It works for both directed and undirected graphs. + template + bool loopFree(const Graph& graph) { + for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { + if (graph.source(it) == graph.target(it)) return false; } return true; } - /// \brief Returns true when there are not parallel edges in the graph. + /// \ingroup graph_properties /// - /// Returns true when there are not parallel edges in the graph. - template - bool parallelFree(const Digraph& digraph) { - typename Digraph::template NodeMap reached(digraph, false); - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { - if (reached[digraph.target(a)]) return false; - reached.set(digraph.target(a), true); + /// \brief Check whether the given graph contains no parallel arcs/edges. + /// + /// This function returns \c true if there are no parallel arcs/edges in + /// the given graph. It works for both directed and undirected graphs. + template + bool parallelFree(const Graph& graph) { + typename Graph::template NodeMap reached(graph, 0); + int cnt = 1; + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { + if (reached[graph.target(a)] == cnt) return false; + reached[graph.target(a)] = cnt; } - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { - reached.set(digraph.target(a), false); - } + ++cnt; } return true; } - /// \brief Returns true when there are not loop edges and parallel - /// edges in the graph. + /// \ingroup graph_properties /// - /// Returns true when there are not loop edges and parallel edges in - /// the graph. - template - bool simpleDigraph(const Digraph& digraph) { - typename Digraph::template NodeMap reached(digraph, false); - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { - reached.set(n, true); - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { - if (reached[digraph.target(a)]) return false; - reached.set(digraph.target(a), true); + /// \brief Check whether the given graph is simple. + /// + /// This function returns \c true if the given graph is simple, i.e. + /// it contains no loop arcs/edges and no parallel arcs/edges. + /// The function works for both directed and undirected graphs. + /// \see loopFree(), parallelFree() + template + bool simpleGraph(const Graph& graph) { + typename Graph::template NodeMap reached(graph, 0); + int cnt = 1; + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { + reached[n] = cnt; + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { + if (reached[graph.target(a)] == cnt) return false; + reached[graph.target(a)] = cnt; } - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { - reached.set(digraph.target(a), false); - } - reached.set(n, false); + ++cnt; } return true; } diff --git a/lemon/euler.h b/lemon/euler.h --- a/lemon/euler.h +++ b/lemon/euler.h @@ -244,10 +244,10 @@ }; - ///Check if the given graph is \e Eulerian + ///Check if the given graph is Eulerian /// \ingroup graph_properties - ///This function checks if the given graph is \e Eulerian. + ///This function checks if the given graph is Eulerian. ///It works for both directed and undirected graphs. /// ///By definition, a digraph is called \e Eulerian if diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -9,6 +9,7 @@ adaptors_test bfs_test circulation_test + connectivity_test counter_test dfs_test digraph_test diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -9,6 +9,7 @@ test/adaptors_test \ test/bfs_test \ test/circulation_test \ + test/connectivity_test \ test/counter_test \ test/dfs_test \ test/digraph_test \ @@ -54,6 +55,7 @@ test_bfs_test_SOURCES = test/bfs_test.cc test_circulation_test_SOURCES = test/circulation_test.cc test_counter_test_SOURCES = test/counter_test.cc +test_connectivity_test_SOURCES = test/connectivity_test.cc test_dfs_test_SOURCES = test/dfs_test.cc test_digraph_test_SOURCES = test/digraph_test.cc test_dijkstra_test_SOURCES = test/dijkstra_test.cc diff --git a/test/connectivity_test.cc b/test/connectivity_test.cc new file mode 100644 --- /dev/null +++ b/test/connectivity_test.cc @@ -0,0 +1,297 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +#include +#include + +#include "test_tools.h" + +using namespace lemon; + + +int main() +{ + 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, + "The empty digraph has 0 strongly connected component"); + check(connected(g), "The empty graph is connected"); + check(countConnectedComponents(g) == 0, + "The empty graph has 0 connected component"); + + check(biNodeConnected(g), "The empty graph is bi-node-connected"); + check(countBiNodeConnectedComponents(g) == 0, + "The empty graph has 0 bi-node-connected component"); + check(biEdgeConnected(g), "The empty graph is bi-edge-connected"); + 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(loopFree(d), "The empty digraph is loop-free."); + check(parallelFree(d), "The empty digraph is parallel-free."); + check(simpleGraph(d), "The empty digraph is simple."); + + check(acyclic(g), "The empty graph is acyclic."); + check(tree(g), "The empty graph is tree."); + check(bipartite(g), "The empty graph is bipartite."); + check(loopFree(g), "The empty graph is loop-free."); + check(parallelFree(g), "The empty graph is parallel-free."); + check(simpleGraph(g), "The empty graph is simple."); + } + + { + Digraph d; + Digraph::NodeMap order(d); + Graph g(d); + Digraph::Node n = d.addNode(); + + check(stronglyConnected(d), "This digraph is strongly connected"); + check(countStronglyConnectedComponents(d) == 1, + "This digraph has 1 strongly connected component"); + check(connected(g), "This graph is connected"); + check(countConnectedComponents(g) == 1, + "This graph has 1 connected component"); + + check(biNodeConnected(g), "This graph is bi-node-connected"); + check(countBiNodeConnectedComponents(g) == 0, + "This graph has 0 bi-node-connected component"); + check(biEdgeConnected(g), "This graph is bi-edge-connected"); + 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."); + check(loopFree(d), "This digraph is loop-free."); + check(parallelFree(d), "This digraph is parallel-free."); + check(simpleGraph(d), "This digraph is simple."); + + check(acyclic(g), "This graph is acyclic."); + check(tree(g), "This graph is tree."); + check(bipartite(g), "This graph is bipartite."); + check(loopFree(g), "This graph is loop-free."); + check(parallelFree(g), "This graph is parallel-free."); + check(simpleGraph(g), "This graph is simple."); + } + + { + Digraph d; + Digraph::NodeMap order(d); + Graph g(d); + + Digraph::Node n1 = d.addNode(); + Digraph::Node n2 = d.addNode(); + Digraph::Node n3 = d.addNode(); + Digraph::Node n4 = d.addNode(); + Digraph::Node n5 = d.addNode(); + Digraph::Node n6 = d.addNode(); + + d.addArc(n1, n3); + d.addArc(n3, n2); + d.addArc(n2, n1); + d.addArc(n4, n2); + d.addArc(n4, n3); + d.addArc(n5, n6); + d.addArc(n6, n5); + + check(!stronglyConnected(d), "This digraph is not strongly connected"); + check(countStronglyConnectedComponents(d) == 3, + "This digraph has 3 strongly connected components"); + check(!connected(g), "This graph is not connected"); + check(countConnectedComponents(g) == 2, + "This graph has 2 connected components"); + + check(!dag(d), "This digraph is not DAG."); + check(!checkedTopologicalSort(d, order), "This digraph is not DAG."); + check(loopFree(d), "This digraph is loop-free."); + check(parallelFree(d), "This digraph is parallel-free."); + check(simpleGraph(d), "This digraph is simple."); + + check(!acyclic(g), "This graph is not acyclic."); + check(!tree(g), "This graph is not tree."); + check(!bipartite(g), "This graph is not bipartite."); + check(loopFree(g), "This graph is loop-free."); + 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(); + Digraph::Node n3 = d.addNode(); + Digraph::Node n4 = d.addNode(); + Digraph::Node n5 = d.addNode(); + Digraph::Node n6 = d.addNode(); + Digraph::Node n7 = d.addNode(); + Digraph::Node n8 = d.addNode(); + + d.addArc(n1, n2); + d.addArc(n5, n1); + d.addArc(n2, n8); + d.addArc(n8, n5); + d.addArc(n6, n4); + d.addArc(n4, n6); + d.addArc(n2, n5); + d.addArc(n1, n8); + d.addArc(n6, n7); + d.addArc(n7, n6); + + check(!stronglyConnected(d), "This digraph is not strongly connected"); + check(countStronglyConnectedComponents(d) == 3, + "This digraph has 3 strongly connected components"); + Digraph::NodeMap scomp1(d); + check(stronglyConnectedComponents(d, scomp1) == 3, + "This digraph has 3 strongly connected components"); + check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] && + scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()"); + check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] && + scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()"); + check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7], + "Wrong stronglyConnectedComponents()"); + Digraph::ArcMap scut1(d, false); + check(stronglyConnectedCutArcs(d, scut1) == 0, + "This digraph has 0 strongly connected cut arc."); + for (Digraph::ArcIt a(d); a != INVALID; ++a) { + check(!scut1[a], "Wrong stronglyConnectedCutArcs()"); + } + + check(!connected(g), "This graph is not connected"); + check(countConnectedComponents(g) == 3, + "This graph has 3 connected components"); + Graph::NodeMap comp(g); + check(connectedComponents(g, comp) == 3, + "This graph has 3 connected components"); + check(comp[n1] != comp[n3] && comp[n1] != comp[n4] && + comp[n3] != comp[n4], "Wrong connectedComponents()"); + check(comp[n1] == comp[n2] && comp[n1] == comp[n5] && + comp[n1] == comp[n8], "Wrong connectedComponents()"); + check(comp[n4] == comp[n6] && comp[n4] == comp[n7], + "Wrong connectedComponents()"); + + cutarcs[d.addArc(n3, n1)] = true; + cutarcs[d.addArc(n3, n5)] = true; + cutarcs[d.addArc(n3, n8)] = true; + cutarcs[d.addArc(n8, n6)] = true; + cutarcs[d.addArc(n8, n7)] = true; + + check(!stronglyConnected(d), "This digraph is not strongly connected"); + check(countStronglyConnectedComponents(d) == 3, + "This digraph has 3 strongly connected components"); + Digraph::NodeMap scomp2(d); + check(stronglyConnectedComponents(d, scomp2) == 3, + "This digraph has 3 strongly connected components"); + check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()"); + check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 && + scomp2[n8] == 1, "Wrong stronglyConnectedComponents()"); + check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2, + "Wrong stronglyConnectedComponents()"); + Digraph::ArcMap scut2(d, false); + check(stronglyConnectedCutArcs(d, scut2) == 5, + "This digraph has 5 strongly connected cut arcs."); + for (Digraph::ArcIt a(d); a != INVALID; ++a) { + check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()"); + } + } + + { + // DAG example for topological sort from the book New Algorithms + // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein) + Digraph d; + Digraph::NodeMap order(d); + + Digraph::Node belt = d.addNode(); + Digraph::Node trousers = d.addNode(); + Digraph::Node necktie = d.addNode(); + Digraph::Node coat = d.addNode(); + Digraph::Node socks = d.addNode(); + Digraph::Node shirt = d.addNode(); + Digraph::Node shoe = d.addNode(); + Digraph::Node watch = d.addNode(); + Digraph::Node pants = d.addNode(); + + d.addArc(socks, shoe); + d.addArc(pants, shoe); + d.addArc(pants, trousers); + d.addArc(trousers, shoe); + d.addArc(trousers, belt); + d.addArc(belt, coat); + d.addArc(shirt, belt); + d.addArc(shirt, necktie); + d.addArc(necktie, coat); + + check(dag(d), "This digraph is DAG."); + topologicalSort(d, order); + for (Digraph::ArcIt a(d); a != INVALID; ++a) { + check(order[d.source(a)] < order[d.target(a)], + "Wrong topologicalSort()"); + } + } + + { + ListGraph g; + ListGraph::NodeMap map(g); + + ListGraph::Node n1 = g.addNode(); + ListGraph::Node n2 = g.addNode(); + ListGraph::Node n3 = g.addNode(); + ListGraph::Node n4 = g.addNode(); + ListGraph::Node n5 = g.addNode(); + ListGraph::Node n6 = g.addNode(); + ListGraph::Node n7 = g.addNode(); + + g.addEdge(n1, n3); + g.addEdge(n1, n4); + g.addEdge(n2, n5); + g.addEdge(n3, n6); + g.addEdge(n4, n6); + 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()"); + check(map[n3] == map[n4] && map[n3] == map[n5], + "Wrong bipartitePartitions()"); + } + + return 0; +}