equal
deleted
inserted
replaced
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::StaticGraph, Graph>(); |
247 checkConcept<concept::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::StaticGraph, Graph>(); |
305 checkConcept<concept::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::StaticGraph, Graph>(); |
374 checkConcept<concept::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<concept::WriteMap<Node, int>, NodeMap>(); |
378 |
378 |
379 using namespace _topology_bits; |
379 using namespace _topology_bits; |
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::StaticGraph, Graph>(); |
437 checkConcept<concept::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<concept::WriteMap<Edge, bool>, EdgeMap>(); |
442 |
442 |
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::StaticGraph, Graph>(); |
1208 checkConcept<concept::Graph, Graph>(); |
1209 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>(); |
1209 checkConcept<concept::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; |
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::StaticGraph, Graph>(); |
1250 checkConcept<concept::Graph, Graph>(); |
1251 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>(); |
1251 checkConcept<concept::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; |
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::StaticGraph, Graph>(); |
1293 checkConcept<concept::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 |