Skip to content

22. The tools

This chapter describes the programs distributed with the library: the three command-line tools of tools/, i.e., dimacs-solver, dimacs-to-lgf and lgf-gen, the script lemon-0.x-to-1.x.sh, and the three demos of demo/. These tools are small applications of the classes of the previous chapters, and their options are read from their sources; we also give, for each of them, the classes it uses, so that one can reproduce its work in a program (as the program of §22.6 does for two of them).

22.1 Building and calling the tools

By default CMake builds the tools, when the option LEMON_BUILD_TOOLS is on, and installs them into the directory of the executables (bin under the prefix, by GNUInstallDirs); the script lemon-0.x-to-1.x.sh is installed with them, except on Windows. Similarly, the demos are built when LEMON_BUILD_DEMOS is on, also by default, but they are not installed. Both can also be built with GNU make, through the makefiles of tools/ and demo/, without a configuration step (chapter 2).

All three tools parse their command line with ArgParser (chapter 8), and hence they share its conventions. An option is a word preceded by a single dash, e.g., -q or -infcap 100, the options of a group marked as exclusive may not be given together, and -h, -help and --help print the list of the options with their descriptions and exit. The words that are not options are the file arguments; in dimacs-solver and dimacs-to-lgf they are an optional input file and an optional output file, which default to the standard input and output, and more than two of them is an error. Since the input file is read once and the problem line comes first, both tools also read from a pipe.

22.2 dimacs-solver

Our first tool, dimacs-solver, reads a problem in one of the DIMACS formats of §21.5 and solves it with the algorithm of the library for that type, reporting the times of the reading, of the construction of the algorithm object, and of the run, and it writes the solution to the output file, or to the standard output when no output file is given. The reports go to the standard error, so that the standard output holds the solution alone.

Option Meaning Default
-q print no report off
-int int for capacities, costs and supplies on
-long long long (only where the compiler has it) off
-double double off
-ldouble long double off
-infcap v the value of an infinite capacity (§21.5) 0, i.e., the infinity or the maximum of the type

Table 22.1. The options of dimacs-solver; the four options of the type form an exclusive group.

At the start, the tool reads the problem line by dimacsType(), and, unless -q is given, writes the type of the problem and the numbers of nodes and arcs. A file that cannot be opened, of unknown type, or a value of -infcap that cannot be read in the chosen type, ends the program with a message and the exit status 1. Then it builds a SmartDigraph (or a SmartGraph for the type mat) and proceeds by type, as follows. For a sp file, it reads the digraph and the lengths by readDimacsSp(), computes the shortest paths from the source by Dijkstra (chapter 10), and writes a line d v d( v ) for each node v reached. For a max file, it reads the capacities by readDimacsMax(), computes a maximum flow by Preflow (chapter 12), and writes its value as s value and a line f u v x for each arc \((u,v)\) with a nonzero flow \(x\). For a mat file, it reads the graph by readDimacsMat(), computes a maximum matching by MaxMatching (chapter 17), and writes its cardinality as s k and a line m u v for each matched edge. The nodes are numbered from 1, as in the input file.

For a min file, the tool reads the problem by readDimacsMin() and solves it by NetworkSimplex (chapter 13), as in Algorithm 22.1. It writes the cost as s cost and a line f u v x for each arc with a nonzero flow, or s INFEASIBLE or s UNBOUNDED; the cost is computed in a wider type (long long when the values are int, the type of the values otherwise). Its report says whether a feasible flow was found and gives the cost of an optimal one.

Algorithm 22.1 (The minimum cost flow problem in dimacs-solver).

1  read lower, capacity, cost, supply (readDimacsMin, infinite capacity =
   the value of -infcap)
2  sigma := sum of the supplies
3  eps := the data tolerance of NetworkSimplex for the largest magnitude
          of the supplies, of the lower bounds and of the finite capacities
4  if |sigma| <= eps: sigma := 0
5  if sigma > 0: supply type LEQ, else GEQ (the default of NetworkSimplex)
6  run NetworkSimplex; report "found" and the total cost if the result is
   OPTIMAL, "not found" otherwise; write the cost and the flows (or the
   cause) to the output

The choice of line 5 rests on the following property of the flows, in which \(b(v)\) is the supply of the node \(v\) (negative for a demand) and \(\sigma=\sum_v b(v)\).

Lemma 22.1. For any flow \(x\) on the arcs, the excesses \(e(v)=\sum_{a\in\delta^+(v)}x_a-\sum_{a\in\delta^-(v)}x_a\) sum to zero. Hence, the constraints \(e(v)=b(v)\) have no solution when \(\sigma\ne0\); the constraints \(e(v)\le b(v)\) (type LEQ) can have one only if \(\sigma\ge0\), and \(e(v)\ge b(v)\) (type GEQ) only if \(\sigma\le0\); when \(\sigma=0\), both are equivalent to the equations.

Proof. Each arc contributes \(+x_a\) to the excess of its tail and \(-x_a\) to that of its head, which gives \(\sum_ve(v)=0\). If \(e\le b\), then \(0=\sum_ve(v)\le\sigma\), and symmetrically for \(\ge\). If \(\sigma=0\) and \(e\le b\), then \(\sum_v(b(v)-e(v))=0\) with nonnegative terms, and hence \(e=b\); symmetrically for \(\ge\). \(\square\)

Thus, with a total supply larger than the total demand the problem can only be feasible if some supply is left unused, which the type LEQ allows; with a smaller one, it needs the type GEQ, under which some demand stays unsatisfied. Lines 3 and 4 treat as zero a sum that only the rounding of fractional supplies keeps away from zero, with the tolerance that NetworkSimplex itself uses to balance the supplies (chapter 13). We remark that the report of line 6 calls an unbounded problem "not found", although it has feasible flows; the output file, instead, says s UNBOUNDED.

abLEMON

dimacs-solver takes as zero a sum of the supplies within the tolerance of NetworkSimplex; in LEMON 1.3.1 it compared the sum with zero exactly, and a sum of \(10^{-12}\) left by fractional supplies of a double instance made it choose and announce the type LEQ. Also, in LEMON 1.3.1 it wrote no solution (the output file, opened when given, stayed empty), wrote the first lines of its report to the standard output, ended with an uncaught exception on a file of unknown type, and reported a total cost also for an unbounded problem; the test dimacs_solver_unbounded checks that the report of such a problem has no cost.

22.3 dimacs-to-lgf

Next, dimacs-to-lgf converts a DIMACS file into an LGF file (§21.1), and it has no option besides the input and the output file. It reads the problem by dimacsType() and by the reader of its type, all values being of type double, into a SmartDigraph, and it writes the digraph by DigraphWriter with the maps and attributes of Table 22.2; the nodes are labeled by their ids, i.e., by the numbers of the DIMACS file minus one.

Type Node maps Arc maps Attributes
min supply lower, capacity, cost problem = min
max capacity source, target, problem = max
sp capacity (the lengths) source, problem = sp
mat problem = mat

Table 22.2. The contents of the LGF file written by dimacs-to-lgf, by type of the DIMACS file.

Two remarks are in order. First, the infinite capacities of a min or max file are written as the infinity of double, i.e., as the token inf; whether a program can read this token back depends on the operator>> of its standard library, and it may need a converter (§21.2). Second, the values are written with the default conversion, i.e., with 6 significant digits (§21.3), which is exact for the integer data of the usual DIMACS instances below \(10^6\) but not for larger or fractional values. As dimacs-solver does, the tool catches the exceptions of LEMON: a file that cannot be opened, a file of unknown type (on which dimacsType() throws FormatError), or a max or sp file without its source or target (which the writer cannot label, after it has written the sections before the attributes) ends it with a message on the standard error and the exit status 1.

abLEMON

In LEMON 1.3.1, dimacs-to-lgf caught no exception, and these files ended it with an uncaught exception; the tests dimacs_to_lgf_unknown_dimacs and dimacs_to_lgf_nosource_max check the message.

22.4 lgf-gen

Finally, lgf-gen generates random plane graphs, i.e., graphs whose nodes are points of the plane, and writes them as LGF files with the coordinates of the nodes, optionally with an EPS drawing. It is a convenient source of test instances for the geometric and graph algorithms of the library.

Option Meaning Default
-n N number of nodes 100
-disc, -square, -gauss the nodes uniformly in the unit disc, uniformly in the square \([-1,1]^2\), or by a two-dimensional Gaussian distribution -disc
-cities k the nodes in \(k\) clusters, with random centres and sizes 1
-area a the scale of the clusters (their full relative area) 1
-2con, -tree, -tsp, -tsp2, -dela the edges: a planar graph built by short disjoint paths, a minimum spanning tree, a TSP tour, a tree-based TSP tour, the Delaunay triangulation no edges
-g d the girth parameter of -2con 10
-dir write a digraph, each edge as two opposite arcs off
-eps also write prefix.eps off
-nonodes draw only the edges in the EPS file off
-rand, -seed s seed the generator with the time, or with s the default seed

Table 22.3. The options of lgf-gen; the distributions, the algorithms and the two ways of seeding form three exclusive groups. The only file argument is the prefix of the output files, lgf-gen-out by default.

Thus, the nodes are placed first. With \(k\) clusters, each cluster \(s\) receives a random weight \(w_s\), uniform in \([0,1)\), and a share of the \(N\) nodes proportional to it; its centre is a random point of the unit disc (the origin when \(k=1\)), and its points are drawn by the chosen distribution and scaled by \(a\sqrt{w_s/\sum_r w_r}\). Then the edges are built by the chosen algorithm, the lengths being the Euclidean distances, as follows.

Algorithm 22.2 (The edges of lgf-gen).

-dela : the Delaunay triangulation of the points (delaunay() of the tool)
-tree : the Delaunay triangulation; keep the spanning tree that
        kruskal() finds on the squared lengths
-tsp  : the cycle of the nodes in the order of creation, improved by
        2-opt moves of gain larger than 1e-8 until none applies
-tsp2 : the tree of -tree; scan the pairs of its nodes of odd degree by
        increasing distance, and join a pair when both ends are still odd;
        shortcut the Euler tour of the result to a tour; improve it by 2-opt
-2con : for each pair of nodes by increasing length: add the edge if it
        crosses no edge already added and the two nodes do not have two
        edge-disjoint paths of total length at most d (Suurballe, unit
        lengths); then, in reverse order of addition, remove each edge
        whose ends keep two such paths without it

The algorithm -2con takes \(d\) from -g, and Suurballe is the algorithm of chapter 10. The algorithms -tsp and -tsp2 need at least 3 nodes, and with fewer the tool ends with a message and the exit status 1, while with no node -dela and -tree give the empty graph. At the end, the tool prints the number of nodes and edges and the total length of the edges, and, for -tsp and -tsp2, the number of 2-opt moves; these reports go to the standard output. It writes prefix.lgf, by GraphWriter, or by DigraphWriter with -dir; the only node maps are coordinates_x and coordinates_y, the coordinates multiplied by 600. With -eps, it also writes prefix.eps by graphToEps() (§21.7), scaled to an A4 page, without prescaling, with the node scale 0.005 and the arc width scale 0.001. The help of the tool calls the graph of -2con "two connected"; what the procedure guarantees is the following.

Lemma 22.2. (i) The graph of -2con has no two crossing edges. (ii) In -tsp2, every node has even degree after the pairing. (iii) The 2-opt phases of -tsp and -tsp2 terminate after at most \(\ell_0/10^{-8}\) moves, where \(\ell_0\) is the length of the starting tour.

Proof. (i) An edge is added only if it crosses no edge already present, and the second phase only removes edges. (ii) An edge is added only between two nodes that are odd at that moment, which makes both even; hence a node that becomes even stays even. If two nodes \(a\) and \(b\) were odd at the end, they would have been odd throughout the scan, and the pair \(\{a,b\}\), which is scanned, would have been joined. (iii) Each move decreases the length of the tour by more than \(10^{-8}\), and the length stays nonnegative. \(\square\)

The -2con graph is not necessarily 2-connected: an edge is left out when its ends already have two edge-disjoint short paths, and a later removal may destroy one of them. Its construction scans the \(N(N-1)/2\) pairs, and each of them costs a scan of the edges for the crossings and possibly a run of Suurballe, so that it is by far the slowest of the five algorithms.

abLEMON

In LEMON 1.3.1, -tsp2 with fewer than 3 nodes read before the list of the odd nodes, whose size less 1 wrapped around when it was empty, -tsp with 1 or 2 nodes did not end, and -dela and -tree with no node read a null pointer; the tests lgf_gen_tsp2_one, lgf_gen_dela_empty and lgf_gen_tree_empty run these cases.

22.5 lemon-0.x-to-1.x.sh and the demos

We now turn to lemon-0.x-to-1.x.sh, which helps to port a program written for the old series 0.x of LEMON: it rewrites in place each file given as an argument by a long sequence of sed substitutions, and with no argument, or with -h, -help or --help, it prints its usage. The substitutions rename the graph concepts of the old series: a graph becomes a digraph, an undirected graph a graph, an edge an arc and an undirected edge an edge, and the A- and B-nodes of the bipartite graphs become red and blue nodes. They also rename the headers (e.g., digraph_adaptor.h becomes adaptors.h and topology.h becomes connectivity.h), the named template parameters Def* into Set*, the adaptors into their current names (e.g., SubDigraphAdaptor becomes SubDigraph and ResDigraphAdaptor becomes ResidualDigraph), several maps (e.g., InvertableMap becomes CrossRefMap), and the LP classes (LpGlpk becomes GlpkLp, and so on). Since the substitutions are textual, the result must be read and compiled; in particular, the words graph and edge in the comments are renamed too.

Each of the three demos of demo/ is a short program that shows the use of one tool of the library. First, arg_parser_demo declares options of all the kinds of ArgParser (a mandatory integer -n, doubles with and without a reference, a synonym, a string, switches, an exclusive and mandatory group of three options and the file arguments), parses the command line with throwOnProblems(), and prints what it found. Then graph_to_eps_demo builds a small digraph and writes seven EPS files, graph_to_eps_demo_out_1_pure.eps to graph_to_eps_demo_out_7_colors.eps, which show the plain drawing, the sizes, shapes, colors and widths given by maps, the arrowheads, the parallel arcs, the fit to an A4 page and, on a second graph, the colors of a Palette with the texts of the nodes in distant colors. Finally, lgf_demo reads the digraph, the capacities and the source and target of the file digraph.lgf of the directory of the demos, which it must be started from, and writes them back on the standard output.

22.6 An example

The program manual/examples/22-tools.cc (the test manual_22_tools) does, on a small minimum cost flow problem, what two of the tools do. It declares the options of dimacs-solver and parses a given command line with them, reads a DIMACS min file from a string with an arc of infinite capacity, chooses the supply type by the sign of the sum of the supplies as in Algorithm 22.1 (the supplies are integer, so that the tolerance of line 4 plays no role), and solves the problem by NetworkSimplex. Then it writes the problem as dimacs-to-lgf writes it, reads the LGF text back, and checks the costs and the attribute problem.

22.7 Exercises

Exercise 22.1. Generate a Delaunay triangulation with lgf-gen -dela -n 1000, read it by GraphReader with the coordinates, and check that its number of edges is at most \(3N-6\), as for any simple plane graph (and that PlanarityChecking of chapter 18 accepts it).

Exercise 22.2. Generate a TSP tour with lgf-gen -tsp and with lgf-gen -tsp2 on the same seed, and compare their lengths with the tours of the classes of chapter 19 on the same points (read by GraphReader, with the costs given by the coordinates).

Exercise 22.3. Write a min file whose supplies sum to a positive value, and check that dimacs-solver announces the type LEQ and finds the same cost as a program that solves the problem by NetworkSimplex with this supply type (manual/examples/22-tools.cc).

Exercise 22.4. Convert a max file with an arc of negative capacity by dimacs-to-lgf, and read the result back by DigraphReader with a converter that maps the token inf to a large finite capacity; check that Preflow gives the same value as dimacs-solver on the original file.

Exercise 22.5. Look for a seed on which lgf-gen -2con gives a graph that is not 2-connected, as the remark after Lemma 22.2 allows, testing the graphs with biNodeConnected() of chapter 18.

Exercise 22.6. Run arg_parser_demo without the mandatory option -n, with two options of the group -gra, -grb, -grc, and with none of them, and explain each message from the declarations of the demo.