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 <lemon/dfs.h>
deba@1698: #include <lemon/graph_utils.h>
deba@1698: 
deba@1698: #include <lemon/concept/graph.h>
deba@1698: #include <lemon/concept/undir_graph.h>
deba@1698: #include <lemon/concept_check.h>
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 <typename NodeMap>
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 <typename Graph, typename NodeMap>
deba@1698:   bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
deba@1698:     using namespace _topology_bits;
deba@1698: 
deba@1698:     checkConcept<concept::StaticGraph, Graph>();
deba@1698:     checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, 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<NodeMap> ProcessedMap;
deba@1698: 
deba@1698:     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
deba@1698:       Dfs 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 <typename Graph>
deba@1698:   bool dag(const Graph& graph) {
deba@1698: 
deba@1698:     checkConcept<concept::StaticGraph, Graph>();
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<bool> ProcessedMap;
deba@1698: 
deba@1698:     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
deba@1698:       Dfs 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 <typename UndirGraph>
deba@1698:   bool connected(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     if (NodeIt(graph) == INVALID) return false;
deba@1698:     Dfs<UndirGraph> 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 <typename UndirGraph>
deba@1698:   bool acyclic(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::Node Node;
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     typedef typename UndirGraph::Edge Edge;
deba@1698:     Dfs<UndirGraph> 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 <typename UndirGraph>
deba@1698:   bool tree(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
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<UndirGraph> 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