The input of the problem is a(n undirected) graph and an integer value f(n) assigned to each node n. The task is to find an orientation of the edges for which the number of edge arriving at each node n is at least least f(n).
In fact, the algorithm reads a directed graph and computes a set of edges to be reversed in order to achieve the in-degree requirement. This input is given using .lgf (Lemon Graph Format) file. It should contain three node maps. The one called "f" contains the in-degree requirements, while "coordinate_x" and "coordinate_y" indicate the position of the nodes. These latter ones are used to generate the output, which is a .eps file.
The first one defines ListGraph, the "Swiss army knife" graph implementation.
#include <lemon/list_graph.h>
The next is to read a .lgf (Lemon Graph Format) file.
#include <lemon/graph_reader.h>
This provides us with some special purpose graph maps.
#include <lemon/iterable_maps.h>
The following header defines a simple data structure to store and manipulate planar coordinates. It will be used to draw the result.
#include <lemon/dim2.h>
And finally, this header contains a simple graph drawing utility.
#include <lemon/graph_to_eps.h>
As we don't want to type in lemon:: million times, the following line seems to be useful.
using namespace lemon;
The following macro will also save a lot of typing by defining some convenience typedefs.
GRAPH_TYPEDEFS(ListGraph);
Actually, the macro above would be equivalent with the following typedefs.
typedef ListGraph::Node Node; typedef ListGraph::NodeIt NodeIt; typedef ListGraph::Edge Edge; typedef ListGraph::EdgeIt EdgeIt; typedef ListGraph::OutEdgeIt OutEdgeIt; typedef ListGraph::InEdgeIt InEdgeIt;
main(). int main(int argc, char** argv) {
First we check whether the program is called with exactly one parameter. If it isn't, we print a short help message end exit. The vast majority of people would probably skip this block.
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; }
Now, we read a graph g, and a map f containing the in-deg requirements from a .lgf (Lemon Graph Format) file. To generate the output picture, we also read the node titles (label) and coordinates (coords). So, first we create the graph
ListGraph g;
ListGraph::NodeMap<int> f(g); //in-deg requirement;
ListGraph::NodeMap<int> label(g);
ListGraph::NodeMap<dim2::Point<double> > coords(g);
try { GraphReader<ListGraph> 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; }
The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the beginning of the execution.
ListGraph::NodeMap<int> level(g,0);
The deficiency (def) of a node is the in-degree requirement minus the actual in-degree.
ListGraph::NodeMap<int> def(g); //deficiency of the nodes def = subMap(f,InDegMap<ListGraph>(g));
A node is active if its deficiency is positive (i.e. if it doesn't meet the degree requirement).
IterableBoolMap<ListGraph, Node> active(g,false); for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
We also store a bool map indicating which edges are reverted. Actually this map called rev is only used to draw these edges with different color in the output picture. The algorithm updates this map, but will not use it otherwise.
ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is to be // reversed
The variable nodeNum will refer to the number of nodes.
int nodeNum=countNodes(g);
Here comes the algorithm itself. In each iteration we choose an active node (act will do it for us). If there is no such a node, then the orientation is feasible so we are done.
Node act; while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {
Then we check if there exists an edge leaving this node and stepping down exactly one level.
OutEdgeIt e(g,act);
while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
If there exists, we decrease the "activity" of the node act by reverting this egde. Fortunately, ListGraph has a special function reverseEdge() that makes this easy. We also have to update the maps def and rev.
if(e!=INVALID) { 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]; }
act. If it reaches level nodeNum, then there exists no appropriate orientation so we stop. else { if(++level[act]>nodeNum) { return 1; } } }
Believe it or not, this algorithm works and runs fast.
Finally, we print the obtained orientation. Note, how the different bool values of rev are transformed into different RGB colors using the class Palette and the map adaptor called composeMap.
graphToEps(g,"graph_orientation.eps").scaleToA4(). title("Sample .eps figure (fits to A4)"). copyright("(C) 2003-2007 LEMON Project"). absoluteNodeSizes().absoluteEdgeWidths(). nodeScale(15). coords(coords). negateY(). edgeColors(composeMap(Palette(),rev)). edgeWidthScale(1). nodeTexts(f).nodeTextSize(20). drawArrows().arrowWidth(10).arrowLength(10). run();
} //end of main()
Finally here are again the list of the used include files (because I can't turn this section off.) #include <lemon/list_graph.h>
#include <lemon/graph_reader.h>
#include <lemon/iterable_maps.h>
#include <lemon/dim2.h>
#include <lemon/graph_to_eps.h>
1.5.9