We use the popular Metis input/output formats for I/O (and extend them in
certain cases). This applies to files for
input graphs and solutions (partition/cluster assignments). All files are simple
ASCII text files. In the following descriptions, n denotes the number
of vertices in the graph.
Graph Format
Note that for the Challenge the input graphs might be seen as unweighted,
i. e. weighted instances might be seen as having unit weights for both vertices
and edges. Details on this aspect will be announced later.
Following the
Metis User's Guide, Version 4.0, the graph files may contain
comment lines that begin with the character '%'. Such lines are ignored.
At its simplest a correct input contains n+1 uncommented lines. The first
of these lines contains either two, three, or four integers, separated by space.
The first two obligatory entries are the number of vertices and
the number of edges in the graph. Note that in this case the number of edges is only half of
the sum of the vertex degrees. The third and fourth parameter in the first line are optional
and control input of weighted graphs. For details on weighted graphs
see Section 4.5.1 of the
Metis User Guide, Version 4.0.
Important:
There is one exception to the use of the format described in Section 4.5.1. If the
graph contains self-loops and/or multiple edges, the third parameter in the first line
is set to 100. Since Metis does not allow such graphs, this extension of the format
is necessary. To exclude these graphs upfront would mean to exclude many real-world instances.
Also note that in this case the second parameter is the actual number of edge entries in the
file, i. e., the sum of the vertex degrees. This deviation is necessary due to self-loops.
They do not appear twice in the file, as undirected (= bidirected) edges do.
In the unweighted case, the remaining n lines contain neighbor lists
for each vertex from 1 to n in order. These lists are sets of integers
separated by spaces and contain all the neighbors of a given vertex. The neighbors
may be listed in any order. Note that vertices are numbered 1 to n,
not from 0 to n-1.
For possible extensions, please refer again to Section 4.5.1 in the
Metis User Guide, Version 4.0. You will find there examples of small graphs
and their respective representations, too.
Output Format
The partition/cluster assignment files have n uncommented lines.
In line i the assignment value for vertex i is given as an integer
between 0 and p-1, where p is the number of partitions.
Geometry Format
Vertex coordinates can optionally be supplied in a separate file. This file should
have the same name as the graph file. But instead of the file extension
.graph, the coordinate file has the extension .xyz.
These coordinate files must have n uncommented lines, with line i
containing the coordinates of vertex i. Each line must contain one, two, or
three floating-point values, depending on the geometry type.
