Changes in lemon/connectivity.h [695:4ff8041e9c2e:633:7c12061bd271] in lemon
- File:
-
- 1 edited
-
lemon/connectivity.h (modified) (30 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r695 r633 43 43 /// \ingroup graph_properties 44 44 /// 45 /// \brief Check whether an undirected graph is connected. 46 /// 47 /// This function checks whether the given undirected graph is connected, 48 /// i.e. there is a path between any two nodes in the graph. 49 /// 50 /// \return \c true if the graph is connected. 45 /// \brief Check whether the given undirected graph is connected. 46 /// 47 /// Check whether the given undirected graph is connected. 48 /// \param graph The undirected graph. 49 /// \return \c true when there is path between any two nodes in the graph. 51 50 /// \note By definition, the empty graph is connected. 52 ///53 /// \see countConnectedComponents(), connectedComponents()54 /// \see stronglyConnected()55 51 template <typename Graph> 56 52 bool connected(const Graph& graph) { … … 72 68 /// \brief Count the number of connected components of an undirected graph 73 69 /// 74 /// This function counts the number of connected components of the given 75 /// undirected graph. 76 /// 77 /// The connected components are the classes of an equivalence relation 78 /// on the nodes of an undirected graph. Two nodes are in the same class 79 /// if they are connected with a path. 80 /// 81 /// \return The number of connected components. 70 /// Count the number of connected components of an undirected graph 71 /// 72 /// \param graph The graph. It must be undirected. 73 /// \return The number of components 82 74 /// \note By definition, the empty graph consists 83 75 /// of zero connected components. 84 ///85 /// \see connected(), connectedComponents()86 76 template <typename Graph> 87 77 int countConnectedComponents(const Graph &graph) { … … 120 110 /// \brief Find the connected components of an undirected graph 121 111 /// 122 /// This function finds the connected components of the given undirected 123 /// graph. 124 /// 125 /// The connected components are the classes of an equivalence relation 126 /// on the nodes of an undirected graph. Two nodes are in the same class 127 /// if they are connected with a path. 112 /// Find the connected components of an undirected graph. 128 113 /// 129 114 /// \image html connected_components.png 130 115 /// \image latex connected_components.eps "Connected components" width=\textwidth 131 116 /// 132 /// \param graph The undirected graph.117 /// \param graph The graph. It must be undirected. 133 118 /// \retval compMap A writable node map. The values will be set from 0 to 134 /// the number of the connected components minus one. Each value of the map135 /// will be set exactly once, andthe values of a certain component will be119 /// the number of the connected components minus one. Each values of the map 120 /// will be set exactly once, the values of a certain component will be 136 121 /// set continuously. 137 /// \return The number of connected components. 138 /// \note By definition, the empty graph consists 139 /// of zero connected components. 140 /// 141 /// \see connected(), countConnectedComponents() 122 /// \return The number of components 142 123 template <class Graph, class NodeMap> 143 124 int connectedComponents(const Graph &graph, NodeMap &compMap) { … … 251 232 /// \ingroup graph_properties 252 233 /// 253 /// \brief Check whether adirected graph is strongly connected.254 /// 255 /// This function checks whether the given directed graph is strongly256 /// connected, i.e. any two nodes of the digraph are234 /// \brief Check whether the given directed graph is strongly connected. 235 /// 236 /// Check whether the given directed graph is strongly connected. The 237 /// graph is strongly connected when any two nodes of the graph are 257 238 /// connected with directed paths in both direction. 258 /// 259 /// \return \c true if the digraph is strongly connected. 260 /// \note By definition, the empty digraph is strongly connected. 261 /// 262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() 263 /// \see connected() 239 /// \return \c false when the graph is not strongly connected. 240 /// \see connected 241 /// 242 /// \note By definition, the empty graph is strongly connected. 264 243 template <typename Digraph> 265 244 bool stronglyConnected(const Digraph& digraph) { … … 292 271 RDigraph rdigraph(digraph); 293 272 294 typedef DfsVisitor< RDigraph> RVisitor;273 typedef DfsVisitor<Digraph> RVisitor; 295 274 RVisitor rvisitor; 296 275 … … 311 290 /// \ingroup graph_properties 312 291 /// 313 /// \brief Count the number of strongly connected components of a 314 /// directed graph 315 /// 316 /// This function counts the number of strongly connected components of 317 /// the given directed graph. 318 /// 292 /// \brief Count the strongly connected components of a directed graph 293 /// 294 /// Count the strongly connected components of a directed graph. 319 295 /// The strongly connected components are the classes of an 320 /// equivalence relation on the nodes of a digraph. Two nodes are in296 /// equivalence relation on the nodes of the graph. Two nodes are in 321 297 /// the same class if they are connected with directed paths in both 322 298 /// direction. 323 299 /// 324 /// \return The number of strongly connected components. 325 /// \note By definition, the empty digraph has zero 300 /// \param digraph The graph. 301 /// \return The number of components 302 /// \note By definition, the empty graph has zero 326 303 /// strongly connected components. 327 ///328 /// \see stronglyConnected(), stronglyConnectedComponents()329 304 template <typename Digraph> 330 305 int countStronglyConnectedComponents(const Digraph& digraph) { … … 381 356 /// \brief Find the strongly connected components of a directed graph 382 357 /// 383 /// This function finds the strongly connected components of the given 384 /// directed graph. In addition, the numbering of the components will 385 /// satisfy that there is no arc going from a higher numbered component 386 /// to a lower one (i.e. it provides a topological order of the components). 387 /// 388 /// The strongly connected components are the classes of an 389 /// equivalence relation on the nodes of a digraph. Two nodes are in 390 /// the same class if they are connected with directed paths in both 391 /// direction. 358 /// Find the strongly connected components of a directed graph. The 359 /// strongly connected components are the classes of an equivalence 360 /// relation on the nodes of the graph. Two nodes are in 361 /// relationship when there are directed paths between them in both 362 /// direction. In addition, the numbering of components will satisfy 363 /// that there is no arc going from a higher numbered component to 364 /// a lower. 392 365 /// 393 366 /// \image html strongly_connected_components.png … … 397 370 /// \retval compMap A writable node map. The values will be set from 0 to 398 371 /// the number of the strongly connected components minus one. Each value 399 /// of the map will be set exactly once, and the values of a certain 400 /// component will be set continuously. 401 /// \return The number of strongly connected components. 402 /// \note By definition, the empty digraph has zero 403 /// strongly connected components. 404 /// 405 /// \see stronglyConnected(), countStronglyConnectedComponents() 372 /// of the map will be set exactly once, the values of a certain component 373 /// will be set continuously. 374 /// \return The number of components 406 375 template <typename Digraph, typename NodeMap> 407 376 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { … … 456 425 /// \brief Find the cut arcs of the strongly connected components. 457 426 /// 458 /// This function finds the cut arcs of the strongly connected components 459 /// of the given digraph. 460 /// 461 /// The strongly connected components are the classes of an 462 /// equivalence relation on the nodes of a digraph. Two nodes are in 463 /// the same class if they are connected with directed paths in both 464 /// direction. 427 /// Find the cut arcs of the strongly connected components. 428 /// The strongly connected components are the classes of an equivalence 429 /// relation on the nodes of the graph. Two nodes are in relationship 430 /// when there are directed paths between them in both direction. 465 431 /// The strongly connected components are separated by the cut arcs. 466 432 /// 467 /// \param digraph The digraph. 468 /// \retval cutMap A writable arc map. The values will be set to \c true 469 /// for the cut arcs (exactly once for each cut arc), and will not be 470 /// changed for other arcs. 471 /// \return The number of cut arcs. 472 /// 473 /// \see stronglyConnected(), stronglyConnectedComponents() 433 /// \param graph The graph. 434 /// \retval cutMap A writable node map. The values will be set true when the 435 /// arc is a cut arc. 436 /// 437 /// \return The number of cut arcs 474 438 template <typename Digraph, typename ArcMap> 475 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {439 int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) { 476 440 checkConcept<concepts::Digraph, Digraph>(); 477 441 typedef typename Digraph::Node Node; … … 485 449 typedef typename Container::iterator Iterator; 486 450 487 Container nodes(countNodes( digraph));451 Container nodes(countNodes(graph)); 488 452 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 489 453 Visitor visitor(nodes.begin()); 490 454 491 DfsVisit<Digraph, Visitor> dfs( digraph, visitor);455 DfsVisit<Digraph, Visitor> dfs(graph, visitor); 492 456 dfs.init(); 493 for (NodeIt it( digraph); it != INVALID; ++it) {457 for (NodeIt it(graph); it != INVALID; ++it) { 494 458 if (!dfs.reached(it)) { 495 459 dfs.addSource(it); … … 501 465 typedef ReverseDigraph<const Digraph> RDigraph; 502 466 503 RDigraph r digraph(digraph);467 RDigraph rgraph(graph); 504 468 505 469 int cutNum = 0; 506 470 507 471 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor; 508 RVisitor rvisitor(r digraph, cutMap, cutNum);509 510 DfsVisit<RDigraph, RVisitor> rdfs(r digraph, rvisitor);472 RVisitor rvisitor(rgraph, cutMap, cutNum); 473 474 DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor); 511 475 512 476 rdfs.init(); … … 743 707 /// \ingroup graph_properties 744 708 /// 745 /// \brief Check whether an undirected graph is bi-node-connected. 746 /// 747 /// This function checks whether the given undirected graph is 748 /// bi-node-connected, i.e. any two edges are on same circle. 749 /// 750 /// \return \c true if the graph bi-node-connected. 751 /// \note By definition, the empty graph is bi-node-connected. 752 /// 753 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() 709 /// \brief Checks the graph is bi-node-connected. 710 /// 711 /// This function checks that the undirected graph is bi-node-connected 712 /// graph. The graph is bi-node-connected if any two undirected edge is 713 /// on same circle. 714 /// 715 /// \param graph The graph. 716 /// \return \c true when the graph bi-node-connected. 754 717 template <typename Graph> 755 718 bool biNodeConnected(const Graph& graph) { … … 759 722 /// \ingroup graph_properties 760 723 /// 761 /// \brief Count the number of bi-node-connected components of an 762 /// undirected graph. 763 /// 764 /// This function counts the number of bi-node-connected components of 765 /// the given undirected graph. 766 /// 767 /// The bi-node-connected components are the classes of an equivalence 768 /// relation on the edges of a undirected graph. Two edges are in the 769 /// same class if they are on same circle. 770 /// 771 /// \return The number of bi-node-connected components. 772 /// 773 /// \see biNodeConnected(), biNodeConnectedComponents() 724 /// \brief Count the biconnected components. 725 /// 726 /// This function finds the bi-node-connected components in an undirected 727 /// graph. The biconnected components are the classes of an equivalence 728 /// relation on the undirected edges. Two undirected edge is in relationship 729 /// when they are on same circle. 730 /// 731 /// \param graph The graph. 732 /// \return The number of components. 774 733 template <typename Graph> 775 734 int countBiNodeConnectedComponents(const Graph& graph) { … … 798 757 /// \ingroup graph_properties 799 758 /// 800 /// \brief Find the bi-node-connected components of an undirected graph. 801 /// 802 /// This function finds the bi-node-connected components of the given 803 /// undirected graph. 804 /// 805 /// The bi-node-connected components are the classes of an equivalence 806 /// relation on the edges of a undirected graph. Two edges are in the 807 /// same class if they are on same circle. 759 /// \brief Find the bi-node-connected components. 760 /// 761 /// This function finds the bi-node-connected components in an undirected 762 /// graph. The bi-node-connected components are the classes of an equivalence 763 /// relation on the undirected edges. Two undirected edge are in relationship 764 /// when they are on same circle. 808 765 /// 809 766 /// \image html node_biconnected_components.png 810 767 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 811 768 /// 812 /// \param graph The undirected graph. 813 /// \retval compMap A writable edge map. The values will be set from 0 814 /// to the number of the bi-node-connected components minus one. Each 815 /// value of the map will be set exactly once, and the values of a 816 /// certain component will be set continuously. 817 /// \return The number of bi-node-connected components. 818 /// 819 /// \see biNodeConnected(), countBiNodeConnectedComponents() 769 /// \param graph The graph. 770 /// \retval compMap A writable uedge map. The values will be set from 0 771 /// to the number of the biconnected components minus one. Each values 772 /// of the map will be set exactly once, the values of a certain component 773 /// will be set continuously. 774 /// \return The number of components. 820 775 template <typename Graph, typename EdgeMap> 821 776 int biNodeConnectedComponents(const Graph& graph, … … 847 802 /// \ingroup graph_properties 848 803 /// 849 /// \brief Find the bi-node-connected cut nodes in an undirected graph. 850 /// 851 /// This function finds the bi-node-connected cut nodes in the given 852 /// undirected graph. 853 /// 854 /// The bi-node-connected components are the classes of an equivalence 855 /// relation on the edges of a undirected graph. Two edges are in the 856 /// same class if they are on same circle. 857 /// The bi-node-connected components are separted by the cut nodes of 858 /// the components. 859 /// 860 /// \param graph The undirected graph. 861 /// \retval cutMap A writable node map. The values will be set to 862 /// \c true for the nodes that separate two or more components 863 /// (exactly once for each cut node), and will not be changed for 864 /// other nodes. 804 /// \brief Find the bi-node-connected cut nodes. 805 /// 806 /// This function finds the bi-node-connected cut nodes in an undirected 807 /// graph. The bi-node-connected components are the classes of an equivalence 808 /// relation on the undirected edges. Two undirected edges are in 809 /// relationship when they are on same circle. The biconnected components 810 /// are separted by nodes which are the cut nodes of the components. 811 /// 812 /// \param graph The graph. 813 /// \retval cutMap A writable edge map. The values will be set true when 814 /// the node separate two or more components. 865 815 /// \return The number of the cut nodes. 866 ///867 /// \see biNodeConnected(), biNodeConnectedComponents()868 816 template <typename Graph, typename NodeMap> 869 817 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { … … 1084 1032 /// \ingroup graph_properties 1085 1033 /// 1086 /// \brief Check whether an undirected graph is bi-edge-connected. 1087 /// 1088 /// This function checks whether the given undirected graph is 1089 /// bi-edge-connected, i.e. any two nodes are connected with at least 1090 /// two edge-disjoint paths. 1091 /// 1092 /// \return \c true if the graph is bi-edge-connected. 1093 /// \note By definition, the empty graph is bi-edge-connected. 1094 /// 1095 /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() 1034 /// \brief Checks that the graph is bi-edge-connected. 1035 /// 1036 /// This function checks that the graph is bi-edge-connected. The undirected 1037 /// graph is bi-edge-connected when any two nodes are connected with two 1038 /// edge-disjoint paths. 1039 /// 1040 /// \param graph The undirected graph. 1041 /// \return The number of components. 1096 1042 template <typename Graph> 1097 1043 bool biEdgeConnected(const Graph& graph) { … … 1101 1047 /// \ingroup graph_properties 1102 1048 /// 1103 /// \brief Count the number of bi-edge-connected components of an 1104 /// undirected graph. 1105 /// 1106 /// This function counts the number of bi-edge-connected components of 1107 /// the given undirected graph. 1108 /// 1109 /// The bi-edge-connected components are the classes of an equivalence 1110 /// relation on the nodes of an undirected graph. Two nodes are in the 1111 /// same class if they are connected with at least two edge-disjoint 1112 /// paths. 1113 /// 1114 /// \return The number of bi-edge-connected components. 1115 /// 1116 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1049 /// \brief Count the bi-edge-connected components. 1050 /// 1051 /// This function count the bi-edge-connected components in an undirected 1052 /// graph. The bi-edge-connected components are the classes of an equivalence 1053 /// relation on the nodes. Two nodes are in relationship when they are 1054 /// connected with at least two edge-disjoint paths. 1055 /// 1056 /// \param graph The undirected graph. 1057 /// \return The number of components. 1117 1058 template <typename Graph> 1118 1059 int countBiEdgeConnectedComponents(const Graph& graph) { … … 1141 1082 /// \ingroup graph_properties 1142 1083 /// 1143 /// \brief Find the bi-edge-connected components of an undirected graph. 1144 /// 1145 /// This function finds the bi-edge-connected components of the given 1146 /// undirected graph. 1147 /// 1148 /// The bi-edge-connected components are the classes of an equivalence 1149 /// relation on the nodes of an undirected graph. Two nodes are in the 1150 /// same class if they are connected with at least two edge-disjoint 1151 /// paths. 1084 /// \brief Find the bi-edge-connected components. 1085 /// 1086 /// This function finds the bi-edge-connected components in an undirected 1087 /// graph. The bi-edge-connected components are the classes of an equivalence 1088 /// relation on the nodes. Two nodes are in relationship when they are 1089 /// connected at least two edge-disjoint paths. 1152 1090 /// 1153 1091 /// \image html edge_biconnected_components.png 1154 1092 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1155 1093 /// 1156 /// \param graph The undirectedgraph.1094 /// \param graph The graph. 1157 1095 /// \retval compMap A writable node map. The values will be set from 0 to 1158 /// the number of the bi-edge-connected components minus one. Each value 1159 /// of the map will be set exactly once, and the values of a certain 1160 /// component will be set continuously. 1161 /// \return The number of bi-edge-connected components. 1162 /// 1163 /// \see biEdgeConnected(), countBiEdgeConnectedComponents() 1096 /// the number of the biconnected components minus one. Each values 1097 /// of the map will be set exactly once, the values of a certain component 1098 /// will be set continuously. 1099 /// \return The number of components. 1164 1100 template <typename Graph, typename NodeMap> 1165 1101 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 1190 1126 /// \ingroup graph_properties 1191 1127 /// 1192 /// \brief Find the bi-edge-connected cut edges in an undirected graph. 1193 /// 1194 /// This function finds the bi-edge-connected cut edges in the given 1195 /// undirected graph. 1196 /// 1197 /// The bi-edge-connected components are the classes of an equivalence 1198 /// relation on the nodes of an undirected graph. Two nodes are in the 1199 /// same class if they are connected with at least two edge-disjoint 1200 /// paths. 1201 /// The bi-edge-connected components are separted by the cut edges of 1202 /// the components. 1203 /// 1204 /// \param graph The undirected graph. 1205 /// \retval cutMap A writable edge map. The values will be set to \c true 1206 /// for the cut edges (exactly once for each cut edge), and will not be 1207 /// changed for other edges. 1128 /// \brief Find the bi-edge-connected cut edges. 1129 /// 1130 /// This function finds the bi-edge-connected components in an undirected 1131 /// graph. The bi-edge-connected components are the classes of an equivalence 1132 /// relation on the nodes. Two nodes are in relationship when they are 1133 /// connected with at least two edge-disjoint paths. The bi-edge-connected 1134 /// components are separted by edges which are the cut edges of the 1135 /// components. 1136 /// 1137 /// \param graph The graph. 1138 /// \retval cutMap A writable node map. The values will be set true when the 1139 /// edge is a cut edge. 1208 1140 /// \return The number of cut edges. 1209 ///1210 /// \see biEdgeConnected(), biEdgeConnectedComponents()1211 1141 template <typename Graph, typename EdgeMap> 1212 1142 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { … … 1260 1190 /// \ingroup graph_properties 1261 1191 /// 1262 /// \brief Check whether a digraph is DAG. 1263 /// 1264 /// This function checks whether the given digraph is DAG, i.e. 1265 /// \e Directed \e Acyclic \e Graph. 1266 /// \return \c true if there is no directed cycle in the digraph. 1267 /// \see acyclic() 1268 template <typename Digraph> 1269 bool dag(const Digraph& digraph) { 1192 /// \brief Sort the nodes of a DAG into topolgical order. 1193 /// 1194 /// Sort the nodes of a DAG into topolgical order. 1195 /// 1196 /// \param graph The graph. It must be directed and acyclic. 1197 /// \retval order A writable node map. The values will be set from 0 to 1198 /// the number of the nodes in the graph minus one. Each values of the map 1199 /// will be set exactly once, the values will be set descending order. 1200 /// 1201 /// \see checkedTopologicalSort 1202 /// \see dag 1203 template <typename Digraph, typename NodeMap> 1204 void topologicalSort(const Digraph& graph, NodeMap& order) { 1205 using namespace _connectivity_bits; 1270 1206 1271 1207 checkConcept<concepts::Digraph, Digraph>(); 1208 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>(); 1272 1209 1273 1210 typedef typename Digraph::Node Node; … … 1275 1212 typedef typename Digraph::Arc Arc; 1276 1213 1277 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1278 1279 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1280 Create dfs(digraph); 1281 1282 ProcessedMap processed(digraph); 1283 dfs.processedMap(processed); 1214 TopologicalSortVisitor<Digraph, NodeMap> 1215 visitor(order, countNodes(graph)); 1216 1217 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1218 dfs(graph, visitor); 1284 1219 1285 1220 dfs.init(); 1286 for (NodeIt it(digraph); it != INVALID; ++it) { 1287 if (!dfs.reached(it)) { 1288 dfs.addSource(it); 1289 while (!dfs.emptyQueue()) { 1290 Arc arc = dfs.nextArc(); 1291 Node target = digraph.target(arc); 1292 if (dfs.reached(target) && !processed[target]) { 1293 return false; 1294 } 1295 dfs.processNextArc(); 1296 } 1297 } 1298 } 1299 return true; 1300 } 1301 1302 /// \ingroup graph_properties 1303 /// 1304 /// \brief Sort the nodes of a DAG into topolgical order. 1305 /// 1306 /// This function sorts the nodes of the given acyclic digraph (DAG) 1307 /// into topolgical order. 1308 /// 1309 /// \param digraph The digraph, which must be DAG. 1310 /// \retval order A writable node map. The values will be set from 0 to 1311 /// the number of the nodes in the digraph minus one. Each value of the 1312 /// map will be set exactly once, and the values will be set descending 1313 /// order. 1314 /// 1315 /// \see dag(), checkedTopologicalSort() 1316 template <typename Digraph, typename NodeMap> 1317 void topologicalSort(const Digraph& digraph, NodeMap& order) { 1318 using namespace _connectivity_bits; 1319 1320 checkConcept<concepts::Digraph, Digraph>(); 1321 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>(); 1322 1323 typedef typename Digraph::Node Node; 1324 typedef typename Digraph::NodeIt NodeIt; 1325 typedef typename Digraph::Arc Arc; 1326 1327 TopologicalSortVisitor<Digraph, NodeMap> 1328 visitor(order, countNodes(digraph)); 1329 1330 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1331 dfs(digraph, visitor); 1332 1333 dfs.init(); 1334 for (NodeIt it(digraph); it != INVALID; ++it) { 1221 for (NodeIt it(graph); it != INVALID; ++it) { 1335 1222 if (!dfs.reached(it)) { 1336 1223 dfs.addSource(it); … … 1344 1231 /// \brief Sort the nodes of a DAG into topolgical order. 1345 1232 /// 1346 /// This function sorts the nodes of the given acyclic digraph (DAG)1347 /// into topolgical order and also checks whether the given digraph1348 /// is DAG.1349 /// 1350 /// \ param digraph The digraph.1351 /// \retval order A readable and writable node map. The values will be1352 /// set from 0 to the number of the nodes in the digraph minus one.1353 /// Each value of the map will be set exactly once, and the values will1354 /// be set descending order.1355 /// \return \c false if the digraph is not DAG.1356 /// 1357 /// \see dag (), topologicalSort()1233 /// Sort the nodes of a DAG into topolgical order. It also checks 1234 /// that the given graph is DAG. 1235 /// 1236 /// \param digraph The graph. It must be directed and acyclic. 1237 /// \retval order A readable - writable node map. The values will be set 1238 /// from 0 to the number of the nodes in the graph minus one. Each values 1239 /// of the map will be set exactly once, the values will be set descending 1240 /// order. 1241 /// \return \c false when the graph is not DAG. 1242 /// 1243 /// \see topologicalSort 1244 /// \see dag 1358 1245 template <typename Digraph, typename NodeMap> 1359 1246 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { … … 1397 1284 /// \ingroup graph_properties 1398 1285 /// 1399 /// \brief Check whether an undirected graph is acyclic. 1400 /// 1401 /// This function checks whether the given undirected graph is acyclic. 1402 /// \return \c true if there is no cycle in the graph. 1403 /// \see dag() 1286 /// \brief Check that the given directed graph is a DAG. 1287 /// 1288 /// Check that the given directed graph is a DAG. The DAG is 1289 /// an Directed Acyclic Digraph. 1290 /// \return \c false when the graph is not DAG. 1291 /// \see acyclic 1292 template <typename Digraph> 1293 bool dag(const Digraph& digraph) { 1294 1295 checkConcept<concepts::Digraph, Digraph>(); 1296 1297 typedef typename Digraph::Node Node; 1298 typedef typename Digraph::NodeIt NodeIt; 1299 typedef typename Digraph::Arc Arc; 1300 1301 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1302 1303 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1304 Create dfs(digraph); 1305 1306 ProcessedMap processed(digraph); 1307 dfs.processedMap(processed); 1308 1309 dfs.init(); 1310 for (NodeIt it(digraph); it != INVALID; ++it) { 1311 if (!dfs.reached(it)) { 1312 dfs.addSource(it); 1313 while (!dfs.emptyQueue()) { 1314 Arc edge = dfs.nextArc(); 1315 Node target = digraph.target(edge); 1316 if (dfs.reached(target) && !processed[target]) { 1317 return false; 1318 } 1319 dfs.processNextArc(); 1320 } 1321 } 1322 } 1323 return true; 1324 } 1325 1326 /// \ingroup graph_properties 1327 /// 1328 /// \brief Check that the given undirected graph is acyclic. 1329 /// 1330 /// Check that the given undirected graph acyclic. 1331 /// \param graph The undirected graph. 1332 /// \return \c true when there is no circle in the graph. 1333 /// \see dag 1404 1334 template <typename Graph> 1405 1335 bool acyclic(const Graph& graph) { … … 1414 1344 dfs.addSource(it); 1415 1345 while (!dfs.emptyQueue()) { 1416 Arc arc= dfs.nextArc();1417 Node source = graph.source( arc);1418 Node target = graph.target( arc);1346 Arc edge = dfs.nextArc(); 1347 Node source = graph.source(edge); 1348 Node target = graph.target(edge); 1419 1349 if (dfs.reached(target) && 1420 dfs.predArc(source) != graph.oppositeArc( arc)) {1350 dfs.predArc(source) != graph.oppositeArc(edge)) { 1421 1351 return false; 1422 1352 } … … 1430 1360 /// \ingroup graph_properties 1431 1361 /// 1432 /// \brief Check whether an undirected graph is tree.1433 /// 1434 /// This function checks whetherthe given undirected graph is tree.1435 /// \ return \c true if the graph is acyclic and connected.1436 /// \ see acyclic(), connected()1362 /// \brief Check that the given undirected graph is tree. 1363 /// 1364 /// Check that the given undirected graph is tree. 1365 /// \param graph The undirected graph. 1366 /// \return \c true when the graph is acyclic and connected. 1437 1367 template <typename Graph> 1438 1368 bool tree(const Graph& graph) { … … 1441 1371 typedef typename Graph::NodeIt NodeIt; 1442 1372 typedef typename Graph::Arc Arc; 1443 if (NodeIt(graph) == INVALID) return true;1444 1373 Dfs<Graph> dfs(graph); 1445 1374 dfs.init(); 1446 1375 dfs.addSource(NodeIt(graph)); 1447 1376 while (!dfs.emptyQueue()) { 1448 Arc arc= dfs.nextArc();1449 Node source = graph.source( arc);1450 Node target = graph.target( arc);1377 Arc edge = dfs.nextArc(); 1378 Node source = graph.source(edge); 1379 Node target = graph.target(edge); 1451 1380 if (dfs.reached(target) && 1452 dfs.predArc(source) != graph.oppositeArc( arc)) {1381 dfs.predArc(source) != graph.oppositeArc(edge)) { 1453 1382 return false; 1454 1383 } … … 1523 1452 /// \ingroup graph_properties 1524 1453 /// 1525 /// \brief Check whether an undirected graph is bipartite. 1526 /// 1527 /// The function checks whether the given undirected graph is bipartite. 1528 /// \return \c true if the graph is bipartite. 1529 /// 1530 /// \see bipartitePartitions() 1454 /// \brief Check if the given undirected graph is bipartite or not 1455 /// 1456 /// The function checks if the given undirected \c graph graph is bipartite 1457 /// or not. The \ref Bfs algorithm is used to calculate the result. 1458 /// \param graph The undirected graph. 1459 /// \return \c true if \c graph is bipartite, \c false otherwise. 1460 /// \sa bipartitePartitions 1531 1461 template<typename Graph> 1532 bool bipartite(const Graph &graph){1462 inline bool bipartite(const Graph &graph){ 1533 1463 using namespace _connectivity_bits; 1534 1464 … … 1559 1489 /// \ingroup graph_properties 1560 1490 /// 1561 /// \brief Find the bipartite partitions of an undirected graph. 1562 /// 1563 /// This function checks whether the given undirected graph is bipartite 1564 /// and gives back the bipartite partitions. 1491 /// \brief Check if the given undirected graph is bipartite or not 1492 /// 1493 /// The function checks if the given undirected graph is bipartite 1494 /// or not. The \ref Bfs algorithm is used to calculate the result. 1495 /// During the execution, the \c partMap will be set as the two 1496 /// partitions of the graph. 1565 1497 /// 1566 1498 /// \image html bipartite_partitions.png … … 1568 1500 /// 1569 1501 /// \param graph The undirected graph. 1570 /// \retval partMap A writable node map of \c bool (or convertible) value 1571 /// type. The values will be set to \c true for one component and 1572 /// \c false for the other one. 1573 /// \return \c true if the graph is bipartite, \c false otherwise. 1574 /// 1575 /// \see bipartite() 1502 /// \retval partMap A writable bool map of nodes. It will be set as the 1503 /// two partitions of the graph. 1504 /// \return \c true if \c graph is bipartite, \c false otherwise. 1576 1505 template<typename Graph, typename NodeMap> 1577 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){1506 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ 1578 1507 using namespace _connectivity_bits; 1579 1508 1580 1509 checkConcept<concepts::Graph, Graph>(); 1581 checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();1582 1510 1583 1511 typedef typename Graph::Node Node; … … 1604 1532 } 1605 1533 1606 /// \ingroup graph_properties 1607 /// 1608 /// \brief Check whether the given graph contains no loop arcs/edges. 1609 /// 1610 /// This function returns \c true if there are no loop arcs/edges in 1611 /// the given graph. It works for both directed and undirected graphs. 1612 template <typename Graph> 1613 bool loopFree(const Graph& graph) { 1614 for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { 1615 if (graph.source(it) == graph.target(it)) return false; 1534 /// \brief Returns true when there are not loop edges in the graph. 1535 /// 1536 /// Returns true when there are not loop edges in the graph. 1537 template <typename Digraph> 1538 bool loopFree(const Digraph& digraph) { 1539 for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { 1540 if (digraph.source(it) == digraph.target(it)) return false; 1616 1541 } 1617 1542 return true; 1618 1543 } 1619 1544 1620 /// \ingroup graph_properties 1621 /// 1622 /// \brief Check whether the given graph contains no parallel arcs/edges. 1623 /// 1624 /// This function returns \c true if there are no parallel arcs/edges in 1625 /// the given graph. It works for both directed and undirected graphs. 1626 template <typename Graph> 1627 bool parallelFree(const Graph& graph) { 1628 typename Graph::template NodeMap<int> reached(graph, 0); 1629 int cnt = 1; 1630 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1631 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1632 if (reached[graph.target(a)] == cnt) return false; 1633 reached[graph.target(a)] = cnt; 1634 } 1635 ++cnt; 1545 /// \brief Returns true when there are not parallel edges in the graph. 1546 /// 1547 /// Returns true when there are not parallel edges in the graph. 1548 template <typename Digraph> 1549 bool parallelFree(const Digraph& digraph) { 1550 typename Digraph::template NodeMap<bool> reached(digraph, false); 1551 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { 1552 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1553 if (reached[digraph.target(a)]) return false; 1554 reached.set(digraph.target(a), true); 1555 } 1556 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1557 reached.set(digraph.target(a), false); 1558 } 1636 1559 } 1637 1560 return true; 1638 1561 } 1639 1562 1640 /// \ingroup graph_properties 1641 /// 1642 /// \brief Check whether the given graph is simple. 1643 /// 1644 /// This function returns \c true if the given graph is simple, i.e. 1645 /// it contains no loop arcs/edges and no parallel arcs/edges. 1646 /// The function works for both directed and undirected graphs. 1647 /// \see loopFree(), parallelFree() 1648 template <typename Graph> 1649 bool simpleGraph(const Graph& graph) { 1650 typename Graph::template NodeMap<int> reached(graph, 0); 1651 int cnt = 1; 1652 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1653 reached[n] = cnt; 1654 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1655 if (reached[graph.target(a)] == cnt) return false; 1656 reached[graph.target(a)] = cnt; 1657 } 1658 ++cnt; 1563 /// \brief Returns true when there are not loop edges and parallel 1564 /// edges in the graph. 1565 /// 1566 /// Returns true when there are not loop edges and parallel edges in 1567 /// the graph. 1568 template <typename Digraph> 1569 bool simpleDigraph(const Digraph& digraph) { 1570 typename Digraph::template NodeMap<bool> reached(digraph, false); 1571 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { 1572 reached.set(n, true); 1573 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1574 if (reached[digraph.target(a)]) return false; 1575 reached.set(digraph.target(a), true); 1576 } 1577 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1578 reached.set(digraph.target(a), false); 1579 } 1580 reached.set(n, false); 1659 1581 } 1660 1582 return true;
Note: See TracChangeset
for help on using the changeset viewer.
