deba@1698: /* -*- C++ -*- deba@1698: * lemon/topology.h - Part of LEMON, a generic C++ optimization library deba@1698: * deba@1698: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1698: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1698: * deba@1698: * Permission to use, modify and distribute this software is granted deba@1698: * provided that this copyright notice appears in all copies. For deba@1698: * precise terms see the accompanying LICENSE file. deba@1698: * deba@1698: * This software is provided "AS IS" with no warranty of any kind, deba@1698: * express or implied, and with no claim as to its suitability for any deba@1698: * purpose. deba@1698: * deba@1698: */ deba@1698: deba@1698: #ifndef LEMON_TOPOLOGY_H deba@1698: #define LEMON_TOPOLOGY_H deba@1698: deba@1698: #include deba@1698: #include deba@1698: deba@1698: #include deba@1698: #include deba@1698: #include deba@1698: deba@1698: /// \ingroup flowalgs deba@1698: /// \file deba@1698: /// \brief Topology related algorithms deba@1698: /// deba@1698: /// Topology related algorithms deba@1698: deba@1698: namespace lemon { deba@1698: deba@1698: namespace _topology_bits { deba@1698: deba@1698: template deba@1698: class BackCounterMap { deba@1698: public: deba@1698: BackCounterMap(NodeMap& _nodeMap, int _counter) deba@1698: : nodeMap(_nodeMap), counter(_counter) {} deba@1698: deba@1698: void set(typename NodeMap::Key key, bool val) { deba@1698: if (val) { deba@1698: nodeMap.set(key, --counter); deba@1698: } else { deba@1698: nodeMap.set(key, -1); deba@1698: } deba@1698: } deba@1698: deba@1698: bool operator[](typename NodeMap::Key key) const { deba@1698: return nodeMap[key] != -1; deba@1698: } deba@1698: deba@1698: private: deba@1698: NodeMap& nodeMap; deba@1698: int counter; deba@1698: }; deba@1698: } deba@1698: deba@1698: // \todo Its to special output // ReadWriteMap deba@1698: template deba@1698: bool topological_sort(const Graph& graph, NodeMap& nodeMap) { deba@1698: using namespace _topology_bits; deba@1698: deba@1698: checkConcept(); deba@1698: checkConcept, NodeMap>(); deba@1698: deba@1698: typedef typename Graph::Node Node; deba@1698: typedef typename Graph::NodeIt NodeIt; deba@1698: typedef typename Graph::Edge Edge; deba@1698: deba@1698: typedef BackCounterMap ProcessedMap; deba@1698: deba@1698: typename Dfs::template DefProcessedMap:: deba@1709: Create dfs(graph); deba@1698: deba@1698: ProcessedMap processed(nodeMap, countNodes(graph)); deba@1698: deba@1698: dfs.processedMap(processed); deba@1698: dfs.init(); deba@1698: for (NodeIt it(graph); it != INVALID; ++it) { deba@1698: if (!dfs.reached(it)) { deba@1698: dfs.addSource(it); deba@1698: while (!dfs.emptyQueue()) { deba@1698: Edge edge = dfs.nextEdge(); deba@1698: Node target = graph.target(edge); deba@1698: if (dfs.reached(target) && !processed[target]) { deba@1698: return false; deba@1698: } deba@1698: dfs.processNextEdge(); deba@1698: } deba@1698: } deba@1698: } deba@1698: return true; deba@1698: } deba@1698: deba@1698: /// \brief Check that the given graph is a DAG. deba@1698: /// deba@1698: /// Check that the given graph is a DAG. The DAG is deba@1698: /// an Directed Acyclic Graph. deba@1698: template deba@1698: bool dag(const Graph& graph) { deba@1698: deba@1698: checkConcept(); deba@1698: deba@1698: typedef typename Graph::Node Node; deba@1698: typedef typename Graph::NodeIt NodeIt; deba@1698: typedef typename Graph::Edge Edge; deba@1698: deba@1698: typedef typename Graph::template NodeMap ProcessedMap; deba@1698: deba@1698: typename Dfs::template DefProcessedMap:: deba@1709: Create dfs(graph); deba@1698: deba@1698: ProcessedMap processed(graph); deba@1698: dfs.processedMap(processed); deba@1698: deba@1698: dfs.init(); deba@1698: for (NodeIt it(graph); it != INVALID; ++it) { deba@1698: if (!dfs.reached(it)) { deba@1698: dfs.addSource(it); deba@1698: while (!dfs.emptyQueue()) { deba@1698: Edge edge = dfs.nextEdge(); deba@1698: Node target = graph.target(edge); deba@1698: if (dfs.reached(target) && !processed[target]) { deba@1698: return false; deba@1698: } deba@1698: dfs.processNextEdge(); deba@1698: } deba@1698: } deba@1698: } deba@1698: return true; deba@1698: } deba@1698: deba@1698: // UndirGraph algorithms deba@1698: deba@1698: /// \brief Check that the given undirected graph is connected. deba@1698: /// deba@1698: /// Check that the given undirected graph connected. deba@1698: template deba@1698: bool connected(const UndirGraph& graph) { deba@1698: checkConcept(); deba@1698: typedef typename UndirGraph::NodeIt NodeIt; deba@1698: if (NodeIt(graph) == INVALID) return false; deba@1698: Dfs dfs(graph); deba@1698: dfs.run(NodeIt(graph)); deba@1698: for (NodeIt it(graph); it != INVALID; ++it) { deba@1698: if (!dfs.reached(it)) { deba@1698: return false; deba@1698: } deba@1698: } deba@1698: return true; deba@1698: } deba@1698: deba@1698: /// \brief Check that the given undirected graph is acyclic. deba@1698: /// deba@1698: /// Check that the given undirected graph acyclic. deba@1698: template deba@1698: bool acyclic(const UndirGraph& graph) { deba@1698: checkConcept(); deba@1698: typedef typename UndirGraph::Node Node; deba@1698: typedef typename UndirGraph::NodeIt NodeIt; deba@1698: typedef typename UndirGraph::Edge Edge; deba@1698: Dfs dfs(graph); deba@1698: dfs.init(); deba@1698: for (NodeIt it(graph); it != INVALID; ++it) { deba@1698: if (!dfs.reached(it)) { deba@1698: dfs.addSource(it); deba@1698: while (!dfs.emptyQueue()) { deba@1698: Edge edge = dfs.nextEdge(); deba@1698: Node source = graph.source(edge); deba@1698: Node target = graph.target(edge); deba@1698: if (dfs.reached(target) && deba@1698: dfs.pred(source) != graph.oppositeEdge(edge)) { deba@1698: return false; deba@1698: } deba@1698: dfs.processNextEdge(); deba@1698: } deba@1698: } deba@1698: } deba@1698: return true; deba@1698: } deba@1698: deba@1698: /// \brief Check that the given undirected graph is tree. deba@1698: /// deba@1698: /// Check that the given undirected graph is tree. deba@1698: template deba@1698: bool tree(const UndirGraph& graph) { deba@1698: checkConcept(); deba@1698: typedef typename UndirGraph::Node Node; deba@1698: typedef typename UndirGraph::NodeIt NodeIt; deba@1698: typedef typename UndirGraph::Edge Edge; deba@1698: if (NodeIt(graph) == INVALID) return false; deba@1698: Dfs dfs(graph); deba@1698: dfs.init(); deba@1698: dfs.addSource(NodeIt(graph)); deba@1698: while (!dfs.emptyQueue()) { deba@1698: Edge edge = dfs.nextEdge(); deba@1698: Node source = graph.source(edge); deba@1698: Node target = graph.target(edge); deba@1698: if (dfs.reached(target) && deba@1698: dfs.pred(source) != graph.oppositeEdge(edge)) { deba@1698: return false; deba@1698: } deba@1698: dfs.processNextEdge(); deba@1698: } deba@1698: for (NodeIt it(graph); it != INVALID; ++it) { deba@1698: if (!dfs.reached(it)) { deba@1698: return false; deba@1698: } deba@1698: } deba@1698: return true; deba@1698: } deba@1698: deba@1698: deba@1698: } //namespace lemon deba@1698: deba@1698: #endif //LEMON_TOPOLOGY_H