1.1 --- a/src/hugo/dimacs.h	Thu May 06 14:25:21 2004 +0000
     1.2 +++ b/src/hugo/dimacs.h	Thu May 06 15:10:48 2004 +0000
     1.3 @@ -77,7 +77,6 @@
     1.4      typename Graph::Node u;
     1.5      NullMap<typename Graph::Edge, int> n;
     1.6      readDimacs(is, g, n, u, u, n);
     1.7 -    std::cout<<"igen en.";
     1.8    }
     1.9  
    1.10    /// sg problem

     2.1 --- a/src/work/marci/bfs_dfs_misc.h	Thu May 06 14:25:21 2004 +0000
     2.2 +++ b/src/work/marci/bfs_dfs_misc.h	Thu May 06 15:10:48 2004 +0000
     2.3 @@ -19,27 +19,29 @@
     2.4      FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
     2.5        if (!reached[n]) {
     2.6  	bfs.pushAndSetReached(n);
     2.7 -	bool_map.set(n, false) {
     2.8 -	  while (!bfs.finished()) {
     2.9 -	    if (bfs.isBNodeNewlyReached()) {
    2.10 -	      bool_map.set(bfs.bNode())=!bfs.aNode();
    2.11 -	    } else {
    2.12 -	      if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
    2.13 -		return false;
    2.14 -	      }
    2.15 +	bool_map.set(n, false);
    2.16 +	while (!bfs.finished()) {
    2.17 +	  if (bfs.isBNodeNewlyReached()) {
    2.18 +	    bool_map.set(bfs.bNode())=!bfs.aNode();
    2.19 +	  } else {
    2.20 +	    if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
    2.21 +	      return false;
    2.22  	    }
    2.23 -	    ++bfs;
    2.24  	  }
    2.25 +	  ++bfs;
    2.26  	}
    2.27        }
    2.28      }
    2.29 +    
    2.30      return true;
    2.31    }
    2.32  
    2.33    /// experimental topsort, 
    2.34    /// I think the final version will work as an iterator
    2.35 +  /// if the graph is not a acyclic, the na pre-topological order is obtained 
    2.36 +  /// (see Schrijver's book)
    2.37    template<typename Graph> 
    2.38 -  void topSort(Graph& g, std::list<typename Graph::Node>& l) {
    2.39 +  void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
    2.40      l.clear();
    2.41      typedef typename Graph::template NodeMap<bool> ReachedMap;
    2.42      ReachedMap reached(g/*, false*/);

     3.1 --- a/src/work/marci/makefile	Thu May 06 14:25:21 2004 +0000
     3.2 +++ b/src/work/marci/makefile	Thu May 06 15:10:48 2004 +0000
     3.3 @@ -4,7 +4,7 @@
     3.4  INCLUDEDIRS ?= -I../.. -I../../hugo -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
     3.5  
     3.6  LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
     3.7 -BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2 bipartite_matching_try_3
     3.8 +BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2 bipartite_matching_try_3 top_sort_test
     3.9  #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    3.10  
    3.11  include ../makefile

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/work/marci/top_sort.dim	Thu May 06 15:10:48 2004 +0000
     4.3 @@ -0,0 +1,5 @@
     4.4 +p mat 5 4
     4.5 +a 1 3
     4.6 +a 2 3
     4.7 +a 3 5
     4.8 +a 3 4

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/work/marci/top_sort_test.cc	Thu May 06 15:10:48 2004 +0000
     5.3 @@ -0,0 +1,25 @@
     5.4 +// -*- c++ -*-
     5.5 +#include <iostream>
     5.6 +#include <fstream>
     5.7 +#include <list>
     5.8 +
     5.9 +#include <hugo/dimacs.h>
    5.10 +#include <bfs_dfs_misc.h>
    5.11 +#include <list_graph.h>
    5.12 +
    5.13 +using namespace hugo;
    5.14 +
    5.15 +int main() {
    5.16 +  typedef ListGraph Graph;
    5.17 +  Graph g;
    5.18 +  readDimacs(std::cin, g);
    5.19 +  std::list<Graph::Node> l;
    5.20 +  topSort(g, l);
    5.21 +  std::cout << "Leaving order of dfs which is pretopological..." << std::endl;
    5.22 +  for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
    5.23 +    std::cout << *i << " ";
    5.24 +  }
    5.25 +  std::cout << std::endl;
    5.26 +
    5.27 +  return 0;
    5.28 +}