/* -*- 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 #include #include #include #include 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 f(g); //in-deg requirement; ListGraph::NodeMap label(g); ListGraph::NodeMap > coords(g); try { GraphReader 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 level(g,0); ListGraph::NodeMap def(g); //deficiency of the nodes def = subMap(f,InDegMap(g)); IterableBoolMap active(g,false); for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0); ListGraph::EdgeMap rev(g,false); // rev[e]==true <=> e is be // reversed int nodeNum=countNodes(g); Node act; while((act=IterableBoolMap::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()