equal
deleted
inserted
replaced
44 /// |
44 /// |
45 /// \brief Check whether the given undirected graph is connected. |
45 /// \brief Check whether the given undirected graph is connected. |
46 /// |
46 /// |
47 /// Check whether the given undirected graph is connected. |
47 /// Check whether the given undirected graph is connected. |
48 /// \param graph The undirected graph. |
48 /// \param graph The undirected graph. |
49 /// \return %True when there is path between any two nodes in the graph. |
49 /// \return \c true when there is path between any two nodes in the graph. |
50 /// \note By definition, the empty graph is connected. |
50 /// \note By definition, the empty graph is connected. |
51 template <typename Graph> |
51 template <typename Graph> |
52 bool connected(const Graph& graph) { |
52 bool connected(const Graph& graph) { |
53 checkConcept<concepts::Graph, Graph>(); |
53 checkConcept<concepts::Graph, Graph>(); |
54 typedef typename Graph::NodeIt NodeIt; |
54 typedef typename Graph::NodeIt NodeIt; |
232 /// \brief Check whether the given directed graph is strongly connected. |
232 /// \brief Check whether the given directed graph is strongly connected. |
233 /// |
233 /// |
234 /// Check whether the given directed graph is strongly connected. The |
234 /// Check whether the given directed graph is strongly connected. The |
235 /// graph is strongly connected when any two nodes of the graph are |
235 /// graph is strongly connected when any two nodes of the graph are |
236 /// connected with directed paths in both direction. |
236 /// connected with directed paths in both direction. |
237 /// \return %False when the graph is not strongly connected. |
237 /// \return \c false when the graph is not strongly connected. |
238 /// \see connected |
238 /// \see connected |
239 /// |
239 /// |
240 /// \note By definition, the empty graph is strongly connected. |
240 /// \note By definition, the empty graph is strongly connected. |
241 template <typename Digraph> |
241 template <typename Digraph> |
242 bool stronglyConnected(const Digraph& digraph) { |
242 bool stronglyConnected(const Digraph& digraph) { |
707 /// This function checks that the undirected graph is bi-node-connected |
707 /// This function checks that the undirected graph is bi-node-connected |
708 /// graph. The graph is bi-node-connected if any two undirected edge is |
708 /// graph. The graph is bi-node-connected if any two undirected edge is |
709 /// on same circle. |
709 /// on same circle. |
710 /// |
710 /// |
711 /// \param graph The graph. |
711 /// \param graph The graph. |
712 /// \return %True when the graph bi-node-connected. |
712 /// \return \c true when the graph bi-node-connected. |
713 template <typename Graph> |
713 template <typename Graph> |
714 bool biNodeConnected(const Graph& graph) { |
714 bool biNodeConnected(const Graph& graph) { |
715 return countBiNodeConnectedComponents(graph) <= 1; |
715 return countBiNodeConnectedComponents(graph) <= 1; |
716 } |
716 } |
717 |
717 |
1228 /// \param digraph The graph. It must be directed and acyclic. |
1228 /// \param digraph The graph. It must be directed and acyclic. |
1229 /// \retval order A readable - writable node map. The values will be set |
1229 /// \retval order A readable - writable node map. The values will be set |
1230 /// from 0 to the number of the nodes in the graph minus one. Each values |
1230 /// from 0 to the number of the nodes in the graph minus one. Each values |
1231 /// of the map will be set exactly once, the values will be set descending |
1231 /// of the map will be set exactly once, the values will be set descending |
1232 /// order. |
1232 /// order. |
1233 /// \return %False when the graph is not DAG. |
1233 /// \return \c false when the graph is not DAG. |
1234 /// |
1234 /// |
1235 /// \see topologicalSort |
1235 /// \see topologicalSort |
1236 /// \see dag |
1236 /// \see dag |
1237 template <typename Digraph, typename NodeMap> |
1237 template <typename Digraph, typename NodeMap> |
1238 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { |
1238 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { |
1277 /// |
1277 /// |
1278 /// \brief Check that the given directed graph is a DAG. |
1278 /// \brief Check that the given directed graph is a DAG. |
1279 /// |
1279 /// |
1280 /// Check that the given directed graph is a DAG. The DAG is |
1280 /// Check that the given directed graph is a DAG. The DAG is |
1281 /// an Directed Acyclic Digraph. |
1281 /// an Directed Acyclic Digraph. |
1282 /// \return %False when the graph is not DAG. |
1282 /// \return \c false when the graph is not DAG. |
1283 /// \see acyclic |
1283 /// \see acyclic |
1284 template <typename Digraph> |
1284 template <typename Digraph> |
1285 bool dag(const Digraph& digraph) { |
1285 bool dag(const Digraph& digraph) { |
1286 |
1286 |
1287 checkConcept<concepts::Digraph, Digraph>(); |
1287 checkConcept<concepts::Digraph, Digraph>(); |
1319 /// |
1319 /// |
1320 /// \brief Check that the given undirected graph is acyclic. |
1320 /// \brief Check that the given undirected graph is acyclic. |
1321 /// |
1321 /// |
1322 /// Check that the given undirected graph acyclic. |
1322 /// Check that the given undirected graph acyclic. |
1323 /// \param graph The undirected graph. |
1323 /// \param graph The undirected graph. |
1324 /// \return %True when there is no circle in the graph. |
1324 /// \return \c true when there is no circle in the graph. |
1325 /// \see dag |
1325 /// \see dag |
1326 template <typename Graph> |
1326 template <typename Graph> |
1327 bool acyclic(const Graph& graph) { |
1327 bool acyclic(const Graph& graph) { |
1328 checkConcept<concepts::Graph, Graph>(); |
1328 checkConcept<concepts::Graph, Graph>(); |
1329 typedef typename Graph::Node Node; |
1329 typedef typename Graph::Node Node; |
1353 /// |
1353 /// |
1354 /// \brief Check that the given undirected graph is tree. |
1354 /// \brief Check that the given undirected graph is tree. |
1355 /// |
1355 /// |
1356 /// Check that the given undirected graph is tree. |
1356 /// Check that the given undirected graph is tree. |
1357 /// \param graph The undirected graph. |
1357 /// \param graph The undirected graph. |
1358 /// \return %True when the graph is acyclic and connected. |
1358 /// \return \c true when the graph is acyclic and connected. |
1359 template <typename Graph> |
1359 template <typename Graph> |
1360 bool tree(const Graph& graph) { |
1360 bool tree(const Graph& graph) { |
1361 checkConcept<concepts::Graph, Graph>(); |
1361 checkConcept<concepts::Graph, Graph>(); |
1362 typedef typename Graph::Node Node; |
1362 typedef typename Graph::Node Node; |
1363 typedef typename Graph::NodeIt NodeIt; |
1363 typedef typename Graph::NodeIt NodeIt; |
1446 /// \brief Check if the given undirected graph is bipartite or not |
1446 /// \brief Check if the given undirected graph is bipartite or not |
1447 /// |
1447 /// |
1448 /// The function checks if the given undirected \c graph graph is bipartite |
1448 /// The function checks if the given undirected \c graph graph is bipartite |
1449 /// or not. The \ref Bfs algorithm is used to calculate the result. |
1449 /// or not. The \ref Bfs algorithm is used to calculate the result. |
1450 /// \param graph The undirected graph. |
1450 /// \param graph The undirected graph. |
1451 /// \return %True if \c graph is bipartite, %false otherwise. |
1451 /// \return \c true if \c graph is bipartite, \c false otherwise. |
1452 /// \sa bipartitePartitions |
1452 /// \sa bipartitePartitions |
1453 template<typename Graph> |
1453 template<typename Graph> |
1454 inline bool bipartite(const Graph &graph){ |
1454 inline bool bipartite(const Graph &graph){ |
1455 using namespace _connectivity_bits; |
1455 using namespace _connectivity_bits; |
1456 |
1456 |
1487 /// During the execution, the \c partMap will be set as the two |
1487 /// During the execution, the \c partMap will be set as the two |
1488 /// partitions of the graph. |
1488 /// partitions of the graph. |
1489 /// \param graph The undirected graph. |
1489 /// \param graph The undirected graph. |
1490 /// \retval partMap A writable bool map of nodes. It will be set as the |
1490 /// \retval partMap A writable bool map of nodes. It will be set as the |
1491 /// two partitions of the graph. |
1491 /// two partitions of the graph. |
1492 /// \return %True if \c graph is bipartite, %false otherwise. |
1492 /// \return \c true if \c graph is bipartite, \c false otherwise. |
1493 template<typename Graph, typename NodeMap> |
1493 template<typename Graph, typename NodeMap> |
1494 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ |
1494 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ |
1495 using namespace _connectivity_bits; |
1495 using namespace _connectivity_bits; |
1496 |
1496 |
1497 checkConcept<concepts::Graph, Graph>(); |
1497 checkConcept<concepts::Graph, Graph>(); |