1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/demo/graph_orientation.cc Mon Sep 12 05:35:36 2005 +0000
1.3 @@ -0,0 +1,124 @@
1.4 +/* -*- C++ -*-
1.5 + * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +
1.21 +#include <lemon/list_graph.h>
1.22 +#include <lemon/graph_reader.h>
1.23 +#include <lemon/iterable_maps.h>
1.24 +#include <lemon/xy.h>
1.25 +#include <lemon/graph_to_eps.h>
1.26 +
1.27 +
1.28 +using namespace lemon;
1.29 +
1.30 +
1.31 +typedef ListGraph::Node Node;
1.32 +typedef ListGraph::NodeIt NodeIt;
1.33 +typedef ListGraph::Edge Edge;
1.34 +typedef ListGraph::EdgeIt EdgeIt;
1.35 +typedef ListGraph::OutEdgeIt OutEdgeIt;
1.36 +typedef ListGraph::InEdgeIt InEdgeIt;
1.37 +
1.38 +int main(int argc, char** argv)
1.39 +{
1.40 + if(argc!=2) {
1.41 + std::cerr << "\n USAGE: " << argv[0]
1.42 + << " input_file.lgf" << std::endl << std::endl;
1.43 + std::cerr << " The file 'input_file.lgf' has to contain "
1.44 + << "at least three node maps called \n 'f', 'coordinates_x' "
1.45 + << "and 'coordinates_y'.\n"
1.46 + << " The in-degree requirement is given by 'f', while the two "
1.47 + << "others is used\n to create to output drawing."
1.48 + << std::endl;
1.49 + return 1;
1.50 + }
1.51 +
1.52 + ListGraph g;
1.53 +
1.54 + ListGraph::NodeMap<int> f(g); //in-deg requirement;
1.55 + ListGraph::NodeMap<int> id(g);
1.56 + ListGraph::NodeMap<xy<double> > coords(g);
1.57 +
1.58 + try {
1.59 + GraphReader<ListGraph> reader(argv[1],g);
1.60 + reader.readNodeMap("f",f);
1.61 + reader.readNodeMap("id",id);
1.62 + reader.readNodeMap("coordinates_x",xMap(coords));
1.63 + reader.readNodeMap("coordinates_y",yMap(coords));
1.64 + reader.run();
1.65 + } catch (DataFormatError& error) {
1.66 + std::cerr << error.what() << std::endl;
1.67 + return 1;
1.68 + }
1.69 +
1.70 +
1.71 + ListGraph::NodeMap<int> level(g,0);
1.72 +
1.73 + ListGraph::NodeMap<int> def(g); //deficiency of the nodes
1.74 + def = subMap(f,InDegMap<ListGraph>(g));
1.75 +
1.76 + IterableBoolNodeMap<ListGraph> active(g,false);
1.77 + for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
1.78 +
1.79 + ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be
1.80 + // reversed
1.81 +
1.82 + int nodeNum=countNodes(g);
1.83 +
1.84 + Node act;
1.85 + while((act=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
1.86 + std::cout << "Process node " << id[act]
1.87 + << " (def=" << def[act]
1.88 + << " lev=" << level[act] << "): ";
1.89 + OutEdgeIt e(g,act);
1.90 + while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
1.91 + if(e!=INVALID) {
1.92 + std::cout << " REVERT EDGE " << g.id(e)
1.93 + << " (" << id[g.source(e)] << "---"
1.94 + << id[g.target(e)] << ")"
1.95 + << std::endl;
1.96 + if(--def[act]==0) active[act]=false;
1.97 + if(++def[g.target(e)]>0) active[g.target(e)]=true;
1.98 + g.reverseEdge(e);
1.99 + rev[e]!=rev[e];
1.100 + }
1.101 + else {
1.102 + std::cout << " LIFT" << std::endl;
1.103 + if(++level[act]>nodeNum) {
1.104 + std::cout << "NINCS ILYEN\n";
1.105 + return 1;
1.106 + }
1.107 + }
1.108 + }
1.109 +
1.110 + //Show the graph
1.111 +
1.112 + graphToEps(g,"indeg_graph_rev_out.eps").scaleToA4().
1.113 + title("Sample .eps figure (fits to A4)").
1.114 + copyright("(C) 2005 LEMON Project").
1.115 + nodeScale(15).
1.116 + coords(coords).
1.117 + negateY().
1.118 + edgeColors(composeMap(ColorSet(),rev)).
1.119 + edgeWidthScale(1).
1.120 + nodeTexts(f).nodeTextSize(20).
1.121 + drawArrows().arrowWidth(10).arrowLength(10).
1.122 + run();
1.123 +
1.124 +
1.125 +} //end of main()
1.126 +
1.127 +