alpar@1678: /* -*- C++ -*-
alpar@1678:  * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library
alpar@1678:  *
alpar@1875:  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1678:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1678:  *
alpar@1678:  * Permission to use, modify and distribute this software is granted
alpar@1678:  * provided that this copyright notice appears in all copies. For
alpar@1678:  * precise terms see the accompanying LICENSE file.
alpar@1678:  *
alpar@1678:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1678:  * express or implied, and with no claim as to its suitability for any
alpar@1678:  * purpose.
alpar@1678:  *
alpar@1678:  */
alpar@1678: 
alpar@1678: 
alpar@1678: #include <lemon/list_graph.h>
alpar@1678: #include <lemon/graph_reader.h>
alpar@1678: #include <lemon/iterable_maps.h>
alpar@1678: #include <lemon/xy.h>
alpar@1678: #include <lemon/graph_to_eps.h>
alpar@1678: 
alpar@1678: 
alpar@1678: using namespace lemon;
alpar@1678:  
alpar@1678: 
alpar@1678: typedef ListGraph::Node Node;
alpar@1678: typedef ListGraph::NodeIt NodeIt;
alpar@1678: typedef ListGraph::Edge Edge;
alpar@1678: typedef ListGraph::EdgeIt EdgeIt;
alpar@1678: typedef ListGraph::OutEdgeIt OutEdgeIt;
alpar@1678: typedef ListGraph::InEdgeIt InEdgeIt;
alpar@1678: 
alpar@1678: int main(int argc, char** argv) 
alpar@1678: {
alpar@1678:   if(argc!=2) {
alpar@1678:     std::cerr << "\n  USAGE: " << argv[0]
alpar@1678: 	      << " input_file.lgf" << std::endl << std::endl;
alpar@1678:     std::cerr << "  The file 'input_file.lgf' has to contain "
alpar@1678: 	      << "at least three node maps called \n  'f', 'coordinates_x' "
alpar@1678: 	      << "and 'coordinates_y'.\n"
alpar@1678: 	      << "  The in-degree requirement is given by 'f', while the two "
alpar@1678: 	      << "others is used\n  to create to output drawing."
alpar@1678: 	      << std::endl;
alpar@1678:     return 1;
alpar@1678:   }
alpar@1678:   
alpar@1678:   ListGraph g;
alpar@1678: 
alpar@1678:   ListGraph::NodeMap<int> f(g); //in-deg requirement;
deba@1901:   ListGraph::NodeMap<int> label(g);
alpar@1678:   ListGraph::NodeMap<xy<double> > coords(g);
alpar@1678:   
alpar@1678:   try {
alpar@1678:     GraphReader<ListGraph> reader(argv[1],g);
alpar@1678:     reader.readNodeMap("f",f);
deba@1901:     reader.readNodeMap("label",label);
alpar@1678:     reader.readNodeMap("coordinates_x",xMap(coords));
alpar@1678:     reader.readNodeMap("coordinates_y",yMap(coords));
alpar@1678:     reader.run();
alpar@1678:   } catch (DataFormatError& error) {
alpar@1678:     std::cerr << error.what() << std::endl;
alpar@1678:     return 1;
alpar@1678:   }
alpar@1678: 
alpar@1678:   
alpar@1678:   ListGraph::NodeMap<int> level(g,0);
alpar@1678:   
alpar@1678:   ListGraph::NodeMap<int> def(g); //deficiency of the nodes
alpar@1678:   def = subMap(f,InDegMap<ListGraph>(g));
alpar@1678:   
deba@1913:   IterableBoolMap<ListGraph, Node> active(g,false);
alpar@1678:   for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
alpar@1678:   
alpar@1678:   ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be 
alpar@1678:                                          //                  reversed
alpar@1678: 
alpar@1678:   int nodeNum=countNodes(g);
alpar@1678:   
alpar@1678:   Node act;
deba@1913:   while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {
deba@1901:     std::cout << "Process node " << label[act]
alpar@1678: 	      << " (def=" << def[act]
alpar@1678: 	      << " lev=" << level[act] << "): ";
alpar@1678:     OutEdgeIt e(g,act);
alpar@1678:     while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
alpar@1678:     if(e!=INVALID) {
alpar@1678:       std::cout << " REVERT EDGE " << g.id(e)
deba@1901: 		<< " (" << label[g.source(e)] << "---"
deba@1901: 		<< label[g.target(e)] << ")"
alpar@1678: 		<< std::endl;
alpar@1678:       if(--def[act]==0) active[act]=false;
alpar@1678:       if(++def[g.target(e)]>0) active[g.target(e)]=true;
alpar@1678:       g.reverseEdge(e);
alpar@1687:       rev[e]=!rev[e];
alpar@1678:     }
alpar@1678:     else {
alpar@1678:       std::cout << " LIFT" << std::endl;
alpar@1678:       if(++level[act]>nodeNum) {
alpar@1678: 	std::cout << "NINCS ILYEN\n";
alpar@1678: 	return 1;
alpar@1678:       }
alpar@1678:     }
alpar@1678:   }
alpar@1678:   
alpar@1678:   //Show the graph
alpar@1678: 
alpar@1687:   graphToEps(g,"graph_orientation.eps").scaleToA4().
alpar@1678:     title("Sample .eps figure (fits to A4)").
alpar@1875:     copyright("(C) 2006 LEMON Project").
alpar@1678:     nodeScale(15).
alpar@1678:     coords(coords).
alpar@1678:     negateY().
alpar@1678:     edgeColors(composeMap(ColorSet(),rev)).
alpar@1678:     edgeWidthScale(1).
alpar@1678:     nodeTexts(f).nodeTextSize(20).
alpar@1678:     drawArrows().arrowWidth(10).arrowLength(10).
alpar@1678:     run();
alpar@1678: 
alpar@1678:   
alpar@1678: } //end of main()
alpar@1678: 
alpar@1678: