Skip to content

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).