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 alpar@1678: #include alpar@1678: #include alpar@1678: #include alpar@1678: #include 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 f(g); //in-deg requirement; alpar@1678: ListGraph::NodeMap id(g); alpar@1678: ListGraph::NodeMap > coords(g); alpar@1678: alpar@1678: try { alpar@1678: GraphReader reader(argv[1],g); alpar@1678: reader.readNodeMap("f",f); alpar@1678: reader.readNodeMap("id",id); 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 level(g,0); alpar@1678: alpar@1678: ListGraph::NodeMap def(g); //deficiency of the nodes alpar@1678: def = subMap(f,InDegMap(g)); alpar@1678: alpar@1678: IterableBoolNodeMap active(g,false); alpar@1678: for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0); alpar@1678: alpar@1678: ListGraph::EdgeMap 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; alpar@1678: while((act=IterableBoolNodeMap::TrueIt(active))!=INVALID) { alpar@1678: std::cout << "Process node " << id[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) alpar@1678: << " (" << id[g.source(e)] << "---" alpar@1678: << id[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: