/* -*- C++ -*-

  * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <lemon/list_graph.h>

 #include <lemon/graph_reader.h>

 #include <lemon/iterable_maps.h>

 #include <lemon/xy.h>

 #include <lemon/graph_to_eps.h>

 using namespace lemon;

 typedef ListGraph::Node Node;

 typedef ListGraph::NodeIt NodeIt;

 typedef ListGraph::Edge Edge;

 typedef ListGraph::EdgeIt EdgeIt;

 typedef ListGraph::OutEdgeIt OutEdgeIt;

 typedef ListGraph::InEdgeIt InEdgeIt;

 int main(int argc, char** argv) 

 {

   if(argc!=2) {

     std::cerr << "\n  USAGE: " << argv[0]

 	      << " input_file.lgf" << std::endl << std::endl;

     std::cerr << "  The file 'input_file.lgf' has to contain "

 	      << "at least three node maps called \n  'f', 'coordinates_x' "

 	      << "and 'coordinates_y'.\n"

 	      << "  The in-degree requirement is given by 'f', while the two "

 	      << "others is used\n  to create to output drawing."

 	      << std::endl;

     return 1;

   }

   ListGraph g;

   ListGraph::NodeMap<int> f(g); //in-deg requirement;

   ListGraph::NodeMap<int> label(g);

   ListGraph::NodeMap<xy<double> > coords(g);

   try {

     GraphReader<ListGraph> reader(argv[1],g);

     reader.readNodeMap("f",f);

     reader.readNodeMap("label",label);

     reader.readNodeMap("coordinates_x",xMap(coords));

     reader.readNodeMap("coordinates_y",yMap(coords));

     reader.run();

   } catch (DataFormatError& error) {

     std::cerr << error.what() << std::endl;

     return 1;

   }

   ListGraph::NodeMap<int> level(g,0);

   ListGraph::NodeMap<int> def(g); //deficiency of the nodes

   def = subMap(f,InDegMap<ListGraph>(g));

   IterableBoolMap<ListGraph, Node> active(g,false);

   for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);

   ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be 

                                          //                  reversed

   int nodeNum=countNodes(g);

   Node act;

   while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {

     std::cout << "Process node " << label[act]

 	      << " (def=" << def[act]

 	      << " lev=" << level[act] << "): ";

     OutEdgeIt e(g,act);

     while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;

     if(e!=INVALID) {

       std::cout << " REVERT EDGE " << g.id(e)

 		<< " (" << label[g.source(e)] << "---"

 		<< label[g.target(e)] << ")"

 		<< std::endl;

       if(--def[act]==0) active[act]=false;

       if(++def[g.target(e)]>0) active[g.target(e)]=true;

       g.reverseEdge(e);

       rev[e]=!rev[e];

     }

     else {

       std::cout << " LIFT" << std::endl;

       if(++level[act]>nodeNum) {

 	std::cout << "NINCS ILYEN\n";

 	return 1;

       }

     }

   }

   //Show the graph

   graphToEps(g,"graph_orientation.eps").scaleToA4().

     title("Sample .eps figure (fits to A4)").

     copyright("(C) 2006 LEMON Project").

     nodeScale(15).

     coords(coords).

     negateY().

     edgeColors(composeMap(ColorSet(),rev)).

     edgeWidthScale(1).

     nodeTexts(f).nodeTextSize(20).

     drawArrows().arrowWidth(10).arrowLength(10).

     run();

 } //end of main()