demo/graph_orientation.cc
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 2172 4b25e7003868
child 2310 96cca167430a
permissions -rw-r--r--
Bug fixes
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/list_graph.h>
    20 #include <lemon/graph_reader.h>
    21 #include <lemon/iterable_maps.h>
    22 #include <lemon/dim2.h>
    23 #include <lemon/graph_to_eps.h>
    24 
    25 
    26 using namespace lemon;
    27  
    28 GRAPH_TYPEDEFS(ListGraph)
    29 
    30 int main(int argc, char** argv) 
    31 {
    32   if(argc!=2) {
    33     std::cerr << "\n  USAGE: " << argv[0]
    34 	      << " input_file.lgf" << std::endl << std::endl;
    35     std::cerr << "  The file 'input_file.lgf' has to contain "
    36 	      << "at least three node maps called \n  'f', 'coordinates_x' "
    37 	      << "and 'coordinates_y'.\n"
    38 	      << "  The in-degree requirement is given by 'f', while the two "
    39 	      << "others is used\n  to create to output drawing."
    40 	      << std::endl;
    41     return 1;
    42   }
    43   
    44   ListGraph g;
    45 
    46   ListGraph::NodeMap<int> f(g); //in-deg requirement;
    47   ListGraph::NodeMap<int> label(g);
    48   ListGraph::NodeMap<dim2::Point<double> > coords(g);
    49   
    50   try {
    51     GraphReader<ListGraph> reader(argv[1],g);
    52     reader.readNodeMap("f",f);
    53     reader.readNodeMap("label",label);
    54     reader.readNodeMap("coordinates_x",xMap(coords));
    55     reader.readNodeMap("coordinates_y",yMap(coords));
    56     reader.run();
    57   } catch (DataFormatError& error) {
    58     std::cerr << error.what() << std::endl;
    59     return 1;
    60   }
    61 
    62   
    63   ListGraph::NodeMap<int> level(g,0);
    64   
    65   ListGraph::NodeMap<int> def(g); //deficiency of the nodes
    66   def = subMap(f,InDegMap<ListGraph>(g));
    67   
    68   IterableBoolMap<ListGraph, Node> active(g,false);
    69   for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
    70   
    71   ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is to be 
    72                                          //                  reversed
    73 
    74   int nodeNum=countNodes(g);
    75   
    76   Node act;
    77   while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {
    78     std::cout << "Process node " << label[act]
    79 	      << " (def=" << def[act]
    80 	      << " lev=" << level[act] << "): ";
    81     OutEdgeIt e(g,act);
    82     while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
    83     if(e!=INVALID) {
    84       std::cout << " REVERT EDGE " << g.id(e)
    85 		<< " (" << label[g.source(e)] << "---"
    86 		<< label[g.target(e)] << ")"
    87 		<< std::endl;
    88       if(--def[act]==0) active[act]=false;
    89       if(++def[g.target(e)]>0) active[g.target(e)]=true;
    90       g.reverseEdge(e);
    91       rev[e]=!rev[e];
    92     }
    93     else {
    94       std::cout << " LIFT" << std::endl;
    95       if(++level[act]>nodeNum) {
    96 	std::cout << "NINCS ILYEN\n";
    97 	return 1;
    98       }
    99     }
   100   }
   101   
   102   //Show the graph
   103 
   104   graphToEps(g,"graph_orientation.eps").scaleToA4().
   105     title("Sample .eps figure (fits to A4)").
   106     copyright("(C) 2006 LEMON Project").
   107     nodeScale(15).
   108     coords(coords).
   109     negateY().
   110     edgeColors(composeMap(Palette(),rev)).
   111     edgeWidthScale(1).
   112     nodeTexts(f).nodeTextSize(20).
   113     drawArrows().arrowWidth(10).arrowLength(10).
   114     run();
   115 
   116   
   117 } //end of main()
   118 
   119