23 #include <lemon/bfs.h> |
23 #include <lemon/bfs.h> |
24 #include <lemon/graph_utils.h> |
24 #include <lemon/graph_utils.h> |
25 #include <lemon/graph_adaptor.h> |
25 #include <lemon/graph_adaptor.h> |
26 #include <lemon/maps.h> |
26 #include <lemon/maps.h> |
27 |
27 |
28 #include <lemon/concept/graph.h> |
28 #include <lemon/concepts/graph.h> |
29 #include <lemon/concept/ugraph.h> |
29 #include <lemon/concepts/ugraph.h> |
30 #include <lemon/concept_check.h> |
30 #include <lemon/concept_check.h> |
31 |
31 |
32 #include <lemon/bin_heap.h> |
32 #include <lemon/bin_heap.h> |
33 #include <lemon/bucket_heap.h> |
33 #include <lemon/bucket_heap.h> |
34 |
34 |
51 /// \param graph The undirected graph. |
51 /// \param graph The undirected graph. |
52 /// \return %True when there is path between any two nodes in the graph. |
52 /// \return %True when there is path between any two nodes in the graph. |
53 /// \note By definition, the empty graph is connected. |
53 /// \note By definition, the empty graph is connected. |
54 template <typename UGraph> |
54 template <typename UGraph> |
55 bool connected(const UGraph& graph) { |
55 bool connected(const UGraph& graph) { |
56 checkConcept<concept::UGraph, UGraph>(); |
56 checkConcept<concepts::UGraph, UGraph>(); |
57 typedef typename UGraph::NodeIt NodeIt; |
57 typedef typename UGraph::NodeIt NodeIt; |
58 if (NodeIt(graph) == INVALID) return true; |
58 if (NodeIt(graph) == INVALID) return true; |
59 Dfs<UGraph> dfs(graph); |
59 Dfs<UGraph> dfs(graph); |
60 dfs.run(NodeIt(graph)); |
60 dfs.run(NodeIt(graph)); |
61 for (NodeIt it(graph); it != INVALID; ++it) { |
61 for (NodeIt it(graph); it != INVALID; ++it) { |
76 /// \return The number of components |
76 /// \return The number of components |
77 /// \note By definition, the empty graph consists |
77 /// \note By definition, the empty graph consists |
78 /// of zero connected components. |
78 /// of zero connected components. |
79 template <typename UGraph> |
79 template <typename UGraph> |
80 int countConnectedComponents(const UGraph &graph) { |
80 int countConnectedComponents(const UGraph &graph) { |
81 checkConcept<concept::UGraph, UGraph>(); |
81 checkConcept<concepts::UGraph, UGraph>(); |
82 typedef typename UGraph::Node Node; |
82 typedef typename UGraph::Node Node; |
83 typedef typename UGraph::Edge Edge; |
83 typedef typename UGraph::Edge Edge; |
84 |
84 |
85 typedef NullMap<Node, Edge> PredMap; |
85 typedef NullMap<Node, Edge> PredMap; |
86 typedef NullMap<Node, int> DistMap; |
86 typedef NullMap<Node, int> DistMap; |
124 /// set continuously. |
124 /// set continuously. |
125 /// \return The number of components |
125 /// \return The number of components |
126 /// |
126 /// |
127 template <class UGraph, class NodeMap> |
127 template <class UGraph, class NodeMap> |
128 int connectedComponents(const UGraph &graph, NodeMap &compMap) { |
128 int connectedComponents(const UGraph &graph, NodeMap &compMap) { |
129 checkConcept<concept::UGraph, UGraph>(); |
129 checkConcept<concepts::UGraph, UGraph>(); |
130 typedef typename UGraph::Node Node; |
130 typedef typename UGraph::Node Node; |
131 typedef typename UGraph::Edge Edge; |
131 typedef typename UGraph::Edge Edge; |
132 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
132 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); |
133 |
133 |
134 typedef NullMap<Node, Edge> PredMap; |
134 typedef NullMap<Node, Edge> PredMap; |
135 typedef NullMap<Node, int> DistMap; |
135 typedef NullMap<Node, int> DistMap; |
136 |
136 |
137 int compNum = 0; |
137 int compNum = 0; |
242 /// \see connected |
242 /// \see connected |
243 /// |
243 /// |
244 /// \note By definition, the empty graph is strongly connected. |
244 /// \note By definition, the empty graph is strongly connected. |
245 template <typename Graph> |
245 template <typename Graph> |
246 bool stronglyConnected(const Graph& graph) { |
246 bool stronglyConnected(const Graph& graph) { |
247 checkConcept<concept::Graph, Graph>(); |
247 checkConcept<concepts::Graph, Graph>(); |
248 |
248 |
249 typedef typename Graph::Node Node; |
249 typedef typename Graph::Node Node; |
250 typedef typename Graph::NodeIt NodeIt; |
250 typedef typename Graph::NodeIt NodeIt; |
251 |
251 |
252 if (NodeIt(graph) == INVALID) return true; |
252 if (NodeIt(graph) == INVALID) return true; |
300 /// \return The number of components |
300 /// \return The number of components |
301 /// \note By definition, the empty graph has zero |
301 /// \note By definition, the empty graph has zero |
302 /// strongly connected components. |
302 /// strongly connected components. |
303 template <typename Graph> |
303 template <typename Graph> |
304 int countStronglyConnectedComponents(const Graph& graph) { |
304 int countStronglyConnectedComponents(const Graph& graph) { |
305 checkConcept<concept::Graph, Graph>(); |
305 checkConcept<concepts::Graph, Graph>(); |
306 |
306 |
307 using namespace _topology_bits; |
307 using namespace _topology_bits; |
308 |
308 |
309 typedef typename Graph::Node Node; |
309 typedef typename Graph::Node Node; |
310 typedef typename Graph::Edge Edge; |
310 typedef typename Graph::Edge Edge; |
369 /// will be set continuously. |
369 /// will be set continuously. |
370 /// \return The number of components |
370 /// \return The number of components |
371 /// |
371 /// |
372 template <typename Graph, typename NodeMap> |
372 template <typename Graph, typename NodeMap> |
373 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { |
373 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { |
374 checkConcept<concept::Graph, Graph>(); |
374 checkConcept<concepts::Graph, Graph>(); |
375 typedef typename Graph::Node Node; |
375 typedef typename Graph::Node Node; |
376 typedef typename Graph::NodeIt NodeIt; |
376 typedef typename Graph::NodeIt NodeIt; |
377 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
377 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); |
378 |
378 |
379 using namespace _topology_bits; |
379 using namespace _topology_bits; |
380 |
380 |
381 typedef std::vector<Node> Container; |
381 typedef std::vector<Node> Container; |
382 typedef typename Container::iterator Iterator; |
382 typedef typename Container::iterator Iterator; |
432 /// edge is a cut edge. |
432 /// edge is a cut edge. |
433 /// |
433 /// |
434 /// \return The number of cut edges |
434 /// \return The number of cut edges |
435 template <typename Graph, typename EdgeMap> |
435 template <typename Graph, typename EdgeMap> |
436 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { |
436 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { |
437 checkConcept<concept::Graph, Graph>(); |
437 checkConcept<concepts::Graph, Graph>(); |
438 typedef typename Graph::Node Node; |
438 typedef typename Graph::Node Node; |
439 typedef typename Graph::Edge Edge; |
439 typedef typename Graph::Edge Edge; |
440 typedef typename Graph::NodeIt NodeIt; |
440 typedef typename Graph::NodeIt NodeIt; |
441 checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>(); |
441 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>(); |
442 |
442 |
443 using namespace _topology_bits; |
443 using namespace _topology_bits; |
444 |
444 |
445 typedef std::vector<Node> Container; |
445 typedef std::vector<Node> Container; |
446 typedef typename Container::iterator Iterator; |
446 typedef typename Container::iterator Iterator; |
728 /// |
728 /// |
729 /// \param graph The graph. |
729 /// \param graph The graph. |
730 /// \return The number of components. |
730 /// \return The number of components. |
731 template <typename UGraph> |
731 template <typename UGraph> |
732 int countBiNodeConnectedComponents(const UGraph& graph) { |
732 int countBiNodeConnectedComponents(const UGraph& graph) { |
733 checkConcept<concept::UGraph, UGraph>(); |
733 checkConcept<concepts::UGraph, UGraph>(); |
734 typedef typename UGraph::NodeIt NodeIt; |
734 typedef typename UGraph::NodeIt NodeIt; |
735 |
735 |
736 using namespace _topology_bits; |
736 using namespace _topology_bits; |
737 |
737 |
738 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor; |
738 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor; |
772 /// \return The number of components. |
772 /// \return The number of components. |
773 /// |
773 /// |
774 template <typename UGraph, typename UEdgeMap> |
774 template <typename UGraph, typename UEdgeMap> |
775 int biNodeConnectedComponents(const UGraph& graph, |
775 int biNodeConnectedComponents(const UGraph& graph, |
776 UEdgeMap& compMap) { |
776 UEdgeMap& compMap) { |
777 checkConcept<concept::UGraph, UGraph>(); |
777 checkConcept<concepts::UGraph, UGraph>(); |
778 typedef typename UGraph::NodeIt NodeIt; |
778 typedef typename UGraph::NodeIt NodeIt; |
779 typedef typename UGraph::UEdge UEdge; |
779 typedef typename UGraph::UEdge UEdge; |
780 checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>(); |
780 checkConcept<concepts::WriteMap<UEdge, int>, UEdgeMap>(); |
781 |
781 |
782 using namespace _topology_bits; |
782 using namespace _topology_bits; |
783 |
783 |
784 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor; |
784 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor; |
785 |
785 |
812 /// \retval cutMap A writable edge map. The values will be set true when |
812 /// \retval cutMap A writable edge map. The values will be set true when |
813 /// the node separate two or more components. |
813 /// the node separate two or more components. |
814 /// \return The number of the cut nodes. |
814 /// \return The number of the cut nodes. |
815 template <typename UGraph, typename NodeMap> |
815 template <typename UGraph, typename NodeMap> |
816 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) { |
816 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) { |
817 checkConcept<concept::UGraph, UGraph>(); |
817 checkConcept<concepts::UGraph, UGraph>(); |
818 typedef typename UGraph::Node Node; |
818 typedef typename UGraph::Node Node; |
819 typedef typename UGraph::NodeIt NodeIt; |
819 typedef typename UGraph::NodeIt NodeIt; |
820 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); |
820 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>(); |
821 |
821 |
822 using namespace _topology_bits; |
822 using namespace _topology_bits; |
823 |
823 |
824 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor; |
824 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor; |
825 |
825 |
1055 /// |
1055 /// |
1056 /// \param graph The undirected graph. |
1056 /// \param graph The undirected graph. |
1057 /// \return The number of components. |
1057 /// \return The number of components. |
1058 template <typename UGraph> |
1058 template <typename UGraph> |
1059 int countBiEdgeConnectedComponents(const UGraph& graph) { |
1059 int countBiEdgeConnectedComponents(const UGraph& graph) { |
1060 checkConcept<concept::UGraph, UGraph>(); |
1060 checkConcept<concepts::UGraph, UGraph>(); |
1061 typedef typename UGraph::NodeIt NodeIt; |
1061 typedef typename UGraph::NodeIt NodeIt; |
1062 |
1062 |
1063 using namespace _topology_bits; |
1063 using namespace _topology_bits; |
1064 |
1064 |
1065 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor; |
1065 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor; |
1098 /// will be set continuously. |
1098 /// will be set continuously. |
1099 /// \return The number of components. |
1099 /// \return The number of components. |
1100 /// |
1100 /// |
1101 template <typename UGraph, typename NodeMap> |
1101 template <typename UGraph, typename NodeMap> |
1102 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { |
1102 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { |
1103 checkConcept<concept::UGraph, UGraph>(); |
1103 checkConcept<concepts::UGraph, UGraph>(); |
1104 typedef typename UGraph::NodeIt NodeIt; |
1104 typedef typename UGraph::NodeIt NodeIt; |
1105 typedef typename UGraph::Node Node; |
1105 typedef typename UGraph::Node Node; |
1106 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
1106 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); |
1107 |
1107 |
1108 using namespace _topology_bits; |
1108 using namespace _topology_bits; |
1109 |
1109 |
1110 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor; |
1110 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor; |
1111 |
1111 |
1139 /// \retval cutMap A writable node map. The values will be set true when the |
1139 /// \retval cutMap A writable node map. The values will be set true when the |
1140 /// edge is a cut edge. |
1140 /// edge is a cut edge. |
1141 /// \return The number of cut edges. |
1141 /// \return The number of cut edges. |
1142 template <typename UGraph, typename UEdgeMap> |
1142 template <typename UGraph, typename UEdgeMap> |
1143 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { |
1143 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { |
1144 checkConcept<concept::UGraph, UGraph>(); |
1144 checkConcept<concepts::UGraph, UGraph>(); |
1145 typedef typename UGraph::NodeIt NodeIt; |
1145 typedef typename UGraph::NodeIt NodeIt; |
1146 typedef typename UGraph::UEdge UEdge; |
1146 typedef typename UGraph::UEdge UEdge; |
1147 checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>(); |
1147 checkConcept<concepts::WriteMap<UEdge, bool>, UEdgeMap>(); |
1148 |
1148 |
1149 using namespace _topology_bits; |
1149 using namespace _topology_bits; |
1150 |
1150 |
1151 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor; |
1151 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor; |
1152 |
1152 |
1203 /// \see dag |
1203 /// \see dag |
1204 template <typename Graph, typename NodeMap> |
1204 template <typename Graph, typename NodeMap> |
1205 void topologicalSort(const Graph& graph, NodeMap& order) { |
1205 void topologicalSort(const Graph& graph, NodeMap& order) { |
1206 using namespace _topology_bits; |
1206 using namespace _topology_bits; |
1207 |
1207 |
1208 checkConcept<concept::Graph, Graph>(); |
1208 checkConcept<concepts::Graph, Graph>(); |
1209 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>(); |
1209 checkConcept<concepts::WriteMap<typename Graph::Node, int>, NodeMap>(); |
1210 |
1210 |
1211 typedef typename Graph::Node Node; |
1211 typedef typename Graph::Node Node; |
1212 typedef typename Graph::NodeIt NodeIt; |
1212 typedef typename Graph::NodeIt NodeIt; |
1213 typedef typename Graph::Edge Edge; |
1213 typedef typename Graph::Edge Edge; |
1214 |
1214 |
1245 /// \see dag |
1245 /// \see dag |
1246 template <typename Graph, typename NodeMap> |
1246 template <typename Graph, typename NodeMap> |
1247 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) { |
1247 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) { |
1248 using namespace _topology_bits; |
1248 using namespace _topology_bits; |
1249 |
1249 |
1250 checkConcept<concept::Graph, Graph>(); |
1250 checkConcept<concepts::Graph, Graph>(); |
1251 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>(); |
1251 checkConcept<concepts::ReadWriteMap<typename Graph::Node, int>, NodeMap>(); |
1252 |
1252 |
1253 typedef typename Graph::Node Node; |
1253 typedef typename Graph::Node Node; |
1254 typedef typename Graph::NodeIt NodeIt; |
1254 typedef typename Graph::NodeIt NodeIt; |
1255 typedef typename Graph::Edge Edge; |
1255 typedef typename Graph::Edge Edge; |
1256 |
1256 |
1288 /// \return %False when the graph is not DAG. |
1288 /// \return %False when the graph is not DAG. |
1289 /// \see acyclic |
1289 /// \see acyclic |
1290 template <typename Graph> |
1290 template <typename Graph> |
1291 bool dag(const Graph& graph) { |
1291 bool dag(const Graph& graph) { |
1292 |
1292 |
1293 checkConcept<concept::Graph, Graph>(); |
1293 checkConcept<concepts::Graph, Graph>(); |
1294 |
1294 |
1295 typedef typename Graph::Node Node; |
1295 typedef typename Graph::Node Node; |
1296 typedef typename Graph::NodeIt NodeIt; |
1296 typedef typename Graph::NodeIt NodeIt; |
1297 typedef typename Graph::Edge Edge; |
1297 typedef typename Graph::Edge Edge; |
1298 |
1298 |
1329 /// \param graph The undirected graph. |
1329 /// \param graph The undirected graph. |
1330 /// \return %True when there is no circle in the graph. |
1330 /// \return %True when there is no circle in the graph. |
1331 /// \see dag |
1331 /// \see dag |
1332 template <typename UGraph> |
1332 template <typename UGraph> |
1333 bool acyclic(const UGraph& graph) { |
1333 bool acyclic(const UGraph& graph) { |
1334 checkConcept<concept::UGraph, UGraph>(); |
1334 checkConcept<concepts::UGraph, UGraph>(); |
1335 typedef typename UGraph::Node Node; |
1335 typedef typename UGraph::Node Node; |
1336 typedef typename UGraph::NodeIt NodeIt; |
1336 typedef typename UGraph::NodeIt NodeIt; |
1337 typedef typename UGraph::Edge Edge; |
1337 typedef typename UGraph::Edge Edge; |
1338 Dfs<UGraph> dfs(graph); |
1338 Dfs<UGraph> dfs(graph); |
1339 dfs.init(); |
1339 dfs.init(); |
1362 /// Check that the given undirected graph is tree. |
1362 /// Check that the given undirected graph is tree. |
1363 /// \param graph The undirected graph. |
1363 /// \param graph The undirected graph. |
1364 /// \return %True when the graph is acyclic and connected. |
1364 /// \return %True when the graph is acyclic and connected. |
1365 template <typename UGraph> |
1365 template <typename UGraph> |
1366 bool tree(const UGraph& graph) { |
1366 bool tree(const UGraph& graph) { |
1367 checkConcept<concept::UGraph, UGraph>(); |
1367 checkConcept<concepts::UGraph, UGraph>(); |
1368 typedef typename UGraph::Node Node; |
1368 typedef typename UGraph::Node Node; |
1369 typedef typename UGraph::NodeIt NodeIt; |
1369 typedef typename UGraph::NodeIt NodeIt; |
1370 typedef typename UGraph::Edge Edge; |
1370 typedef typename UGraph::Edge Edge; |
1371 Dfs<UGraph> dfs(graph); |
1371 Dfs<UGraph> dfs(graph); |
1372 dfs.init(); |
1372 dfs.init(); |
1400 /// \sa bipartitePartitions |
1400 /// \sa bipartitePartitions |
1401 /// |
1401 /// |
1402 /// \author Balazs Attila Mihaly |
1402 /// \author Balazs Attila Mihaly |
1403 template<typename UGraph> |
1403 template<typename UGraph> |
1404 inline bool bipartite(const UGraph &graph){ |
1404 inline bool bipartite(const UGraph &graph){ |
1405 checkConcept<concept::UGraph, UGraph>(); |
1405 checkConcept<concepts::UGraph, UGraph>(); |
1406 |
1406 |
1407 typedef typename UGraph::NodeIt NodeIt; |
1407 typedef typename UGraph::NodeIt NodeIt; |
1408 typedef typename UGraph::EdgeIt EdgeIt; |
1408 typedef typename UGraph::EdgeIt EdgeIt; |
1409 |
1409 |
1410 Bfs<UGraph> bfs(graph); |
1410 Bfs<UGraph> bfs(graph); |
1437 /// |
1437 /// |
1438 /// \image html bipartite_partitions.png |
1438 /// \image html bipartite_partitions.png |
1439 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
1439 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
1440 template<typename UGraph, typename NodeMap> |
1440 template<typename UGraph, typename NodeMap> |
1441 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ |
1441 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ |
1442 checkConcept<concept::UGraph, UGraph>(); |
1442 checkConcept<concepts::UGraph, UGraph>(); |
1443 |
1443 |
1444 typedef typename UGraph::Node Node; |
1444 typedef typename UGraph::Node Node; |
1445 typedef typename UGraph::NodeIt NodeIt; |
1445 typedef typename UGraph::NodeIt NodeIt; |
1446 typedef typename UGraph::EdgeIt EdgeIt; |
1446 typedef typename UGraph::EdgeIt EdgeIt; |
1447 |
1447 |