src/work/marci/top_sort_test.cc
author marci
Tue, 11 May 2004 15:54:00 +0000
changeset 609 0566ac97809b
parent 577 e8703f0a6e2f
child 640 d426dca0aaf7
permissions -rw-r--r--
misc
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 #include <list>
     5 
     6 #include <hugo/dimacs.h>
     7 #include <bfs_dfs_misc.h>
     8 #include <list_graph.h>
     9 #include <hugo/graph_wrapper.h>
    10 #include <hugo/maps.h>
    11 #include <for_each_macros.h>
    12 
    13 using namespace hugo;
    14 
    15 using std::cout;
    16 using std::endl;
    17 
    18 int main() {
    19   typedef ListGraph Graph;
    20   Graph g;
    21   readDimacs(std::cin, g); 
    22  
    23   {
    24     std::list<Graph::Node> l;
    25     //NullMap<Graph::Node, Graph::Edge> pred;
    26     Graph::NodeMap<Graph::Edge> pred(g, INVALID);
    27     topSort(g, l, pred);
    28     cout << "Leaving order of dfs which is pretopological..." << endl;
    29     for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
    30       cout << *i << " ";
    31     }
    32     cout << endl;
    33     
    34     FOR_EACH_LOC(Graph::NodeIt, n, g) {
    35       cout << "pred of node " << n << " is " << pred[n] << endl;
    36     }
    37   }
    38   
    39   {
    40     typedef RevGraphWrapper<Graph> GW;
    41     GW gw(g);
    42     std::list<GW::Node> l;
    43     //NullMap<GW::Node, GW::Edge> pred;
    44     GW::NodeMap<Graph::Edge> pred(gw, INVALID);
    45     topSort(gw, l, pred);
    46     cout << "Same in the reversed oriented graph..." << endl;
    47     for(std::list<GW::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
    48       cout << *i << " ";
    49     }
    50     cout << endl;
    51 
    52     FOR_EACH_LOC(GW::NodeIt, n, gw) {
    53       cout << "pred of node " << n << " is " << pred[n] << endl;
    54     }
    55   }
    56 
    57   return 0;
    58 }