1.1 --- a/lemon/connectivity.h Thu May 07 02:07:59 2009 +0200
1.2 +++ b/lemon/connectivity.h Thu May 07 12:19:41 2009 +0100
1.3 @@ -42,12 +42,16 @@
1.4
1.5 /// \ingroup graph_properties
1.6 ///
1.7 - /// \brief Check whether the given undirected graph is connected.
1.8 + /// \brief Check whether an undirected graph is connected.
1.9 ///
1.10 - /// Check whether the given undirected graph is connected.
1.11 - /// \param graph The undirected graph.
1.12 - /// \return \c true when there is path between any two nodes in the graph.
1.13 + /// This function checks whether the given undirected graph is connected,
1.14 + /// i.e. there is a path between any two nodes in the graph.
1.15 + ///
1.16 + /// \return \c true if the graph is connected.
1.17 /// \note By definition, the empty graph is connected.
1.18 + ///
1.19 + /// \see countConnectedComponents(), connectedComponents()
1.20 + /// \see stronglyConnected()
1.21 template <typename Graph>
1.22 bool connected(const Graph& graph) {
1.23 checkConcept<concepts::Graph, Graph>();
1.24 @@ -67,12 +71,18 @@
1.25 ///
1.26 /// \brief Count the number of connected components of an undirected graph
1.27 ///
1.28 - /// Count the number of connected components of an undirected graph
1.29 + /// This function counts the number of connected components of the given
1.30 + /// undirected graph.
1.31 ///
1.32 - /// \param graph The graph. It must be undirected.
1.33 - /// \return The number of components
1.34 + /// The connected components are the classes of an equivalence relation
1.35 + /// on the nodes of an undirected graph. Two nodes are in the same class
1.36 + /// if they are connected with a path.
1.37 + ///
1.38 + /// \return The number of connected components.
1.39 /// \note By definition, the empty graph consists
1.40 /// of zero connected components.
1.41 + ///
1.42 + /// \see connected(), connectedComponents()
1.43 template <typename Graph>
1.44 int countConnectedComponents(const Graph &graph) {
1.45 checkConcept<concepts::Graph, Graph>();
1.46 @@ -109,17 +119,26 @@
1.47 ///
1.48 /// \brief Find the connected components of an undirected graph
1.49 ///
1.50 - /// Find the connected components of an undirected graph.
1.51 + /// This function finds the connected components of the given undirected
1.52 + /// graph.
1.53 + ///
1.54 + /// The connected components are the classes of an equivalence relation
1.55 + /// on the nodes of an undirected graph. Two nodes are in the same class
1.56 + /// if they are connected with a path.
1.57 ///
1.58 /// \image html connected_components.png
1.59 /// \image latex connected_components.eps "Connected components" width=\textwidth
1.60 ///
1.61 - /// \param graph The graph. It must be undirected.
1.62 + /// \param graph The undirected graph.
1.63 /// \retval compMap A writable node map. The values will be set from 0 to
1.64 - /// the number of the connected components minus one. Each values of the map
1.65 - /// will be set exactly once, the values of a certain component will be
1.66 + /// the number of the connected components minus one. Each value of the map
1.67 + /// will be set exactly once, and the values of a certain component will be
1.68 /// set continuously.
1.69 - /// \return The number of components
1.70 + /// \return The number of connected components.
1.71 + /// \note By definition, the empty graph consists
1.72 + /// of zero connected components.
1.73 + ///
1.74 + /// \see connected(), countConnectedComponents()
1.75 template <class Graph, class NodeMap>
1.76 int connectedComponents(const Graph &graph, NodeMap &compMap) {
1.77 checkConcept<concepts::Graph, Graph>();
1.78 @@ -231,15 +250,17 @@
1.79
1.80 /// \ingroup graph_properties
1.81 ///
1.82 - /// \brief Check whether the given directed graph is strongly connected.
1.83 + /// \brief Check whether a directed graph is strongly connected.
1.84 ///
1.85 - /// Check whether the given directed graph is strongly connected. The
1.86 - /// graph is strongly connected when any two nodes of the graph are
1.87 + /// This function checks whether the given directed graph is strongly
1.88 + /// connected, i.e. any two nodes of the digraph are
1.89 /// connected with directed paths in both direction.
1.90 - /// \return \c false when the graph is not strongly connected.
1.91 - /// \see connected
1.92 ///
1.93 - /// \note By definition, the empty graph is strongly connected.
1.94 + /// \return \c true if the digraph is strongly connected.
1.95 + /// \note By definition, the empty digraph is strongly connected.
1.96 + ///
1.97 + /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
1.98 + /// \see connected()
1.99 template <typename Digraph>
1.100 bool stronglyConnected(const Digraph& digraph) {
1.101 checkConcept<concepts::Digraph, Digraph>();
1.102 @@ -270,7 +291,7 @@
1.103 typedef typename RDigraph::NodeIt RNodeIt;
1.104 RDigraph rdigraph(digraph);
1.105
1.106 - typedef DfsVisitor<Digraph> RVisitor;
1.107 + typedef DfsVisitor<RDigraph> RVisitor;
1.108 RVisitor rvisitor;
1.109
1.110 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.111 @@ -289,18 +310,22 @@
1.112
1.113 /// \ingroup graph_properties
1.114 ///
1.115 - /// \brief Count the strongly connected components of a directed graph
1.116 + /// \brief Count the number of strongly connected components of a
1.117 + /// directed graph
1.118 ///
1.119 - /// Count the strongly connected components of a directed graph.
1.120 + /// This function counts the number of strongly connected components of
1.121 + /// the given directed graph.
1.122 + ///
1.123 /// The strongly connected components are the classes of an
1.124 - /// equivalence relation on the nodes of the graph. Two nodes are in
1.125 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.126 /// the same class if they are connected with directed paths in both
1.127 /// direction.
1.128 ///
1.129 - /// \param digraph The graph.
1.130 - /// \return The number of components
1.131 - /// \note By definition, the empty graph has zero
1.132 + /// \return The number of strongly connected components.
1.133 + /// \note By definition, the empty digraph has zero
1.134 /// strongly connected components.
1.135 + ///
1.136 + /// \see stronglyConnected(), stronglyConnectedComponents()
1.137 template <typename Digraph>
1.138 int countStronglyConnectedComponents(const Digraph& digraph) {
1.139 checkConcept<concepts::Digraph, Digraph>();
1.140 @@ -355,13 +380,15 @@
1.141 ///
1.142 /// \brief Find the strongly connected components of a directed graph
1.143 ///
1.144 - /// Find the strongly connected components of a directed graph. The
1.145 - /// strongly connected components are the classes of an equivalence
1.146 - /// relation on the nodes of the graph. Two nodes are in
1.147 - /// relationship when there are directed paths between them in both
1.148 - /// direction. In addition, the numbering of components will satisfy
1.149 - /// that there is no arc going from a higher numbered component to
1.150 - /// a lower.
1.151 + /// This function finds the strongly connected components of the given
1.152 + /// directed graph. In addition, the numbering of the components will
1.153 + /// satisfy that there is no arc going from a higher numbered component
1.154 + /// to a lower one (i.e. it provides a topological order of the components).
1.155 + ///
1.156 + /// The strongly connected components are the classes of an
1.157 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.158 + /// the same class if they are connected with directed paths in both
1.159 + /// direction.
1.160 ///
1.161 /// \image html strongly_connected_components.png
1.162 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
1.163 @@ -369,9 +396,13 @@
1.164 /// \param digraph The digraph.
1.165 /// \retval compMap A writable node map. The values will be set from 0 to
1.166 /// the number of the strongly connected components minus one. Each value
1.167 - /// of the map will be set exactly once, the values of a certain component
1.168 - /// will be set continuously.
1.169 - /// \return The number of components
1.170 + /// of the map will be set exactly once, and the values of a certain
1.171 + /// component will be set continuously.
1.172 + /// \return The number of strongly connected components.
1.173 + /// \note By definition, the empty digraph has zero
1.174 + /// strongly connected components.
1.175 + ///
1.176 + /// \see stronglyConnected(), countStronglyConnectedComponents()
1.177 template <typename Digraph, typename NodeMap>
1.178 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
1.179 checkConcept<concepts::Digraph, Digraph>();
1.180 @@ -424,19 +455,24 @@
1.181 ///
1.182 /// \brief Find the cut arcs of the strongly connected components.
1.183 ///
1.184 - /// Find the cut arcs of the strongly connected components.
1.185 - /// The strongly connected components are the classes of an equivalence
1.186 - /// relation on the nodes of the graph. Two nodes are in relationship
1.187 - /// when there are directed paths between them in both direction.
1.188 + /// This function finds the cut arcs of the strongly connected components
1.189 + /// of the given digraph.
1.190 + ///
1.191 + /// The strongly connected components are the classes of an
1.192 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.193 + /// the same class if they are connected with directed paths in both
1.194 + /// direction.
1.195 /// The strongly connected components are separated by the cut arcs.
1.196 ///
1.197 - /// \param graph The graph.
1.198 - /// \retval cutMap A writable node map. The values will be set true when the
1.199 - /// arc is a cut arc.
1.200 + /// \param digraph The digraph.
1.201 + /// \retval cutMap A writable arc map. The values will be set to \c true
1.202 + /// for the cut arcs (exactly once for each cut arc), and will not be
1.203 + /// changed for other arcs.
1.204 + /// \return The number of cut arcs.
1.205 ///
1.206 - /// \return The number of cut arcs
1.207 + /// \see stronglyConnected(), stronglyConnectedComponents()
1.208 template <typename Digraph, typename ArcMap>
1.209 - int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
1.210 + int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
1.211 checkConcept<concepts::Digraph, Digraph>();
1.212 typedef typename Digraph::Node Node;
1.213 typedef typename Digraph::Arc Arc;
1.214 @@ -448,13 +484,13 @@
1.215 typedef std::vector<Node> Container;
1.216 typedef typename Container::iterator Iterator;
1.217
1.218 - Container nodes(countNodes(graph));
1.219 + Container nodes(countNodes(digraph));
1.220 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
1.221 Visitor visitor(nodes.begin());
1.222
1.223 - DfsVisit<Digraph, Visitor> dfs(graph, visitor);
1.224 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.225 dfs.init();
1.226 - for (NodeIt it(graph); it != INVALID; ++it) {
1.227 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.228 if (!dfs.reached(it)) {
1.229 dfs.addSource(it);
1.230 dfs.start();
1.231 @@ -464,14 +500,14 @@
1.232 typedef typename Container::reverse_iterator RIterator;
1.233 typedef ReverseDigraph<const Digraph> RDigraph;
1.234
1.235 - RDigraph rgraph(graph);
1.236 + RDigraph rdigraph(digraph);
1.237
1.238 int cutNum = 0;
1.239
1.240 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
1.241 - RVisitor rvisitor(rgraph, cutMap, cutNum);
1.242 + RVisitor rvisitor(rdigraph, cutMap, cutNum);
1.243
1.244 - DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
1.245 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.246
1.247 rdfs.init();
1.248 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.249 @@ -706,14 +742,15 @@
1.250
1.251 /// \ingroup graph_properties
1.252 ///
1.253 - /// \brief Checks the graph is bi-node-connected.
1.254 + /// \brief Check whether an undirected graph is bi-node-connected.
1.255 ///
1.256 - /// This function checks that the undirected graph is bi-node-connected
1.257 - /// graph. The graph is bi-node-connected if any two undirected edge is
1.258 - /// on same circle.
1.259 + /// This function checks whether the given undirected graph is
1.260 + /// bi-node-connected, i.e. any two edges are on same circle.
1.261 ///
1.262 - /// \param graph The graph.
1.263 - /// \return \c true when the graph bi-node-connected.
1.264 + /// \return \c true if the graph bi-node-connected.
1.265 + /// \note By definition, the empty graph is bi-node-connected.
1.266 + ///
1.267 + /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
1.268 template <typename Graph>
1.269 bool biNodeConnected(const Graph& graph) {
1.270 return countBiNodeConnectedComponents(graph) <= 1;
1.271 @@ -721,15 +758,19 @@
1.272
1.273 /// \ingroup graph_properties
1.274 ///
1.275 - /// \brief Count the biconnected components.
1.276 + /// \brief Count the number of bi-node-connected components of an
1.277 + /// undirected graph.
1.278 ///
1.279 - /// This function finds the bi-node-connected components in an undirected
1.280 - /// graph. The biconnected components are the classes of an equivalence
1.281 - /// relation on the undirected edges. Two undirected edge is in relationship
1.282 - /// when they are on same circle.
1.283 + /// This function counts the number of bi-node-connected components of
1.284 + /// the given undirected graph.
1.285 ///
1.286 - /// \param graph The graph.
1.287 - /// \return The number of components.
1.288 + /// The bi-node-connected components are the classes of an equivalence
1.289 + /// relation on the edges of a undirected graph. Two edges are in the
1.290 + /// same class if they are on same circle.
1.291 + ///
1.292 + /// \return The number of bi-node-connected components.
1.293 + ///
1.294 + /// \see biNodeConnected(), biNodeConnectedComponents()
1.295 template <typename Graph>
1.296 int countBiNodeConnectedComponents(const Graph& graph) {
1.297 checkConcept<concepts::Graph, Graph>();
1.298 @@ -756,22 +797,26 @@
1.299
1.300 /// \ingroup graph_properties
1.301 ///
1.302 - /// \brief Find the bi-node-connected components.
1.303 + /// \brief Find the bi-node-connected components of an undirected graph.
1.304 ///
1.305 - /// This function finds the bi-node-connected components in an undirected
1.306 - /// graph. The bi-node-connected components are the classes of an equivalence
1.307 - /// relation on the undirected edges. Two undirected edge are in relationship
1.308 - /// when they are on same circle.
1.309 + /// This function finds the bi-node-connected components of the given
1.310 + /// undirected graph.
1.311 + ///
1.312 + /// The bi-node-connected components are the classes of an equivalence
1.313 + /// relation on the edges of a undirected graph. Two edges are in the
1.314 + /// same class if they are on same circle.
1.315 ///
1.316 /// \image html node_biconnected_components.png
1.317 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
1.318 ///
1.319 - /// \param graph The graph.
1.320 - /// \retval compMap A writable uedge map. The values will be set from 0
1.321 - /// to the number of the biconnected components minus one. Each values
1.322 - /// of the map will be set exactly once, the values of a certain component
1.323 - /// will be set continuously.
1.324 - /// \return The number of components.
1.325 + /// \param graph The undirected graph.
1.326 + /// \retval compMap A writable edge map. The values will be set from 0
1.327 + /// to the number of the bi-node-connected components minus one. Each
1.328 + /// value of the map will be set exactly once, and the values of a
1.329 + /// certain component will be set continuously.
1.330 + /// \return The number of bi-node-connected components.
1.331 + ///
1.332 + /// \see biNodeConnected(), countBiNodeConnectedComponents()
1.333 template <typename Graph, typename EdgeMap>
1.334 int biNodeConnectedComponents(const Graph& graph,
1.335 EdgeMap& compMap) {
1.336 @@ -801,18 +846,25 @@
1.337
1.338 /// \ingroup graph_properties
1.339 ///
1.340 - /// \brief Find the bi-node-connected cut nodes.
1.341 + /// \brief Find the bi-node-connected cut nodes in an undirected graph.
1.342 ///
1.343 - /// This function finds the bi-node-connected cut nodes in an undirected
1.344 - /// graph. The bi-node-connected components are the classes of an equivalence
1.345 - /// relation on the undirected edges. Two undirected edges are in
1.346 - /// relationship when they are on same circle. The biconnected components
1.347 - /// are separted by nodes which are the cut nodes of the components.
1.348 + /// This function finds the bi-node-connected cut nodes in the given
1.349 + /// undirected graph.
1.350 ///
1.351 - /// \param graph The graph.
1.352 - /// \retval cutMap A writable edge map. The values will be set true when
1.353 - /// the node separate two or more components.
1.354 + /// The bi-node-connected components are the classes of an equivalence
1.355 + /// relation on the edges of a undirected graph. Two edges are in the
1.356 + /// same class if they are on same circle.
1.357 + /// The bi-node-connected components are separted by the cut nodes of
1.358 + /// the components.
1.359 + ///
1.360 + /// \param graph The undirected graph.
1.361 + /// \retval cutMap A writable node map. The values will be set to
1.362 + /// \c true for the nodes that separate two or more components
1.363 + /// (exactly once for each cut node), and will not be changed for
1.364 + /// other nodes.
1.365 /// \return The number of the cut nodes.
1.366 + ///
1.367 + /// \see biNodeConnected(), biNodeConnectedComponents()
1.368 template <typename Graph, typename NodeMap>
1.369 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
1.370 checkConcept<concepts::Graph, Graph>();
1.371 @@ -1031,14 +1083,16 @@
1.372
1.373 /// \ingroup graph_properties
1.374 ///
1.375 - /// \brief Checks that the graph is bi-edge-connected.
1.376 + /// \brief Check whether an undirected graph is bi-edge-connected.
1.377 ///
1.378 - /// This function checks that the graph is bi-edge-connected. The undirected
1.379 - /// graph is bi-edge-connected when any two nodes are connected with two
1.380 - /// edge-disjoint paths.
1.381 + /// This function checks whether the given undirected graph is
1.382 + /// bi-edge-connected, i.e. any two nodes are connected with at least
1.383 + /// two edge-disjoint paths.
1.384 ///
1.385 - /// \param graph The undirected graph.
1.386 - /// \return The number of components.
1.387 + /// \return \c true if the graph is bi-edge-connected.
1.388 + /// \note By definition, the empty graph is bi-edge-connected.
1.389 + ///
1.390 + /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
1.391 template <typename Graph>
1.392 bool biEdgeConnected(const Graph& graph) {
1.393 return countBiEdgeConnectedComponents(graph) <= 1;
1.394 @@ -1046,15 +1100,20 @@
1.395
1.396 /// \ingroup graph_properties
1.397 ///
1.398 - /// \brief Count the bi-edge-connected components.
1.399 + /// \brief Count the number of bi-edge-connected components of an
1.400 + /// undirected graph.
1.401 ///
1.402 - /// This function count the bi-edge-connected components in an undirected
1.403 - /// graph. The bi-edge-connected components are the classes of an equivalence
1.404 - /// relation on the nodes. Two nodes are in relationship when they are
1.405 - /// connected with at least two edge-disjoint paths.
1.406 + /// This function counts the number of bi-edge-connected components of
1.407 + /// the given undirected graph.
1.408 ///
1.409 - /// \param graph The undirected graph.
1.410 - /// \return The number of components.
1.411 + /// The bi-edge-connected components are the classes of an equivalence
1.412 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.413 + /// same class if they are connected with at least two edge-disjoint
1.414 + /// paths.
1.415 + ///
1.416 + /// \return The number of bi-edge-connected components.
1.417 + ///
1.418 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.419 template <typename Graph>
1.420 int countBiEdgeConnectedComponents(const Graph& graph) {
1.421 checkConcept<concepts::Graph, Graph>();
1.422 @@ -1081,22 +1140,27 @@
1.423
1.424 /// \ingroup graph_properties
1.425 ///
1.426 - /// \brief Find the bi-edge-connected components.
1.427 + /// \brief Find the bi-edge-connected components of an undirected graph.
1.428 ///
1.429 - /// This function finds the bi-edge-connected components in an undirected
1.430 - /// graph. The bi-edge-connected components are the classes of an equivalence
1.431 - /// relation on the nodes. Two nodes are in relationship when they are
1.432 - /// connected at least two edge-disjoint paths.
1.433 + /// This function finds the bi-edge-connected components of the given
1.434 + /// undirected graph.
1.435 + ///
1.436 + /// The bi-edge-connected components are the classes of an equivalence
1.437 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.438 + /// same class if they are connected with at least two edge-disjoint
1.439 + /// paths.
1.440 ///
1.441 /// \image html edge_biconnected_components.png
1.442 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.443 ///
1.444 - /// \param graph The graph.
1.445 + /// \param graph The undirected graph.
1.446 /// \retval compMap A writable node map. The values will be set from 0 to
1.447 - /// the number of the biconnected components minus one. Each values
1.448 - /// of the map will be set exactly once, the values of a certain component
1.449 - /// will be set continuously.
1.450 - /// \return The number of components.
1.451 + /// the number of the bi-edge-connected components minus one. Each value
1.452 + /// of the map will be set exactly once, and the values of a certain
1.453 + /// component will be set continuously.
1.454 + /// \return The number of bi-edge-connected components.
1.455 + ///
1.456 + /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
1.457 template <typename Graph, typename NodeMap>
1.458 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1.459 checkConcept<concepts::Graph, Graph>();
1.460 @@ -1125,19 +1189,25 @@
1.461
1.462 /// \ingroup graph_properties
1.463 ///
1.464 - /// \brief Find the bi-edge-connected cut edges.
1.465 + /// \brief Find the bi-edge-connected cut edges in an undirected graph.
1.466 ///
1.467 - /// This function finds the bi-edge-connected components in an undirected
1.468 - /// graph. The bi-edge-connected components are the classes of an equivalence
1.469 - /// relation on the nodes. Two nodes are in relationship when they are
1.470 - /// connected with at least two edge-disjoint paths. The bi-edge-connected
1.471 - /// components are separted by edges which are the cut edges of the
1.472 - /// components.
1.473 + /// This function finds the bi-edge-connected cut edges in the given
1.474 + /// undirected graph.
1.475 ///
1.476 - /// \param graph The graph.
1.477 - /// \retval cutMap A writable node map. The values will be set true when the
1.478 - /// edge is a cut edge.
1.479 + /// The bi-edge-connected components are the classes of an equivalence
1.480 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.481 + /// same class if they are connected with at least two edge-disjoint
1.482 + /// paths.
1.483 + /// The bi-edge-connected components are separted by the cut edges of
1.484 + /// the components.
1.485 + ///
1.486 + /// \param graph The undirected graph.
1.487 + /// \retval cutMap A writable edge map. The values will be set to \c true
1.488 + /// for the cut edges (exactly once for each cut edge), and will not be
1.489 + /// changed for other edges.
1.490 /// \return The number of cut edges.
1.491 + ///
1.492 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.493 template <typename Graph, typename EdgeMap>
1.494 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1.495 checkConcept<concepts::Graph, Graph>();
1.496 @@ -1189,19 +1259,62 @@
1.497
1.498 /// \ingroup graph_properties
1.499 ///
1.500 + /// \brief Check whether a digraph is DAG.
1.501 + ///
1.502 + /// This function checks whether the given digraph is DAG, i.e.
1.503 + /// \e Directed \e Acyclic \e Graph.
1.504 + /// \return \c true if there is no directed cycle in the digraph.
1.505 + /// \see acyclic()
1.506 + template <typename Digraph>
1.507 + bool dag(const Digraph& digraph) {
1.508 +
1.509 + checkConcept<concepts::Digraph, Digraph>();
1.510 +
1.511 + typedef typename Digraph::Node Node;
1.512 + typedef typename Digraph::NodeIt NodeIt;
1.513 + typedef typename Digraph::Arc Arc;
1.514 +
1.515 + typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.516 +
1.517 + typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.518 + Create dfs(digraph);
1.519 +
1.520 + ProcessedMap processed(digraph);
1.521 + dfs.processedMap(processed);
1.522 +
1.523 + dfs.init();
1.524 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.525 + if (!dfs.reached(it)) {
1.526 + dfs.addSource(it);
1.527 + while (!dfs.emptyQueue()) {
1.528 + Arc arc = dfs.nextArc();
1.529 + Node target = digraph.target(arc);
1.530 + if (dfs.reached(target) && !processed[target]) {
1.531 + return false;
1.532 + }
1.533 + dfs.processNextArc();
1.534 + }
1.535 + }
1.536 + }
1.537 + return true;
1.538 + }
1.539 +
1.540 + /// \ingroup graph_properties
1.541 + ///
1.542 /// \brief Sort the nodes of a DAG into topolgical order.
1.543 ///
1.544 - /// Sort the nodes of a DAG into topolgical order.
1.545 + /// This function sorts the nodes of the given acyclic digraph (DAG)
1.546 + /// into topolgical order.
1.547 ///
1.548 - /// \param graph The graph. It must be directed and acyclic.
1.549 + /// \param digraph The digraph, which must be DAG.
1.550 /// \retval order A writable node map. The values will be set from 0 to
1.551 - /// the number of the nodes in the graph minus one. Each values of the map
1.552 - /// will be set exactly once, the values will be set descending order.
1.553 + /// the number of the nodes in the digraph minus one. Each value of the
1.554 + /// map will be set exactly once, and the values will be set descending
1.555 + /// order.
1.556 ///
1.557 - /// \see checkedTopologicalSort
1.558 - /// \see dag
1.559 + /// \see dag(), checkedTopologicalSort()
1.560 template <typename Digraph, typename NodeMap>
1.561 - void topologicalSort(const Digraph& graph, NodeMap& order) {
1.562 + void topologicalSort(const Digraph& digraph, NodeMap& order) {
1.563 using namespace _connectivity_bits;
1.564
1.565 checkConcept<concepts::Digraph, Digraph>();
1.566 @@ -1212,13 +1325,13 @@
1.567 typedef typename Digraph::Arc Arc;
1.568
1.569 TopologicalSortVisitor<Digraph, NodeMap>
1.570 - visitor(order, countNodes(graph));
1.571 + visitor(order, countNodes(digraph));
1.572
1.573 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1.574 - dfs(graph, visitor);
1.575 + dfs(digraph, visitor);
1.576
1.577 dfs.init();
1.578 - for (NodeIt it(graph); it != INVALID; ++it) {
1.579 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.580 if (!dfs.reached(it)) {
1.581 dfs.addSource(it);
1.582 dfs.start();
1.583 @@ -1230,18 +1343,18 @@
1.584 ///
1.585 /// \brief Sort the nodes of a DAG into topolgical order.
1.586 ///
1.587 - /// Sort the nodes of a DAG into topolgical order. It also checks
1.588 - /// that the given graph is DAG.
1.589 + /// This function sorts the nodes of the given acyclic digraph (DAG)
1.590 + /// into topolgical order and also checks whether the given digraph
1.591 + /// is DAG.
1.592 ///
1.593 - /// \param digraph The graph. It must be directed and acyclic.
1.594 - /// \retval order A readable - writable node map. The values will be set
1.595 - /// from 0 to the number of the nodes in the graph minus one. Each values
1.596 - /// of the map will be set exactly once, the values will be set descending
1.597 - /// order.
1.598 - /// \return \c false when the graph is not DAG.
1.599 + /// \param digraph The digraph.
1.600 + /// \retval order A readable and writable node map. The values will be
1.601 + /// set from 0 to the number of the nodes in the digraph minus one.
1.602 + /// Each value of the map will be set exactly once, and the values will
1.603 + /// be set descending order.
1.604 + /// \return \c false if the digraph is not DAG.
1.605 ///
1.606 - /// \see topologicalSort
1.607 - /// \see dag
1.608 + /// \see dag(), topologicalSort()
1.609 template <typename Digraph, typename NodeMap>
1.610 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1.611 using namespace _connectivity_bits;
1.612 @@ -1283,54 +1396,11 @@
1.613
1.614 /// \ingroup graph_properties
1.615 ///
1.616 - /// \brief Check that the given directed graph is a DAG.
1.617 + /// \brief Check whether an undirected graph is acyclic.
1.618 ///
1.619 - /// Check that the given directed graph is a DAG. The DAG is
1.620 - /// an Directed Acyclic Digraph.
1.621 - /// \return \c false when the graph is not DAG.
1.622 - /// \see acyclic
1.623 - template <typename Digraph>
1.624 - bool dag(const Digraph& digraph) {
1.625 -
1.626 - checkConcept<concepts::Digraph, Digraph>();
1.627 -
1.628 - typedef typename Digraph::Node Node;
1.629 - typedef typename Digraph::NodeIt NodeIt;
1.630 - typedef typename Digraph::Arc Arc;
1.631 -
1.632 - typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.633 -
1.634 - typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.635 - Create dfs(digraph);
1.636 -
1.637 - ProcessedMap processed(digraph);
1.638 - dfs.processedMap(processed);
1.639 -
1.640 - dfs.init();
1.641 - for (NodeIt it(digraph); it != INVALID; ++it) {
1.642 - if (!dfs.reached(it)) {
1.643 - dfs.addSource(it);
1.644 - while (!dfs.emptyQueue()) {
1.645 - Arc edge = dfs.nextArc();
1.646 - Node target = digraph.target(edge);
1.647 - if (dfs.reached(target) && !processed[target]) {
1.648 - return false;
1.649 - }
1.650 - dfs.processNextArc();
1.651 - }
1.652 - }
1.653 - }
1.654 - return true;
1.655 - }
1.656 -
1.657 - /// \ingroup graph_properties
1.658 - ///
1.659 - /// \brief Check that the given undirected graph is acyclic.
1.660 - ///
1.661 - /// Check that the given undirected graph acyclic.
1.662 - /// \param graph The undirected graph.
1.663 - /// \return \c true when there is no circle in the graph.
1.664 - /// \see dag
1.665 + /// This function checks whether the given undirected graph is acyclic.
1.666 + /// \return \c true if there is no cycle in the graph.
1.667 + /// \see dag()
1.668 template <typename Graph>
1.669 bool acyclic(const Graph& graph) {
1.670 checkConcept<concepts::Graph, Graph>();
1.671 @@ -1343,11 +1413,11 @@
1.672 if (!dfs.reached(it)) {
1.673 dfs.addSource(it);
1.674 while (!dfs.emptyQueue()) {
1.675 - Arc edge = dfs.nextArc();
1.676 - Node source = graph.source(edge);
1.677 - Node target = graph.target(edge);
1.678 + Arc arc = dfs.nextArc();
1.679 + Node source = graph.source(arc);
1.680 + Node target = graph.target(arc);
1.681 if (dfs.reached(target) &&
1.682 - dfs.predArc(source) != graph.oppositeArc(edge)) {
1.683 + dfs.predArc(source) != graph.oppositeArc(arc)) {
1.684 return false;
1.685 }
1.686 dfs.processNextArc();
1.687 @@ -1359,26 +1429,27 @@
1.688
1.689 /// \ingroup graph_properties
1.690 ///
1.691 - /// \brief Check that the given undirected graph is tree.
1.692 + /// \brief Check whether an undirected graph is tree.
1.693 ///
1.694 - /// Check that the given undirected graph is tree.
1.695 - /// \param graph The undirected graph.
1.696 - /// \return \c true when the graph is acyclic and connected.
1.697 + /// This function checks whether the given undirected graph is tree.
1.698 + /// \return \c true if the graph is acyclic and connected.
1.699 + /// \see acyclic(), connected()
1.700 template <typename Graph>
1.701 bool tree(const Graph& graph) {
1.702 checkConcept<concepts::Graph, Graph>();
1.703 typedef typename Graph::Node Node;
1.704 typedef typename Graph::NodeIt NodeIt;
1.705 typedef typename Graph::Arc Arc;
1.706 + if (NodeIt(graph) == INVALID) return true;
1.707 Dfs<Graph> dfs(graph);
1.708 dfs.init();
1.709 dfs.addSource(NodeIt(graph));
1.710 while (!dfs.emptyQueue()) {
1.711 - Arc edge = dfs.nextArc();
1.712 - Node source = graph.source(edge);
1.713 - Node target = graph.target(edge);
1.714 + Arc arc = dfs.nextArc();
1.715 + Node source = graph.source(arc);
1.716 + Node target = graph.target(arc);
1.717 if (dfs.reached(target) &&
1.718 - dfs.predArc(source) != graph.oppositeArc(edge)) {
1.719 + dfs.predArc(source) != graph.oppositeArc(arc)) {
1.720 return false;
1.721 }
1.722 dfs.processNextArc();
1.723 @@ -1451,15 +1522,14 @@
1.724
1.725 /// \ingroup graph_properties
1.726 ///
1.727 - /// \brief Check if the given undirected graph is bipartite or not
1.728 + /// \brief Check whether an undirected graph is bipartite.
1.729 ///
1.730 - /// The function checks if the given undirected \c graph graph is bipartite
1.731 - /// or not. The \ref Bfs algorithm is used to calculate the result.
1.732 - /// \param graph The undirected graph.
1.733 - /// \return \c true if \c graph is bipartite, \c false otherwise.
1.734 - /// \sa bipartitePartitions
1.735 + /// The function checks whether the given undirected graph is bipartite.
1.736 + /// \return \c true if the graph is bipartite.
1.737 + ///
1.738 + /// \see bipartitePartitions()
1.739 template<typename Graph>
1.740 - inline bool bipartite(const Graph &graph){
1.741 + bool bipartite(const Graph &graph){
1.742 using namespace _connectivity_bits;
1.743
1.744 checkConcept<concepts::Graph, Graph>();
1.745 @@ -1488,25 +1558,27 @@
1.746
1.747 /// \ingroup graph_properties
1.748 ///
1.749 - /// \brief Check if the given undirected graph is bipartite or not
1.750 + /// \brief Find the bipartite partitions of an undirected graph.
1.751 ///
1.752 - /// The function checks if the given undirected graph is bipartite
1.753 - /// or not. The \ref Bfs algorithm is used to calculate the result.
1.754 - /// During the execution, the \c partMap will be set as the two
1.755 - /// partitions of the graph.
1.756 + /// This function checks whether the given undirected graph is bipartite
1.757 + /// and gives back the bipartite partitions.
1.758 ///
1.759 /// \image html bipartite_partitions.png
1.760 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.761 ///
1.762 /// \param graph The undirected graph.
1.763 - /// \retval partMap A writable bool map of nodes. It will be set as the
1.764 - /// two partitions of the graph.
1.765 - /// \return \c true if \c graph is bipartite, \c false otherwise.
1.766 + /// \retval partMap A writable node map of \c bool (or convertible) value
1.767 + /// type. The values will be set to \c true for one component and
1.768 + /// \c false for the other one.
1.769 + /// \return \c true if the graph is bipartite, \c false otherwise.
1.770 + ///
1.771 + /// \see bipartite()
1.772 template<typename Graph, typename NodeMap>
1.773 - inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.774 + bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.775 using namespace _connectivity_bits;
1.776
1.777 checkConcept<concepts::Graph, Graph>();
1.778 + checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
1.779
1.780 typedef typename Graph::Node Node;
1.781 typedef typename Graph::NodeIt NodeIt;
1.782 @@ -1531,53 +1603,59 @@
1.783 return true;
1.784 }
1.785
1.786 - /// \brief Returns true when there are not loop edges in the graph.
1.787 + /// \ingroup graph_properties
1.788 ///
1.789 - /// Returns true when there are not loop edges in the graph.
1.790 - template <typename Digraph>
1.791 - bool loopFree(const Digraph& digraph) {
1.792 - for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
1.793 - if (digraph.source(it) == digraph.target(it)) return false;
1.794 + /// \brief Check whether the given graph contains no loop arcs/edges.
1.795 + ///
1.796 + /// This function returns \c true if there are no loop arcs/edges in
1.797 + /// the given graph. It works for both directed and undirected graphs.
1.798 + template <typename Graph>
1.799 + bool loopFree(const Graph& graph) {
1.800 + for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
1.801 + if (graph.source(it) == graph.target(it)) return false;
1.802 }
1.803 return true;
1.804 }
1.805
1.806 - /// \brief Returns true when there are not parallel edges in the graph.
1.807 + /// \ingroup graph_properties
1.808 ///
1.809 - /// Returns true when there are not parallel edges in the graph.
1.810 - template <typename Digraph>
1.811 - bool parallelFree(const Digraph& digraph) {
1.812 - typename Digraph::template NodeMap<bool> reached(digraph, false);
1.813 - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.814 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.815 - if (reached[digraph.target(a)]) return false;
1.816 - reached.set(digraph.target(a), true);
1.817 + /// \brief Check whether the given graph contains no parallel arcs/edges.
1.818 + ///
1.819 + /// This function returns \c true if there are no parallel arcs/edges in
1.820 + /// the given graph. It works for both directed and undirected graphs.
1.821 + template <typename Graph>
1.822 + bool parallelFree(const Graph& graph) {
1.823 + typename Graph::template NodeMap<int> reached(graph, 0);
1.824 + int cnt = 1;
1.825 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.826 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1.827 + if (reached[graph.target(a)] == cnt) return false;
1.828 + reached[graph.target(a)] = cnt;
1.829 }
1.830 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.831 - reached.set(digraph.target(a), false);
1.832 - }
1.833 + ++cnt;
1.834 }
1.835 return true;
1.836 }
1.837
1.838 - /// \brief Returns true when there are not loop edges and parallel
1.839 - /// edges in the graph.
1.840 + /// \ingroup graph_properties
1.841 ///
1.842 - /// Returns true when there are not loop edges and parallel edges in
1.843 - /// the graph.
1.844 - template <typename Digraph>
1.845 - bool simpleDigraph(const Digraph& digraph) {
1.846 - typename Digraph::template NodeMap<bool> reached(digraph, false);
1.847 - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.848 - reached.set(n, true);
1.849 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.850 - if (reached[digraph.target(a)]) return false;
1.851 - reached.set(digraph.target(a), true);
1.852 + /// \brief Check whether the given graph is simple.
1.853 + ///
1.854 + /// This function returns \c true if the given graph is simple, i.e.
1.855 + /// it contains no loop arcs/edges and no parallel arcs/edges.
1.856 + /// The function works for both directed and undirected graphs.
1.857 + /// \see loopFree(), parallelFree()
1.858 + template <typename Graph>
1.859 + bool simpleGraph(const Graph& graph) {
1.860 + typename Graph::template NodeMap<int> reached(graph, 0);
1.861 + int cnt = 1;
1.862 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.863 + reached[n] = cnt;
1.864 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1.865 + if (reached[graph.target(a)] == cnt) return false;
1.866 + reached[graph.target(a)] = cnt;
1.867 }
1.868 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.869 - reached.set(digraph.target(a), false);
1.870 - }
1.871 - reached.set(n, false);
1.872 + ++cnt;
1.873 }
1.874 return true;
1.875 }
2.1 --- a/lemon/euler.h Thu May 07 02:07:59 2009 +0200
2.2 +++ b/lemon/euler.h Thu May 07 12:19:41 2009 +0100
2.3 @@ -244,10 +244,10 @@
2.4 };
2.5
2.6
2.7 - ///Check if the given graph is \e Eulerian
2.8 + ///Check if the given graph is Eulerian
2.9
2.10 /// \ingroup graph_properties
2.11 - ///This function checks if the given graph is \e Eulerian.
2.12 + ///This function checks if the given graph is Eulerian.
2.13 ///It works for both directed and undirected graphs.
2.14 ///
2.15 ///By definition, a digraph is called \e Eulerian if
3.1 --- a/test/CMakeLists.txt Thu May 07 02:07:59 2009 +0200
3.2 +++ b/test/CMakeLists.txt Thu May 07 12:19:41 2009 +0100
3.3 @@ -9,6 +9,7 @@
3.4 adaptors_test
3.5 bfs_test
3.6 circulation_test
3.7 + connectivity_test
3.8 counter_test
3.9 dfs_test
3.10 digraph_test
4.1 --- a/test/Makefile.am Thu May 07 02:07:59 2009 +0200
4.2 +++ b/test/Makefile.am Thu May 07 12:19:41 2009 +0100
4.3 @@ -9,6 +9,7 @@
4.4 test/adaptors_test \
4.5 test/bfs_test \
4.6 test/circulation_test \
4.7 + test/connectivity_test \
4.8 test/counter_test \
4.9 test/dfs_test \
4.10 test/digraph_test \
4.11 @@ -54,6 +55,7 @@
4.12 test_bfs_test_SOURCES = test/bfs_test.cc
4.13 test_circulation_test_SOURCES = test/circulation_test.cc
4.14 test_counter_test_SOURCES = test/counter_test.cc
4.15 +test_connectivity_test_SOURCES = test/connectivity_test.cc
4.16 test_dfs_test_SOURCES = test/dfs_test.cc
4.17 test_digraph_test_SOURCES = test/digraph_test.cc
4.18 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/connectivity_test.cc Thu May 07 12:19:41 2009 +0100
5.3 @@ -0,0 +1,297 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2009
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#include <lemon/connectivity.h>
5.23 +#include <lemon/list_graph.h>
5.24 +#include <lemon/adaptors.h>
5.25 +
5.26 +#include "test_tools.h"
5.27 +
5.28 +using namespace lemon;
5.29 +
5.30 +
5.31 +int main()
5.32 +{
5.33 + typedef ListDigraph Digraph;
5.34 + typedef Undirector<Digraph> Graph;
5.35 +
5.36 + {
5.37 + Digraph d;
5.38 + Digraph::NodeMap<int> order(d);
5.39 + Graph g(d);
5.40 +
5.41 + check(stronglyConnected(d), "The empty digraph is strongly connected");
5.42 + check(countStronglyConnectedComponents(d) == 0,
5.43 + "The empty digraph has 0 strongly connected component");
5.44 + check(connected(g), "The empty graph is connected");
5.45 + check(countConnectedComponents(g) == 0,
5.46 + "The empty graph has 0 connected component");
5.47 +
5.48 + check(biNodeConnected(g), "The empty graph is bi-node-connected");
5.49 + check(countBiNodeConnectedComponents(g) == 0,
5.50 + "The empty graph has 0 bi-node-connected component");
5.51 + check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
5.52 + check(countBiEdgeConnectedComponents(g) == 0,
5.53 + "The empty graph has 0 bi-edge-connected component");
5.54 +
5.55 + check(dag(d), "The empty digraph is DAG.");
5.56 + check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
5.57 + check(loopFree(d), "The empty digraph is loop-free.");
5.58 + check(parallelFree(d), "The empty digraph is parallel-free.");
5.59 + check(simpleGraph(d), "The empty digraph is simple.");
5.60 +
5.61 + check(acyclic(g), "The empty graph is acyclic.");
5.62 + check(tree(g), "The empty graph is tree.");
5.63 + check(bipartite(g), "The empty graph is bipartite.");
5.64 + check(loopFree(g), "The empty graph is loop-free.");
5.65 + check(parallelFree(g), "The empty graph is parallel-free.");
5.66 + check(simpleGraph(g), "The empty graph is simple.");
5.67 + }
5.68 +
5.69 + {
5.70 + Digraph d;
5.71 + Digraph::NodeMap<int> order(d);
5.72 + Graph g(d);
5.73 + Digraph::Node n = d.addNode();
5.74 +
5.75 + check(stronglyConnected(d), "This digraph is strongly connected");
5.76 + check(countStronglyConnectedComponents(d) == 1,
5.77 + "This digraph has 1 strongly connected component");
5.78 + check(connected(g), "This graph is connected");
5.79 + check(countConnectedComponents(g) == 1,
5.80 + "This graph has 1 connected component");
5.81 +
5.82 + check(biNodeConnected(g), "This graph is bi-node-connected");
5.83 + check(countBiNodeConnectedComponents(g) == 0,
5.84 + "This graph has 0 bi-node-connected component");
5.85 + check(biEdgeConnected(g), "This graph is bi-edge-connected");
5.86 + check(countBiEdgeConnectedComponents(g) == 1,
5.87 + "This graph has 1 bi-edge-connected component");
5.88 +
5.89 + check(dag(d), "This digraph is DAG.");
5.90 + check(checkedTopologicalSort(d, order), "This digraph is DAG.");
5.91 + check(loopFree(d), "This digraph is loop-free.");
5.92 + check(parallelFree(d), "This digraph is parallel-free.");
5.93 + check(simpleGraph(d), "This digraph is simple.");
5.94 +
5.95 + check(acyclic(g), "This graph is acyclic.");
5.96 + check(tree(g), "This graph is tree.");
5.97 + check(bipartite(g), "This graph is bipartite.");
5.98 + check(loopFree(g), "This graph is loop-free.");
5.99 + check(parallelFree(g), "This graph is parallel-free.");
5.100 + check(simpleGraph(g), "This graph is simple.");
5.101 + }
5.102 +
5.103 + {
5.104 + Digraph d;
5.105 + Digraph::NodeMap<int> order(d);
5.106 + Graph g(d);
5.107 +
5.108 + Digraph::Node n1 = d.addNode();
5.109 + Digraph::Node n2 = d.addNode();
5.110 + Digraph::Node n3 = d.addNode();
5.111 + Digraph::Node n4 = d.addNode();
5.112 + Digraph::Node n5 = d.addNode();
5.113 + Digraph::Node n6 = d.addNode();
5.114 +
5.115 + d.addArc(n1, n3);
5.116 + d.addArc(n3, n2);
5.117 + d.addArc(n2, n1);
5.118 + d.addArc(n4, n2);
5.119 + d.addArc(n4, n3);
5.120 + d.addArc(n5, n6);
5.121 + d.addArc(n6, n5);
5.122 +
5.123 + check(!stronglyConnected(d), "This digraph is not strongly connected");
5.124 + check(countStronglyConnectedComponents(d) == 3,
5.125 + "This digraph has 3 strongly connected components");
5.126 + check(!connected(g), "This graph is not connected");
5.127 + check(countConnectedComponents(g) == 2,
5.128 + "This graph has 2 connected components");
5.129 +
5.130 + check(!dag(d), "This digraph is not DAG.");
5.131 + check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
5.132 + check(loopFree(d), "This digraph is loop-free.");
5.133 + check(parallelFree(d), "This digraph is parallel-free.");
5.134 + check(simpleGraph(d), "This digraph is simple.");
5.135 +
5.136 + check(!acyclic(g), "This graph is not acyclic.");
5.137 + check(!tree(g), "This graph is not tree.");
5.138 + check(!bipartite(g), "This graph is not bipartite.");
5.139 + check(loopFree(g), "This graph is loop-free.");
5.140 + check(!parallelFree(g), "This graph is not parallel-free.");
5.141 + check(!simpleGraph(g), "This graph is not simple.");
5.142 +
5.143 + d.addArc(n3, n3);
5.144 +
5.145 + check(!loopFree(d), "This digraph is not loop-free.");
5.146 + check(!loopFree(g), "This graph is not loop-free.");
5.147 + check(!simpleGraph(d), "This digraph is not simple.");
5.148 +
5.149 + d.addArc(n3, n2);
5.150 +
5.151 + check(!parallelFree(d), "This digraph is not parallel-free.");
5.152 + }
5.153 +
5.154 + {
5.155 + Digraph d;
5.156 + Digraph::ArcMap<bool> cutarcs(d, false);
5.157 + Graph g(d);
5.158 +
5.159 + Digraph::Node n1 = d.addNode();
5.160 + Digraph::Node n2 = d.addNode();
5.161 + Digraph::Node n3 = d.addNode();
5.162 + Digraph::Node n4 = d.addNode();
5.163 + Digraph::Node n5 = d.addNode();
5.164 + Digraph::Node n6 = d.addNode();
5.165 + Digraph::Node n7 = d.addNode();
5.166 + Digraph::Node n8 = d.addNode();
5.167 +
5.168 + d.addArc(n1, n2);
5.169 + d.addArc(n5, n1);
5.170 + d.addArc(n2, n8);
5.171 + d.addArc(n8, n5);
5.172 + d.addArc(n6, n4);
5.173 + d.addArc(n4, n6);
5.174 + d.addArc(n2, n5);
5.175 + d.addArc(n1, n8);
5.176 + d.addArc(n6, n7);
5.177 + d.addArc(n7, n6);
5.178 +
5.179 + check(!stronglyConnected(d), "This digraph is not strongly connected");
5.180 + check(countStronglyConnectedComponents(d) == 3,
5.181 + "This digraph has 3 strongly connected components");
5.182 + Digraph::NodeMap<int> scomp1(d);
5.183 + check(stronglyConnectedComponents(d, scomp1) == 3,
5.184 + "This digraph has 3 strongly connected components");
5.185 + check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
5.186 + scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
5.187 + check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
5.188 + scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
5.189 + check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
5.190 + "Wrong stronglyConnectedComponents()");
5.191 + Digraph::ArcMap<bool> scut1(d, false);
5.192 + check(stronglyConnectedCutArcs(d, scut1) == 0,
5.193 + "This digraph has 0 strongly connected cut arc.");
5.194 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
5.195 + check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
5.196 + }
5.197 +
5.198 + check(!connected(g), "This graph is not connected");
5.199 + check(countConnectedComponents(g) == 3,
5.200 + "This graph has 3 connected components");
5.201 + Graph::NodeMap<int> comp(g);
5.202 + check(connectedComponents(g, comp) == 3,
5.203 + "This graph has 3 connected components");
5.204 + check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
5.205 + comp[n3] != comp[n4], "Wrong connectedComponents()");
5.206 + check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
5.207 + comp[n1] == comp[n8], "Wrong connectedComponents()");
5.208 + check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
5.209 + "Wrong connectedComponents()");
5.210 +
5.211 + cutarcs[d.addArc(n3, n1)] = true;
5.212 + cutarcs[d.addArc(n3, n5)] = true;
5.213 + cutarcs[d.addArc(n3, n8)] = true;
5.214 + cutarcs[d.addArc(n8, n6)] = true;
5.215 + cutarcs[d.addArc(n8, n7)] = true;
5.216 +
5.217 + check(!stronglyConnected(d), "This digraph is not strongly connected");
5.218 + check(countStronglyConnectedComponents(d) == 3,
5.219 + "This digraph has 3 strongly connected components");
5.220 + Digraph::NodeMap<int> scomp2(d);
5.221 + check(stronglyConnectedComponents(d, scomp2) == 3,
5.222 + "This digraph has 3 strongly connected components");
5.223 + check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
5.224 + check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
5.225 + scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
5.226 + check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
5.227 + "Wrong stronglyConnectedComponents()");
5.228 + Digraph::ArcMap<bool> scut2(d, false);
5.229 + check(stronglyConnectedCutArcs(d, scut2) == 5,
5.230 + "This digraph has 5 strongly connected cut arcs.");
5.231 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
5.232 + check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
5.233 + }
5.234 + }
5.235 +
5.236 + {
5.237 + // DAG example for topological sort from the book New Algorithms
5.238 + // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
5.239 + Digraph d;
5.240 + Digraph::NodeMap<int> order(d);
5.241 +
5.242 + Digraph::Node belt = d.addNode();
5.243 + Digraph::Node trousers = d.addNode();
5.244 + Digraph::Node necktie = d.addNode();
5.245 + Digraph::Node coat = d.addNode();
5.246 + Digraph::Node socks = d.addNode();
5.247 + Digraph::Node shirt = d.addNode();
5.248 + Digraph::Node shoe = d.addNode();
5.249 + Digraph::Node watch = d.addNode();
5.250 + Digraph::Node pants = d.addNode();
5.251 +
5.252 + d.addArc(socks, shoe);
5.253 + d.addArc(pants, shoe);
5.254 + d.addArc(pants, trousers);
5.255 + d.addArc(trousers, shoe);
5.256 + d.addArc(trousers, belt);
5.257 + d.addArc(belt, coat);
5.258 + d.addArc(shirt, belt);
5.259 + d.addArc(shirt, necktie);
5.260 + d.addArc(necktie, coat);
5.261 +
5.262 + check(dag(d), "This digraph is DAG.");
5.263 + topologicalSort(d, order);
5.264 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
5.265 + check(order[d.source(a)] < order[d.target(a)],
5.266 + "Wrong topologicalSort()");
5.267 + }
5.268 + }
5.269 +
5.270 + {
5.271 + ListGraph g;
5.272 + ListGraph::NodeMap<bool> map(g);
5.273 +
5.274 + ListGraph::Node n1 = g.addNode();
5.275 + ListGraph::Node n2 = g.addNode();
5.276 + ListGraph::Node n3 = g.addNode();
5.277 + ListGraph::Node n4 = g.addNode();
5.278 + ListGraph::Node n5 = g.addNode();
5.279 + ListGraph::Node n6 = g.addNode();
5.280 + ListGraph::Node n7 = g.addNode();
5.281 +
5.282 + g.addEdge(n1, n3);
5.283 + g.addEdge(n1, n4);
5.284 + g.addEdge(n2, n5);
5.285 + g.addEdge(n3, n6);
5.286 + g.addEdge(n4, n6);
5.287 + g.addEdge(n4, n7);
5.288 + g.addEdge(n5, n7);
5.289 +
5.290 + check(bipartite(g), "This graph is bipartite");
5.291 + check(bipartitePartitions(g, map), "This graph is bipartite");
5.292 +
5.293 + check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
5.294 + "Wrong bipartitePartitions()");
5.295 + check(map[n3] == map[n4] && map[n3] == map[n5],
5.296 + "Wrong bipartitePartitions()");
5.297 + }
5.298 +
5.299 + return 0;
5.300 +}