# HG changeset patch
# User marci
# Date 1083931054 0
# Node ID e8703f0a6e2fb5c24c2c5ef0a4908b85e3aeaa3d
# Parent  d00c33d07114ad74fb52edc4358d36a81a68ee75
top-sort, dimacs mods.

diff -r d00c33d07114 -r e8703f0a6e2f src/work/makefile
--- a/src/work/makefile	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/makefile	Fri May 07 11:57:34 2004 +0000
@@ -1,5 +1,5 @@
 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
-CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
 
 BINARIES ?= bin_heap_demo
 
diff -r d00c33d07114 -r e8703f0a6e2f src/work/marci/bfs_dfs_misc.h
--- a/src/work/marci/bfs_dfs_misc.h	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/marci/bfs_dfs_misc.h	Fri May 07 11:57:34 2004 +0000
@@ -39,24 +39,47 @@
   /// experimental topsort, 
   /// I think the final version will work as an iterator
   /// if the graph is not a acyclic, the na pre-topological order is obtained 
-  /// (see Schrijver's book)
-  template<typename Graph> 
-  void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
+  /// (see Schrijver's book).
+  /// PredMap have to be a writtable node-map.
+  /// If the graph is directed and not acyclic, 
+  /// then going back from the returned node via the pred information, a 
+  /// cycle is obtained.
+  template<typename Graph, typename PredMap> 
+  typename Graph::Node 
+  topSort(const Graph& g, std::list<typename Graph::Node>& l, 
+	       PredMap& pred) {
     l.clear();
     typedef typename Graph::template NodeMap<bool> ReachedMap;
+    typedef typename Graph::template NodeMap<bool> ExaminedMap;    
     ReachedMap reached(g/*, false*/);
+    ExaminedMap examined(g/*, false*/);
     DfsIterator<Graph, ReachedMap> dfs(g, reached);
     FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
       if (!reached[n]) {
 	dfs.pushAndSetReached(n);
+	pred.set(n, INVALID);
 	while (!dfs.finished()) {
 	  ++dfs;
+	  if (dfs.isBNodeNewlyReached()) {
+	    ///\bug hugo 0.2-ben Edge kell
+	    pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
+	  } else {
+	    ///\bug ugyanaz
+	    if (g.valid(typename Graph::OutEdgeIt(dfs)) && 
+		!examined[dfs.bNode()]) {
+	      ///\bug hugo 0.2-ben Edge kell
+	      pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
+	      return dfs.aNode();
+	    }
+	  }
 	  if (dfs.isANodeExamined()) {
 	    l.push_back(dfs.aNode());
+	    examined.set(dfs.aNode(), true);
 	  }
 	}
       }
     }
+    return INVALID;
   }
 } //namespace hugo
 
diff -r d00c33d07114 -r e8703f0a6e2f src/work/marci/bfsit_vs_byhand.cc
--- a/src/work/marci/bfsit_vs_byhand.cc	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/marci/bfsit_vs_byhand.cc	Fri May 07 11:57:34 2004 +0000
@@ -19,15 +19,17 @@
   typedef Graph::EdgeIt EdgeIt;
   typedef Graph::OutEdgeIt OutEdgeIt;
 
-  Graph G;
+  Graph g;
   Node s, t;
-  Graph::EdgeMap<int> cap(G);
-  readDimacsMaxFlow(std::cin, G, s, t, cap);
-  Graph::NodeMap<OutEdgeIt> pred(G);
+  Graph::EdgeMap<int> cap(g);
+  //readDimacsMaxFlow(std::cin, g, s, t, cap);
+  readDimacs(std::cin, g);
+
+  Graph::NodeMap<OutEdgeIt> pred(g);
   Timer ts;
   {
     ts.reset();
-    Graph::NodeMap<bool> reached(G);
+    Graph::NodeMap<bool> reached(g);
     reached.set(s, true);
     pred.set(s, INVALID);
     std::queue<Node> bfs_queue;
@@ -36,8 +38,8 @@
       Node v=bfs_queue.front();	
       bfs_queue.pop();
       OutEdgeIt e;
-      for(G.first(e,v); G.valid(e); G.next(e)) {
-	Node w=G.head(e);
+      for(g.first(e,v); g.valid(e); g.next(e)) {
+	Node w=g.head(e);
 	if (!reached[w]) {
 	  bfs_queue.push(w);
 	  reached.set(w, true);
@@ -51,12 +53,12 @@
 
   {
     ts.reset();      
-    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
+    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
     bfs.pushAndSetReached(s);
     pred.set(s, INVALID);
     while (!bfs.finished()) { 
       ++bfs; 
-      if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
+      if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
 	pred.set(bfs.bNode(), bfs);
     }
     std::cout << ts << std::endl;
diff -r d00c33d07114 -r e8703f0a6e2f src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/marci/lg_vs_sg.cc	Fri May 07 11:57:34 2004 +0000
@@ -25,16 +25,17 @@
     typedef Graph::Node Node;
     typedef Graph::EdgeIt EdgeIt;
 
-    Graph G;
+    Graph g;
     Node s, t;
-    Graph::EdgeMap<int> cap(G);
+    Graph::EdgeMap<int> cap(g);
     std::ifstream ins(in.c_str());
-    readDimacsMaxFlow(ins, G, s, t, cap);
+    //readDimacsMaxFlow(ins, g, s, t, cap);
+    readDimacs(ins, g, cap, s, t);
 
     Timer ts;
-    Graph::EdgeMap<int> flow(G); //0 flow
+    Graph::EdgeMap<int> flow(g); //0 flow
     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow/*, true*/);
+      max_flow_test(g, s, t, cap, flow/*, true*/);
 
     std::cout << "ListGraph ..." << std::endl;
 
@@ -48,7 +49,7 @@
 
     {
       std::cout << "physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       int i=0;
       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -59,7 +60,7 @@
 
 //     {
 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
-//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 //       ts.reset();
 //       int i=0;
 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
@@ -70,7 +71,7 @@
 
     {
       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       int i=0;
       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -81,7 +82,7 @@
 
     {
       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       int i=0;
       while (max_flow_test.augmentOnShortestPath()) { ++i; }
@@ -97,24 +98,25 @@
     typedef Graph::Node Node;
     typedef Graph::EdgeIt EdgeIt;
 
-    Graph G;
+    Graph g;
     Node s, t;
-    Graph::EdgeMap<int> cap(G);
+    Graph::EdgeMap<int> cap(g);
     std::ifstream ins(in.c_str());
-    readDimacsMaxFlow(ins, G, s, t, cap);
+    //readDimacsMaxFlow(ins, g, s, t, cap);
+    readDimacs(ins, g, cap, s, t);
 
     Timer ts;
-    Graph::EdgeMap<int> flow(G); //0 flow
+    Graph::EdgeMap<int> flow(g); //0 flow
     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow/*, true*/);
+      max_flow_test(g, s, t, cap, flow/*, true*/);
     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-    //  max_flow_test(G, s, t, cap, flow);
+    //  max_flow_test(g, s, t, cap, flow);
 
     std::cout << "SmatrGraph ..." << std::endl;
 
     {
       std::cout << "preflow ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       max_flow_test.run();
       std::cout << "elapsed time: " << ts << std::endl;
@@ -123,7 +125,7 @@
 
     {
       std::cout << "physical blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       int i=0;
       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -134,7 +136,7 @@
 
 //     {
 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
-//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 //       ts.reset();
 //       int i=0;
 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
@@ -145,7 +147,7 @@
 
     {
       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       int i=0;
       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -156,7 +158,7 @@
 
     {
       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
       ts.reset();
       int i=0;
       while (max_flow_test.augmentOnShortestPath()) { ++i; }
diff -r d00c33d07114 -r e8703f0a6e2f src/work/marci/max_flow_demo.cc
--- a/src/work/marci/max_flow_demo.cc	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/marci/max_flow_demo.cc	Fri May 07 11:57:34 2004 +0000
@@ -63,14 +63,15 @@
 //   std::cout << sizeof(Bumm) << std::endl;
 
 
-  Graph G;
+  Graph g;
   Node s, t;
-  Graph::EdgeMap<int> cap(G);
-  readDimacsMaxFlow(std::cin, G, s, t, cap);
+  Graph::EdgeMap<int> cap(g);
+  //readDimacsMaxFlow(std::cin, g, s, t, cap);
+  readDimacs(std::cin, g, cap, s, t);
   Timer ts;
-  Graph::EdgeMap<int> flow(G); //0 flow
+  Graph::EdgeMap<int> flow(g); //0 flow
   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-    max_flow_test(G, s, t, cap, flow);
+    max_flow_test(g, s, t, cap, flow);
 
   {
     std::cout << "preflow ..." << std::endl;
@@ -82,7 +83,7 @@
 
   {
     std::cout << "preflow ..." << std::endl;
-    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     ts.reset();
     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
     std::cout << "elapsed time: " << ts << std::endl;
@@ -91,7 +92,7 @@
 
 //   {
 //     std::cout << "wrapped preflow ..." << std::endl;
-//     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 //     ts.reset();
 //     pre_flow_res.run();
 //     std::cout << "elapsed time: " << ts << std::endl;
@@ -100,7 +101,7 @@
 
   {
     std::cout << "physical blocking flow augmentation ..." << std::endl;
-    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     ts.reset();
     int i=0;
     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
@@ -111,7 +112,7 @@
 
 //   {
 //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
-//     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 //     ts.reset();
 //     int i=0;
 //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
@@ -122,7 +123,7 @@
 
   {
     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     ts.reset();
     int i=0;
     while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
@@ -133,7 +134,7 @@
 
   {
     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     ts.reset();
     int i=0;
     while (max_flow_test.augmentOnShortestPath()) { ++i; }
diff -r d00c33d07114 -r e8703f0a6e2f src/work/marci/top_sort.dim
--- a/src/work/marci/top_sort.dim	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/marci/top_sort.dim	Fri May 07 11:57:34 2004 +0000
@@ -2,5 +2,5 @@
 a 1 3
 a 2 3
 a 3 5
-a 3 4
+a 4 3
 a 5 4
\ No newline at end of file
diff -r d00c33d07114 -r e8703f0a6e2f src/work/marci/top_sort_test.cc
--- a/src/work/marci/top_sort_test.cc	Fri May 07 10:57:31 2004 +0000
+++ b/src/work/marci/top_sort_test.cc	Fri May 07 11:57:34 2004 +0000
@@ -7,6 +7,7 @@
 #include <bfs_dfs_misc.h>
 #include <list_graph.h>
 #include <hugo/graph_wrapper.h>
+#include <hugo/maps.h>
 
 using namespace hugo;
 
@@ -16,7 +17,8 @@
   readDimacs(std::cin, g); 
   {
     std::list<Graph::Node> l;
-    topSort(g, l);
+    NullMap<Graph::Node, Graph::Edge> pred;
+    topSort(g, l, pred);
     std::cout << "Leaving order of dfs which is pretopological..." << std::endl;
     for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
       std::cout << *i << " ";
@@ -28,7 +30,8 @@
     typedef RevGraphWrapper<Graph> GW;
     GW gw(g);
     std::list<GW::Node> l;
-    topSort(gw, l);
+    NullMap<GW::Node, GW::Edge> pred;
+    topSort(gw, l, pred);
     std::cout << "Same in the revered oriented graph..." << std::endl;
     for(std::list<GW::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
       std::cout << *i << " ";