# HG changeset patch
# User deba
# Date 1128334718 0
# Node ID 755cdc461ddd3bf6134e5ab3f71aaf8c37aa288d
# Parent  4c593a4096dab1961cdb42a0463e1d9afa6b6c27
Small functions for discovering graph topology

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