1.1 --- a/demo/Makefile.am Mon Sep 12 05:31:55 2005 +0000
1.2 +++ b/demo/Makefile.am Mon Sep 12 05:35:36 2005 +0000
1.3 @@ -9,6 +9,7 @@
1.4 reader_writer_demo \
1.5 dim_to_lgf \
1.6 graph_to_eps_demo \
1.7 + graph_orientation \
1.8 min_route \
1.9 hello_lemon \
1.10 sub_graph_adaptor_demo \
1.11 @@ -36,6 +37,8 @@
1.12
1.13 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
1.14
1.15 +graph_orientation_SOURCES = graph_orientation.cc
1.16 +
1.17 min_route_SOURCES = min_route.cc
1.18
1.19 hello_lemon_SOURCES = hello_lemon.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/graph_orientation.cc Mon Sep 12 05:35:36 2005 +0000
2.3 @@ -0,0 +1,124 @@
2.4 +/* -*- C++ -*-
2.5 + * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +
2.21 +#include <lemon/list_graph.h>
2.22 +#include <lemon/graph_reader.h>
2.23 +#include <lemon/iterable_maps.h>
2.24 +#include <lemon/xy.h>
2.25 +#include <lemon/graph_to_eps.h>
2.26 +
2.27 +
2.28 +using namespace lemon;
2.29 +
2.30 +
2.31 +typedef ListGraph::Node Node;
2.32 +typedef ListGraph::NodeIt NodeIt;
2.33 +typedef ListGraph::Edge Edge;
2.34 +typedef ListGraph::EdgeIt EdgeIt;
2.35 +typedef ListGraph::OutEdgeIt OutEdgeIt;
2.36 +typedef ListGraph::InEdgeIt InEdgeIt;
2.37 +
2.38 +int main(int argc, char** argv)
2.39 +{
2.40 + if(argc!=2) {
2.41 + std::cerr << "\n USAGE: " << argv[0]
2.42 + << " input_file.lgf" << std::endl << std::endl;
2.43 + std::cerr << " The file 'input_file.lgf' has to contain "
2.44 + << "at least three node maps called \n 'f', 'coordinates_x' "
2.45 + << "and 'coordinates_y'.\n"
2.46 + << " The in-degree requirement is given by 'f', while the two "
2.47 + << "others is used\n to create to output drawing."
2.48 + << std::endl;
2.49 + return 1;
2.50 + }
2.51 +
2.52 + ListGraph g;
2.53 +
2.54 + ListGraph::NodeMap<int> f(g); //in-deg requirement;
2.55 + ListGraph::NodeMap<int> id(g);
2.56 + ListGraph::NodeMap<xy<double> > coords(g);
2.57 +
2.58 + try {
2.59 + GraphReader<ListGraph> reader(argv[1],g);
2.60 + reader.readNodeMap("f",f);
2.61 + reader.readNodeMap("id",id);
2.62 + reader.readNodeMap("coordinates_x",xMap(coords));
2.63 + reader.readNodeMap("coordinates_y",yMap(coords));
2.64 + reader.run();
2.65 + } catch (DataFormatError& error) {
2.66 + std::cerr << error.what() << std::endl;
2.67 + return 1;
2.68 + }
2.69 +
2.70 +
2.71 + ListGraph::NodeMap<int> level(g,0);
2.72 +
2.73 + ListGraph::NodeMap<int> def(g); //deficiency of the nodes
2.74 + def = subMap(f,InDegMap<ListGraph>(g));
2.75 +
2.76 + IterableBoolNodeMap<ListGraph> active(g,false);
2.77 + for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
2.78 +
2.79 + ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be
2.80 + // reversed
2.81 +
2.82 + int nodeNum=countNodes(g);
2.83 +
2.84 + Node act;
2.85 + while((act=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
2.86 + std::cout << "Process node " << id[act]
2.87 + << " (def=" << def[act]
2.88 + << " lev=" << level[act] << "): ";
2.89 + OutEdgeIt e(g,act);
2.90 + while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
2.91 + if(e!=INVALID) {
2.92 + std::cout << " REVERT EDGE " << g.id(e)
2.93 + << " (" << id[g.source(e)] << "---"
2.94 + << id[g.target(e)] << ")"
2.95 + << std::endl;
2.96 + if(--def[act]==0) active[act]=false;
2.97 + if(++def[g.target(e)]>0) active[g.target(e)]=true;
2.98 + g.reverseEdge(e);
2.99 + rev[e]!=rev[e];
2.100 + }
2.101 + else {
2.102 + std::cout << " LIFT" << std::endl;
2.103 + if(++level[act]>nodeNum) {
2.104 + std::cout << "NINCS ILYEN\n";
2.105 + return 1;
2.106 + }
2.107 + }
2.108 + }
2.109 +
2.110 + //Show the graph
2.111 +
2.112 + graphToEps(g,"indeg_graph_rev_out.eps").scaleToA4().
2.113 + title("Sample .eps figure (fits to A4)").
2.114 + copyright("(C) 2005 LEMON Project").
2.115 + nodeScale(15).
2.116 + coords(coords).
2.117 + negateY().
2.118 + edgeColors(composeMap(ColorSet(),rev)).
2.119 + edgeWidthScale(1).
2.120 + nodeTexts(f).nodeTextSize(20).
2.121 + drawArrows().arrowWidth(10).arrowLength(10).
2.122 + run();
2.123 +
2.124 +
2.125 +} //end of main()
2.126 +
2.127 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/doc/graph_orientation.dox Mon Sep 12 05:35:36 2005 +0000
3.3 @@ -0,0 +1,142 @@
3.4 +namespace lemon {
3.5 +/**
3.6 +
3.7 +\ingroup demos
3.8 +\file graph_orientation.cc
3.9 +\brief Graph orientation with lower bound requirement on the
3.10 +in-degree of the nodes.
3.11 +
3.12 +
3.13 +
3.14 +First we include some important headers.
3.15 +
3.16 +The first one defines \ref lemon::ListGraph "ListGraph",
3.17 +the "Swiss army knife" graph implementation.
3.18 +\dontinclude graph_orientation.cc
3.19 +\skipline list_graph
3.20 +
3.21 +The next is to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
3.22 +\skipline reader
3.23 +
3.24 +This provides us with some special purpose graph \ref maps "maps".
3.25 +\skipline iterable
3.26 +
3.27 +The following header defines a simple data structure to store and manipulate
3.28 +planar coordinates. It will be used to draw the result.
3.29 +\skipline xy
3.30 +
3.31 +And finally, this header contains a simple graph drawing utility.
3.32 +\skipline eps
3.33 +
3.34 +As we don't want to type in \ref lemon "lemon::" million times, the
3.35 +following line seems to be useful.
3.36 +\skipline namespace
3.37 +
3.38 +The following <tt>typedef</tt>s will also save a lot of typing.
3.39 +\skip typedef
3.40 +\until InEdgeIt
3.41 +
3.42 +Well, we are ready to start <tt>main()</tt>.
3.43 +\skip main
3.44 +\until {
3.45 +
3.46 +First we check whether the program is called with exactly 1 parameter.
3.47 +If it isn't, we print a short help message end exit.
3.48 +The vast majority of people would probably skip this block.
3.49 +\skip if
3.50 +\until }
3.51 +
3.52 +Now, we read a graph \c g, and a map \c f containing
3.53 +the in-deg requirements from a \ref graph-io-page ".lgf" (Lemon Graph Format)
3.54 +file. To generate the output picture, we also read the node titles (\c id) and
3.55 +coordinates (\c coords).
3.56 +So, first we create the graph
3.57 +\skipline ListGraph
3.58 +and the corresponding NodeMaps.
3.59 +\skipline NodeMap
3.60 +\until coords
3.61 +\note The graph must be given to the maps' constructor.
3.62 +
3.63 +Then, the following block will read these data from the file, or exit if
3.64 +the file is missing or corrupt.
3.65 +\skip try
3.66 +\until }
3.67 +\until }
3.68 +
3.69 +The algorithm needs a "level" integer value assigned to each node. In the
3.70 +beginning, the nodes are on level 0.
3.71 +\skipline level
3.72 +
3.73 +The deficiency (\c def) of a node is the in-degree requirement minus the
3.74 +actual in-degree.
3.75 +
3.76 +\skip def
3.77 +\until subMap
3.78 +
3.79 +A node is \e active if its deficiency is positive (i.e. if it doesn't meet
3.80 +the degree requirement).
3.81 +\skip active
3.82 +\until def
3.83 +
3.84 +We also store in a bool map which edges are reverted. Actually this is only
3.85 +used to draw these edges with different color in the output picture. The
3.86 +algorithm will update this map called \c rev, but will not use it otherwise.
3.87 +\skip rev
3.88 +\until reversed
3.89 +
3.90 +The variable \c nodeNum will refer to the number of nodes.
3.91 +\skipline nodeNum
3.92 +
3.93 +Here comes the algorithms itself.
3.94 +In each iteration we choose an active node (\c act will store it). If there is
3.95 +no such a node, then the orientation is feasible so we are done.
3.96 +\skip act
3.97 +\until while
3.98 +
3.99 +Then we check if there exists an edge leaving this node that steps down exactly
3.100 +one level.
3.101 +\skip OutEdge
3.102 +\until while
3.103 +
3.104 +If there exists, we decrease the "activity" of the node \c act by reverting
3.105 +this egde.
3.106 +Fortunately, \ref lemon::ListGraph "ListGraph"
3.107 +has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
3.108 +that makes this easy.
3.109 +We also have to update the maps \c def and
3.110 +\c rev.
3.111 +\skipline if
3.112 +\skip if
3.113 +\until }
3.114 +Otherwise (i.e. if there is no edge stepping down one level). We lift up the
3.115 +current active node \c act. If it reaches level \c nodeNum, then there
3.116 +exists no appropriate orientation so we stop.
3.117 +\skipline else
3.118 +\skipline if
3.119 +\skipline return
3.120 +\until }
3.121 +\until }
3.122 +\until }
3.123 +
3.124 +Believe it or not, this algorithm works and runs fast.
3.125 +
3.126 +Finally, we print the obtained orientation. Note, how the different
3.127 +\c bool values of
3.128 +\c rev are transformed into different \ref lemon::Color "RGB color"s
3.129 +using the class
3.130 +\ref lemon::ColorSet "ColorSet"
3.131 +and the \ref map_adaptors "map adaptor" called
3.132 +\ref lemon::ComposeMap "composeMap".
3.133 +
3.134 +\skip graphToEps
3.135 +\until run
3.136 +
3.137 +
3.138 +\until end of main
3.139 +
3.140 +Finally here are again the list of the used include files (because I can't turn
3.141 +this section off.)
3.142 +
3.143 +*/
3.144 +
3.145 +}
3.146 \ No newline at end of file