LEDA graph input/output format

Sven Thiel

October 15, 1999

The following passage describes the format of the output produced by the function graph::write(ostream& out). The output consists of several lines which are separated by endl. The output can be partitioned in three sections:

1.

header section:
The first line always contains the string "LEDA.GRAPH". If the graph type is not parameterized, i.e. graph or ugraph, the following two lines both contain the string "void". In case the graph is parameterized, i.e. GRAPH or UGRAPH, these lines contain a description of the node type and the edge type, which is obtained by calling the macro LEDA_TYPE_NAME.

2.

nodes section:
The first line contains n, the number of nodes in the graph. The nodes are ordered and numbered according to their position in the node list of the graph. Each of the following n lines contains the information which is associated with the respective node of the graph. When the information of a node (or an edge) is sent to an output stream, it is always enclosed by the strings "|{" and "}|". If the graph is not parameterized, then the string between these parantheses is empty, so that all the n lines contain the string "|{}|".

3.

edges section:
The first line contains m, the number of edges in the graph. The edges of the graph are ordered by two criteria: first according to the number of their source node and second according to their position in the adjacency list of the source node. Each of the next m lines contains the description of an edge which consists of four space-separated parts:

(a)

the number of the source node

(b)

the number of the target node

(c)

the number of the reversal edge or 0, if no such edge is set

(d)

the information associated with the edge (cf. nodes section)

Note: For the data type planar_map the order of the edges is important, because the ordering of the edges in the adjacency list of a node corresponds to the counter-clockwise ordering of these edges around the node in the planar embedding. And the information about reversal edges is also vital for this data type.