source: lemon-0.x/demo/graph_orientation.cc @ 1689:f1795dafe42c

/* -*- C++ -*-
 * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 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> id(g);
  ListGraph::NodeMap<xy<double> > coords(g);
  
  try {
    GraphReader<ListGraph> reader(argv[1],g);
    reader.readNodeMap("f",f);
    reader.readNodeMap("id",id);
    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));
  
  IterableBoolNodeMap<ListGraph> 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=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
    std::cout << "Process node " << id[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)
                << " (" << id[g.source(e)] << "---"
                << id[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) 2005 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()