21. Input and output¶
This chapter describes how graphs and the data attached to them are read from
and written to files. The format of the library is the LEMON Graph Format
(LGF), read by the classes of lgf_reader.h and written by those of
lgf_writer.h (§21.1 to §21.4).
Besides it, dimacs.h reads the formats of the first DIMACS implementation
challenge and writes one of them (§21.5),
nauty_reader.h reads the graph6 format of the nauty package
(§21.6), and graph_to_eps.h draws a graph in
Encapsulated PostScript (§21.7). A malformed input makes
the readers and the writers throw FormatError, and a file that cannot be
opened makes them throw IoError (chapter 8); both
derive from Exception.
21.1 The LEMON Graph Format¶
An LGF file is a text file made of sections, each opened by a header line
whose first character is @, followed by the type of the section and by an
optional name, the caption, which distinguishes sections of the same type. A
line whose first non-blank character is # is a comment, and the empty lines
are ignored; whatever precedes the first header is skipped. The standard types
are @nodes, @arcs (with its synonym @edges) and @attributes for
digraphs and graphs, and @red_nodes and @blue_nodes for the two node sets
of a bipartite graph. A file may contain other sections, whose content is free
(§21.4).
Standard sections are made of tokens separated by white space. A token is
either plain, i.e., a sequence of characters other than white space, or
quoted, i.e., enclosed in double quotes, in which case it may contain white
space. In both kinds a backslash introduces an escape sequence of C: \\,
\", \', \?, \a, \b, \f, \n, \r, \t, \v, a character in
octal (one to three digits) or in hexadecimal (\x with one or two digits).
Moreover, the node and arc sections are column oriented: their first line
gives the names of the maps, and each following line, up to the next header,
gives the values of these maps for one item. A short file shows the structure:
@nodes
label name
0 "the source"
1 a
2 t
@arcs
label capacity
0 1 0 16
0 2 1 12
1 2 2 4
@attributes
source 0
target 2
In a node section, the map named label plays a special role, since its
values identify the nodes in the rest of the file; it is needed whenever the
arcs or the attributes refer to the nodes. In an arc section, each line starts
with the labels of the source and of the target node, followed by the values
of the maps; the map label is optional here, and it identifies the arcs for
the attributes. An arc section without maps must contain a single - in its
first line (in a node section, a - would be read as the name of a map). For
an undirected graph, the section @edges (or @arcs) describes the edges,
and two columns whose names are the name of a map prefixed with + and -
hold the values of an arc map on the two arcs of each edge. Each line of the
section @attributes consists of two tokens, a name and a value. The value
may be the label of a node or of an edge, and the label of an edge prefixed
with + or - refers to the forward or the backward arc of that edge. For a
bipartite graph, the sections @red_nodes and @blue_nodes replace @nodes,
each with its own maps; a map present in both sections can be read as a node
map.
21.2 Reading¶
We now describe DigraphReader< DGR >, which reads an LGF file into a digraph
of type DGR (exported as Digraph) by batch processing. One creates a
reader, adds to it the rules that specify which maps and attributes are wanted
and where they go, and executes them by run(), which reads the file once.
The functions that add the rules return a reference to the reader, and are
therefore chained:
DigraphReader< ListDigraph >( g , std::cin )
.arcMap( "capacity" , cap ).node( "source" , s ).run();
Its three constructors take the digraph and an input stream (by default
std::cin), a file name as a std::string or a file name as a const char
*; the last two open the file and throw IoError when they cannot. With the
same three kinds of source, digraphReader() returns a reader, which lets one
write the chain without naming the type (the reader returned is moved, not
copied, and a reader whose stream has been taken over by another one may not
be run).
abLEMON
The readers and the writers take over the stream of the object returned by
digraphReader() and the like through a constructor that takes it by
rvalue reference, which C++23 requires; in LEMON 1.3.1 it took a
non-constant lvalue reference, and the LGF classes did not compile under
C++23 (version 1.4.0).
We now list the reading rules. A rule nodeMap( caption , map ) reads the
column caption of the node section into map, a writable node map, and
arcMap( caption , map ) does the same for the arc section. One column can be
read into several maps. The value of each token is converted to the value type
of the map by operator>> of a std::istringstream, and the token must be
read whole, i.e., a token that cannot be converted, or that leaves characters
behind, throws FormatError. A token read into a std::string is taken as it
is. The overloads nodeMap( caption , map , converter ) and
arcMap( caption , map , converter ) take instead a functor from
std::string to the value type. The rules attribute( caption , value ) and
attribute( caption , value , converter ) read an attribute into a variable,
and node( caption , n ) and arc( caption , a ) read an attribute whose
value is a label into a node or an arc handle.
By default the reader uses the first section of each type. The functions
nodes( caption ), arcs( caption ) and attributes( caption ) select
instead the section of that type with the given caption. With
useNodes( map ) the nodes are taken as already existing, and they are not
created. Then map gives the label of each existing node (its values are
turned into strings by operator<<, or by a converter in the overload
useNodes( map , converter )), and the node section only identifies the nodes
by their labels, reading the other maps into them. Similarly, useArcs( map )
and useArcs( map , converter ) reuse the existing arcs. These functions
allow a multipass reading, e.g., to read a node set and one arc section into
a digraph in a first pass, and a second arc section into an arc set of
chapter 4 in a second pass. The functions skipNodes()
and skipArcs() leave a section out, i.e., the nodes are then not created,
and the arcs can only be read if useNodes() gives the labels.
Algorithm 21.1 (The reading of an LGF file by
run()).
1 read lines up to the first header (skipSection)
2 while a header "@type caption" has been read:
3 if type = nodes, no node section read yet, and the caption matches:
4 read the map names; for each line up to the next header: read one
token per map; create a node (or find the node of its label, with
useNodes); store its label; apply the node rules (readNodes)
5 elif type is arcs or edges, likewise, the first two tokens of a line
being the labels of the source and of the target (readArcs)
6 elif type = attributes, likewise: each line is a name and a value,
given to all the rules of that name (readAttributes)
7 else skip the section
8 throw FormatError if the node or the arc section was not read (unless
skipped), or if attribute rules exist and no attribute section was read
Note that the checks are rather strict. A map named by a rule and absent from
the header, a column missing in a line, an extra token at the end of a line, a
label not found, a label repeated in a node section, a map name repeated in a
header and an attribute repeated in its section all throw FormatError; so
does an attribute required by a rule and absent from the section. In all
cases, the error carries the line number and, when the reader was opened on a
file, the file name, and its what() gives both. A label repeated in an arc
(or edge) section, which files that use the label column as a dummy contain,
names no arc: the arcs are read, and an attribute that refers to the label
throws FormatError, since it is not found.
abLEMON
In LEMON 1.3.1, a label repeated in a node or an arc section was not
detected: the item read first kept it, and the later references went to
that item; the test lgf_test reads both kinds of repetition.
Theorem 21.1. Algorithm 21.1 reads each line of the stream once, and on success it has created one node per line of the selected node section and one arc per line of the selected arc section, in the order of the lines, with the values of the rules set on them. With \(L\) characters in the input, \(n\) nodes, \(m\) arcs and \(k\) map columns, it performs \(O(L)\) character operations, \(O((n+m)\log(n+m))\) comparisons of labels, and \(n+m\) times \(k\) conversions at most.
Proof. Every line is obtained by readLine(), which advances the stream,
and a header line is pushed back only into the buffer of the current line,
never into the stream; the outer loop handles one header per iteration, and
each of readNodes(), readArcs(), readAttributes() and skipSection()
consumes the lines up to the next header. A section with a type already read,
or with a caption that does not match, falls into the last branch and is
skipped. In readNodes() each line yields one node, created in the order of
the lines (or looked up by its label when useNodes() is given), and its
tokens are passed to the storages of the rules; readArcs() does the same,
looking up the source and the target by their labels. The labels are kept in a
std::map from the token to the item, so that each insertion (which also
finds a repeated label) and each look-up costs \(O(\log(n+m))\) comparisons,
and so does the removal of a repeated arc label at the end of its section.
Each token is converted once for each rule that reads its column. \(\square\)
For an undirected graph one uses GraphReader< GR > (exported as Graph),
which reads it in the same way, with the rules nodeMap(), edgeMap(),
attribute(), node() and edge(), the selection functions nodes(),
edges() and attributes(), and useNodes(), useEdges(), skipNodes()
and skipEdges(). Its rule arcMap( caption , map ) reads the two columns
+caption and -caption into the values of an arc map on the forward and the
backward arc of each edge, and arc( caption , a ) reads an attribute whose
value is an edge label with a sign. Similarly, BpGraphReader< BGR > reads a
bipartite graph from the sections @red_nodes, @blue_nodes and @edges,
all three of which must be present. It has the members of GraphReader, its
nodes( caption ) selects both node sections, and it adds the rules
redNodeMap(), blueNodeMap(), redNode() and blueNode(), while its
nodeMap() reads a map that both node sections contain. The functions
graphReader() and bpGraphReader() return readers as digraphReader()
does. In the code, each rule is an object of the namespace _reader_bits,
i.e., a MapStorage (or a GraphArcMapStorage, for the two columns of an arc
map) for a map, and a ValueStorage for an attribute, both converting by a
DefaultConverter unless a converter is given. The label of an attribute is
resolved by a MapLookUpConverter, a DoubleMapLookUpConverter (for a node
of a bipartite graph, searched among the red and the blue labels) or a
GraphArcLookUpConverter (for a signed edge label).
21.3 Writing¶
Symmetrically, DigraphWriter< DGR > writes a digraph in the same batch
style: the rules nodeMap( caption , map ), arcMap( caption , map ),
attribute( caption , value ), node( caption , n ) and
arc( caption , a ), executed by run(). Its constructors take the digraph
and an output stream (by default std::cout) or a file name, and throw
IoError when the file cannot be opened; digraphWriter() returns a writer
in the same three ways. Each value of a map or of an attribute is converted to
a token by operator<< of a std::ostringstream, or by a functor from the
value type to std::string given as the third argument of the rule. A token
that is empty, starts with @ or #, or contains white space or one of the
characters \, ", ', \a and \b, is written quoted. Its characters are
written with the escapes \\, \", \a, \b, \f, \n, \r, \t, \v
and the octal code, in three digits, of any other character below 32, the
other characters (the bytes above 127 included) as they are, and the tokens
that need no quotes are written as they are. We remark that the default
conversion writes a double with the default precision of the streams, i.e.,
6 significant digits, so that a file written with it does not give back the
same values when it is read; a converter that writes 17 significant digits (as
the program of §21.8 does) avoids this.
Lemma 21.1. Let \(s\) be a string of characters. Then the token that the writer writes for \(s\) is read back by the reader as \(s\).
Proof. If the writer does not quote \(s\), then \(s\) is not empty, does not
start with @, # or ", and contains no white space and no backslash; the
reader reads a plain token up to the next white space, i.e., \(s\), and finds no
escape in it. If the writer quotes \(s\), then each \ and " of \(s\) is
written as a two-character escape that the reader maps back, each of the seven
control characters as its letter escape, which the reader maps back, every
other character below 32 as a backslash and three octal digits, which the
reader reads as one escape of at most three digits and maps back, and every
other character of \(s\) as it is. The reader stops at the first " that is not
escaped, which is the closing one. In both cases the token is followed by
white space or by the end of the line, so that the next token does not absorb
its last character, and a line never starts with a plain token that starts
with #, which would make it a comment. \(\square\)
abLEMON
In LEMON 1.3.1, the writer wrote a character below 32 in octal without
padding to three digits, so that a following digit from 0 to 7 was read
as part of the escape, and a byte above 127, e.g., of a UTF-8 text, as the
octal code of a negative number, and it wrote plain a token starting with
#, so that a line whose first column was such a token was read as a
comment; the test lgf_reader_writer_test reads such tokens back. Also,
the reader accepted any letter after \x as a hexadecimal digit (\xg
was the character 16); the test lgf_test checks that it is an error.
Each item gets a label from the writer. If a map is written under the name
label, its values are the labels, and the items are written in the order of
these values (an order that operator< must define, otherwise FormatError
is thrown at run time). Otherwise the writer adds a column label with the
ids of the items, and writes them in the order of the ids. Hence, the arc
section always has the label column, and therefore it never needs the - of
§21.1. The functions nodes( caption ),
arcs( caption ) and attributes( caption ) give a caption to the sections,
skipNodes() and skipArcs() leave a section out (its labels are still
computed, for the sections that follow). Also, ostream() returns the stream
of the writer. These allow writing two arc sections in two passes on the same
stream: the second writer skips the nodes and appends its arc section to the
output of the first.
Theorem 21.2. run() of DigraphWriter
writes each node and each arc once, in the order of their labels (or of their
ids), with distinct labels when the ids are used, in \(O((n+m)\log(n+m))\)
comparisons plus one conversion per value written.
Proof. The writer collects the items of each section in a vector and sorts
it, by the comparator MapLess (or GraphArcMapLess) on the label map when
it is given, and by the ids otherwise. The ids are distinct, and hence so are
the labels it adds. The labels of the nodes are then kept in a std::map to
write the source and the target of each arc and the attributes that refer to
items, with \(O(\log n)\) comparisons per look-up. \(\square\)
Note that the writer keeps the maps and the values of the rules by reference,
and reads them only in run(). Thus, they must exist until then. A temporary
passed to a rule lives until the end of the full expression that contains it;
this is enough in a chain that ends with run(), but not when the rules and
run() are separated.
abLEMON
The documentation of the writers states that the values of their rules are kept by reference; in LEMON 1.3.1 the test of the format passed a temporary arc to a writer, which read it after its end (trac #683, version 1.4.0).
For an undirected graph, GraphWriter< GR > is used, with edgeMap() and
edge() for the edges and an arcMap() that writes the columns +caption
and -caption; the rule arc( caption , a ) writes the label of the edge of
a with the sign of its direction, and nodes(), edges(), attributes(),
skipNodes(), skipEdges() and ostream() work as for digraphs. Similarly,
BpGraphWriter< BGR > (exporting the type as BpGraph) writes the sections
@red_nodes, @blue_nodes and @edges, with the rules redNodeMap(),
blueNodeMap(), redNode() and blueNode(); its nodeMap() writes the map
in both node sections, and its nodes( caption ) gives the caption to both.
The functions graphWriter() and bpGraphWriter() return writers. Their
rules are objects of the namespace _writer_bits with the same names as those
of the readers (MapStorage, GraphArcMapStorage, ValueStorage,
MapLookUpConverter, DoubleMapLookUpConverter and
GraphArcLookUpConverter), and the items are sorted by their labels through
the comparators MapLess and GraphArcMapLess.
21.4 Extra sections and the contents of a file¶
Sections of other types are read by SectionReader and written by
SectionWriter, which are constructed, like the other readers and writers,
from a stream or a file name, or returned by sectionReader() and
sectionWriter(). In a SectionReader, sectionLines( type , functor )
gives each line of the section @type to a functor that takes a
std::string, after the empty lines and the comments have been removed and
the leading white space trimmed. Instead, sectionStream( type , functor )
calls once a functor that takes the std::istream & and an int & line
number, which it reads from and updates. A section is read at most once (a
second section of the same type throws FormatError), and run() throws
FormatError when a section with a rule is missing. In a SectionWriter,
sectionLines( type , generator ) writes the strings returned by a functor
without arguments until it returns an empty string, while
sectionStream( type , functor ) lets a functor write to the stream, its last
line ending with a newline. The two kinds of rules are stored as objects of
the classes LineSection and StreamSection of the namespaces _reader_bits
and _writer_bits, derived from a class Section. These classes act on the
extra sections only, and they can be run on the same file as the graph
readers, which skip the sections they do not know.
Finally, LgfContents reads a file without knowing its contents and records
its structure, for general tools that must guess what a file holds; it is
constructed from a stream or a file name. After run(), nodeSectionNum(),
nodeSection( i ) and nodeMapNames( i ) give the number of node sections,
the caption of the \(i\)-th one and the names of its maps; arcSectionNum(),
arcSection( i ) and arcMapNames( i ) do the same for the arc and edge
sections, with the synonyms edgeSectionNum(), edgeSection( i ) and
edgeMapNames( i ). Also, attributeSectionNum(),
attributeSectionNames( i ) and attributes( i ) describe the attribute
sections, and extraSectionNum() and extraSection( i ) give the types of
the other sections.
21.5 The DIMACS formats¶
We now turn to the formats of the first DIMACS implementation challenge
(Johnson and McGeoch 1993). They
are line oriented: a line starting with c is a comment, the line
p type n m gives the type of the problem and the numbers of nodes and arcs,
a line starting with n describes a node, and a line starting with a an
arc, the nodes being numbered from 1. A call of dimacsType( is ) reads the
comments and the problem line, and returns a DimacsDescriptor, whose fields
are the type (NONE, MIN, MAX, SP or MAT, of the enumeration
DimacsDescriptor::Type), the nodeNum, the edgeNum and the lineShift,
the number of lines it has read. An unknown type, a missing problem line or
another line before it throws FormatError. Each reader takes the descriptor
as its last, optional, argument. Without it (i.e., with the default descriptor
of type NONE), the reader calls dimacsType() itself, and with it, the
reader continues on the stream where dimacsType() stopped. A reader clears
the graph, creates the \(n\) nodes in order, and throws FormatError when the
type of the file is not the one it reads, and when a node number of an n or
an a line is outside \([1,n]\).
| Function | Type | Lines read | Data written |
|---|---|---|---|
readDimacsMin(is, g, lower, capacity, cost, supply, infty, desc) |
min |
n id supply, a u v low cap cost |
lower bounds, capacities, costs, supplies (0 when absent) |
readDimacsMax(is, g, capacity, s, t, infty, desc) |
max |
n id s, n id t, a u v cap |
capacities, source, target |
readDimacsSp(is, g, length, s, desc) |
sp |
n id, a u v len |
lengths, source |
readDimacsCap(is, g, capacity, infty, desc) |
max or sp |
a u v cap |
capacities (or lengths) |
readDimacsMat(is, g, desc) |
mat |
a u v |
the arcs (or edges) |
Table 21.1. The DIMACS readers of dimacs.h;
the problem line and the comments are read as described in the text.
An infinite capacity is written in the DIMACS files in two ways, and the
readers translate both into the value infty. In a min file, an arc whose
capacity is smaller than its lower bound gets the capacity infty, and in a
max file (also through readDimacsCap()) an arc with a negative capacity
gets it, while the lengths of an sp file are kept as they are. When infty
is 0, its default, the readers take
std::numeric_limits< Capacity >::infinity() if the type has an infinity, and
its maximum value otherwise. The source and the target of readDimacsMax()
and readDimacsSp() are INVALID when the file has no n line for them. As
for readDimacsMat(), it adds an edge for each a line to an undirected
graph, and an arc to a digraph, and it reads only the a lines. A line that
starts with another letter, e.g., the e lines that some matching and clique
files use, is skipped one character at a time, which is harmless for lines of
numbers but misreads a later a, c or n on the same line. Conversely,
writeDimacsMat( os , g , comment ) writes a digraph in the format mat,
i.e., an optional comment line, the problem line, and one a line per arc;
the nodes are numbered from 1 in the order of the node iterator.
Theorem 21.3. On a file whose node numbers lie
between 1 and the \(n\) of its problem line, each reader of Table 21.1 builds a
graph with \(n\) nodes, the node of number \(k\) being the \(k\)-th created, and one
arc (or edge) per a line, in the order of the lines, in \(O(L+n)\) time for
\(L\) characters; on any other file it throws FormatError at the first line
with a number outside \([1,n]\).
Proof. The reader creates the \(n\) nodes in a vector indexed by their
numbers, and then reads the stream once. Each a line adds one arc between
the nodes of its two numbers and sets its data, each n line sets a supply or
a source or target, each c line is skipped by getline(), and each step
consumes at least one character. Each number is compared with the bounds of
the vector before it indexes it, in \(O(1)\). \(\square\)
abLEMON
dimacsType() is inline, and hence two translation units that include
dimacs.h link together, which they did not in LEMON 1.3.1 (version
1.4.0). Also, in LEMON 1.3.1 the readers did not check the node numbers,
and a number outside \([1,n]\) indexed the vector of the nodes out of its
bounds; the test dimacs_test reads such numbers in every kind of
line.
21.6 The graph6 format of nauty¶
Our next format comes from the program geng of the nauty package (McKay and
Piperno 2014), which generates all
the non-isomorphic undirected graphs of a class with a given number of nodes,
writing one graph per line in the graph6 format. A call of
readNautyGraph( graph , is ) reads one line of the stream (by default
std::cin) and builds the graph it describes, after clearing graph. It
returns the stream, and it can thus be used as the condition of a loop that
reads a whole file. In graph6, each character carries six bits, its code minus
63, and the upper triangle of the adjacency matrix is listed column by column.
Thus, the pairs \(\{i,j\}\), \(i<j\), in the order
\((0,1),(0,2),(1,2),(0,3),\dots\), padded with zeros to a multiple of six bits.
Algorithm 21.2 (The decoding of a graph6 line).
1 skip the header ">>graph6<<" (10 characters) if the line starts with '>'
2 c := next character - 63
3 if c < 63: n := c
4 else if the next character is '~': n := the 36 bits of the six characters
after it (minus 63 each)
5 else: n := the 18 bits of the next three characters (minus 63 each)
6 if the line is shorter than its header, its n or its ceil(n(n-1)/12)
characters of edges, or n is beyond int: leave the graph empty, fail
the stream, return
7 create n nodes
8 for j := 1 to n - 1, for i := 0 to j - 1:
9 take the next bit, from the most significant of each character;
if it is 1, add the edge {i, j}
Lemma 21.2. On a line of the graph6 format
with a number \(n\) of nodes that an int holds, Algorithm 21.2 builds the
graph of the line, with its edges in the order of the pairs, in \(O(n^2)\) time;
on a line too short it reads no character past its end.
Proof. The pairs \(\{i,j\}\) with \(i<j\) are taken in the order of \(j\) and, for
each \(j\), of \(i\), which is the order of the format. The \(k\)-th bit of the
sequence is the bit \(5-(k\bmod 6)\) of the character \(\lfloor k/6\rfloor\) after
the header and the size; hence the edge \(\{i,j\}\) is added exactly when its
bit is 1. Since a size of 18 bits is below \(63\cdot2^{12}=258048\), its first
character is not ~, and lines 3 to 5 tell the three forms of the size apart.
Line 6 compares the length of the line with the \(1\), \(4\) or \(8\) characters of
the size and with the \(\lceil n(n-1)/12\rceil\) characters of the \(n(n-1)/2\)
bits before reading them. The loop takes \(n(n-1)/2\) steps. \(\square\)
For instance, the line D~{ describes the complete graph on 5 nodes: D
gives \(n=68-63=5\), and ~{ give the bits 111111 and 1111 of the 10 pairs,
followed by two bits of padding. A line too short for its header, its number
of nodes or its edges leaves the graph empty and sets the failbit of the
stream; so does a number of nodes of the form of 36 bits beyond the range of
int. The header suggests to pipe the output of geng into the program,
since the files are large.
abLEMON
In LEMON 1.3.1 a line too short was read past its end, and the form of
the size for \(n\ge 258048\), with 36 bits after two characters ~, was
not read, the size being misread; the test nauty_reader_test reads
complete and truncated lines, and the sizes of 18 and of 36 bits.
21.7 Drawing a graph in EPS¶
A call of graphToEps( g , os ) draws a graph or a digraph as an Encapsulated
PostScript picture on a stream (by default std::cout); the overloads
graphToEps( g , file_name ), with a std::string or a const char *, write
to a file, which they open and throw IoError when they cannot open it; the
file is flushed by run() and closed with the last of the objects of the
chain below, also when run() is not called. The function returns an object
of the class GraphToEps< T >, where T is the traits class
DefaultGraphToEpsTraits< GR > that holds the parameters. The member
functions of this class set the parameters of the picture by the technique of
the named parameters (chapter 3), and its run()
writes the picture. Nothing is written without run(), which therefore must
close the chain:
graphToEps( g , "flow.eps" ).coords( coords ).arcWidths( cap )
.autoArcWidthScale().drawArrows().title( "a flow problem" ).run();
The maps of the picture are given by functions that return a new object with
the type of the map, and they are kept by reference. The object on which such
a function is called is left inert, i.e., its run() writes nothing, so that
the chain must continue on the returned object. First, coords( map ) gives
the position of each node, a node map with values of type dim2::Point
(chapter 8), without which all the nodes are drawn at
the point \((1,1)\). Then nodeSizes( map ), nodeShapes( map ),
nodeColors( map ), nodeTexts( map ), nodeTextColors( map ) and
nodePsTexts( map ) set the size, the shape (of the enumeration NodeShapes:
CIRCLE, SQUARE, DIAMOND, MALE, FEMALE, i.e., 0 to 4), the color, a
text written on the node (of any type that operator<< writes), its color,
and a block of PostScript code drawn at the node, which
nodePsTextsPreamble( str ) may precede with a block of definitions. Also,
arcWidths( map ) and arcColors( map ) set the width and the color of the
arcs. Colors are objects of the class Color of color.h, and a Palette
composed with an integer map (composeMap(), chapter 6)
gives distinct colors.
Other parameters are set by functions that return the same object. Usually one
scales the sizes by nodeScale( d ) (0.01 by default) and
arcWidthScale( d ) (0.003). Both are relative to the diagonal of the
bounding box of the nodes, unless absoluteNodeSizes() and
absoluteArcWidths() make them absolute, and autoNodeScale() and
autoArcWidthScale() rescale them so that the largest size equals the scale.
Similarly, scale( d ) scales the picture (1 by default); by default, the
prescaling divides the scale by 10 while a side of the bounding box exceeds
1000 points, and then multiplies it by 10 while a side of positive length is
below 100, so that a picture whose sides differ by more than a factor of 10
may keep a side above 1000; preScale( false ) turns this off. Also,
scaleToA4() fits the picture to an A4 page, border( b ) and
border( x , y ) set the margin (10 points by default), and negateY() flips
the vertical axis. As for the arcs, drawArrows() draws the arrowheads, whose
size arrowLength( d ) (1 by default) and arrowWidth( d ) (0.3) set, and
enableParallel() draws parallel arcs as distinct curves at the distance
parArcDist( d ) (1 by default). Moreover, hideNodes() and hideArcs()
leave the nodes or the arcs out, nodeTextSize( d ) sets the size of the
texts (1 by default), and distantColorNodeTexts() and distantBWNodeTexts()
color each text so that it stands out on its node. The functions
undirected() and directed() choose whether the edges of an undirected
graph are drawn once (the default for undirected graphs) or as two arcs, and
title( t ) and copyright( t ) write the DSC fields %%Title and
%%Copyright of the header, which also gets the creation date. Also,
edgeWidths(), edgeColors(), edgeWidthScale(), autoEdgeWidthScale(),
absoluteEdgeWidths(), parEdgeDist() and hideEdges() are aliases of the
functions on the arcs. On a graph with no node the bounding box is the single
point \((0,0)\), which the prescaling leaves as it is. The demo
graph_to_eps_demo (chapter 22) uses most of these
parameters.
abLEMON
In LEMON 1.3.1, the prescaling also looked at a side of length 0, which
stays below 100 points at any scale, and multiplied the scale by 10 up to
infinity, so that on a graph with no node, or with nodes of no size on a
line, it wrote a meaningless %%BoundingBox; the test
graph_to_eps_test checks the bounding box of both. Also, the stream
of the file opened by the overloads was deleted only by run(), and
without it the stream was lost and the file never closed; the same test
counts the deletions of such a stream with run() and without it.
21.8 Examples¶
The program manual/examples/21-lgf.cc (the test manual_21_lgf) writes a
network with integer capacities, floating-point costs, a name for each node
(one of which contains a blank and is therefore quoted) and the source and the
target as attributes, and reads it back into another digraph. It writes the
costs twice, once with the default conversion and once with a converter that
prints 17 significant digits, and checks that only the second gives back the
same values; then it checks that a rule for a map absent from the file throws
FormatError.
The program manual/examples/21-formats.cc (the test manual_21_formats)
reads a maximum flow instance in DIMACS format from a string, with an arc of
infinite capacity, and checks the maximum flow found by Preflow. Then it
writes the digraph in the format mat and reads it back as an undirected
graph, decodes two graph6 lines, and draws the digraph in EPS on a string,
checking the header of the picture.
21.9 Exercises¶
Exercise 21.1. Write a digraph with two arc maps
into an LGF file in two passes, each with its own arc section and caption, and
read it back into a digraph and an arc set of chapter 4
with useNodes() and arcs( caption ) (the multipass reading is exercised by
test/lgf_reader_writer_test.cc).
Exercise 21.2. Write a double map with the
default conversion and read it back; measure the largest relative error, and
explain it by the precision of the streams (manual/examples/21-lgf.cc).
Exercise 21.3. Write an undirected graph with an
arc map by GraphWriter, inspect the columns +caption and -caption, and
read the map back by GraphReader::arcMap(); then write an arc as an
attribute and read it back by arc() (test/lgf_test.cc).
Exercise 21.4. Use SectionWriter and
SectionReader to store a list of paths, one per line as a sequence of arc
labels, in an extra section of a file that also contains the digraph, and read
both back.
Exercise 21.5. Convert a min file of DIMACS
into LGF as the tool dimacs-to-lgf of chapter 22 does,
and check that NetworkSimplex (chapter 13)
finds the same optimal cost on both.
Exercise 21.6. Count the non-isomorphic
connected planar graphs with 7 nodes from the output of geng -c 7, read by
readNautyGraph() and tested by PlanarityChecking (chapter
18), and compare the count with the known value 646.
Exercise 21.7. Write a node map of strings whose values contain a blank and one of the cases excluded by Lemma 21.1 (a control character followed by a digit, or a UTF-8 letter), and observe what is read back.
Exercise 21.8. Draw a spanning tree of a random
geometric graph by graphToEps(), with the tree arcs wider and in another
color than the others, and compare the bounding box with and without
preScale() (manual/examples/21-formats.cc draws a small digraph).