

9th DIMACS Implementation Challenge
 Shortest Paths


In this page we describe the standard file format conventions for the Challenge.
We define both input file and output file formats. Input files include one or
more graph specification files and zero or more problem specification files.
Output files include performance report files and distance checksum files for
correctness checking. For each file we use the following conventions:
The following table summarizes all standard file formats defined for the Challenge:
The following table shows the current list of problems addressed in the Challenge.
More problems may be added later, depending on the interest of Challenge participants.
Graph specification formats

Node coordinates (.co files)


XY coordinates in the plane associated with
nodes of the graph can be stored in an auxiliary file having the same name
of the graph file it is related to and extension .co. For instance,
file mygraph.co would contain the node coordinates of graph mygraph.gr.
Line types are as follows. In the format descriptions below, bold characters
should appear exactly as typed: 
Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The problem line is unique and must appear as the first
noncomment line. This line has the format on the right, where n
is the number of coordinate lines that follow. 

Coord
lines 
Coordinate lines are of the form on the right, where
id , X and Y are the id of the node, its Xcoordinate,
and its Ycoordinate, respectively. 

Singlesource shortest path problem

The goal of the singlesource (SS) shortest paths problem is to find shortest
paths between a specified source node and all other nodes in the input graph.
The nonnegative singlesource (NSS) shortest paths problem is the same as the
more general SS problem, with the understanding that all arc weights in the
input graph are nonnegative.
Problem specification files
(.ss files)


The auxiliary file for the problem should have
the extension .ss. Line types are as follows. In the format descriptions
below, bold characters should appear exactly as typed: 
Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The problem line is unique and must appear as the first
noncomment line. This line has the format on the right, where n
is the number of source lines that follow. 

Source
lines 
Source lines are of the form on the right, where S
is the id of the source node. If more than one source line in file.ss
is specified, each line defines a new problem on the same graph with a different
source. 

Performance report files (.ss.res
files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (ssfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the average time T in milliseconds
required by the solver to perform each singlesource computation on the
graph specified by the previous graph line. 

Space
lines 
The line (optional) specifies the maximum space S
in kilobytes required by the data structures maintained by the solver to
perform each singlesource computation on the graph specified by the previous
graph line. 

Node
scan lines 
The line (optional) specifies the average number count
of nodes scanned by the solver to perform each singlesource computation
on the graph specified by the previous graph line. 

Arc
scan lines 
The line (optional) specifies the average number count
of arcs scanned by the solver to perform each singlesource computation
on the graph specified by the previous graph line. 

Improvement
lines 
The line (optional) specifies the average number count
of distance improvements done by the solver to perform each singlesource
computation on the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Correctness checking files
(.ss.chk files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the checking file refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (ssfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Negative
cycle lines 
The line (optional) specifies whether a negative cycle has
been found in the graph specified by the previous graph line. In particular,
flag=1 if there is a negative cycle, and flag=0 otherwise. 

Checksum
lines 
The line (which should appear only if there are no negative
cycles) specifies the sum (checksum) modulo 2^{62} of the
distances from source S to all other nodes reachable from it computed by
the solver in the graph specified by the previous graph line. The each sum
operation must be performed modulo 2^{62} using 64bit variables
so as to avoid overflow problems. The goal of this line is to help in checking
the correctness of the solver. The line corresponds to a singlesource computation
as specified in the input problem specification file. 

Pointtopoint shortest path
problem

The goal of the pointtopoint (P2P) shortest path problem is to find a shortest
path between a specified pair of nodes in the input graph. The nonnegative
pointtopoint (NP2P) shortest paths problem is the same as the more general
P2P problem, with the understanding that all arc weights in the input graph
are nonnegative.
Problem specification files
(.p2p files)


The auxiliary file for this problem should have
the extension .p2p. Line types are as follows. In the format descriptions
below, bold characters should appear exactly as typed: 
Comment
lines 
These lines begin with a lowercase character c
and can appear anywhere. Comment lines are ignored by programs. 

Problem
line 
The problem line is unique and must appear as the first
noncomment line. This line has the format on the right, where n
is the number of query lines that follow. 

Query
lines 
Query lines are of the form on the right, where S,
T are the ids of the source and the destination nodes, respectively.
Each query line defines a new problem on the same graph. 

For the P2P problem, many algorithms have an initial preprocessing phase which
computes information about the input graph that can be later used to speed up
queries. For this reason, there are separate performance report files for preprocessing
and for queries.
Performance report files
for preprocessing (.p2p.p.res files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 
p res sp p2p p solvername 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename). 

Graph
details lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the average time T in milliseconds
required by the solver to preprocess the graph specified by the previous
graph line. 

Space
lines 
The line (optional) specifies the maximum space S
in kilobytes required by the data structures maintained by the solver to
preprocess the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Performance report files
for queries (.p2p.q.res files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 
p res sp p2p q solvername 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (p2pfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the average time T in milliseconds
required by the solver to answer each p2p query on the graph specified by
the previous graph line. 

Space
lines 
The line (optional) specifies the maximum space S
in kilobytes required by the data structures maintained by the solver to
answer each p2p query on the graph specified by the previous graph line. 

Node
scan lines 
The line (optional) specifies the average number count
of nodes scanned by the solver to answer each p2p query on the graph specified
by the previous graph line. 

Arc
scan lines 
The line (optional) specifies the average number count
of arcs scanned by the solver to answer each p2p query on the graph specified
by the previous graph line. 

Improvement
lines 
The line (optional) specifies the average number count
of distance improvements done by the solver to answer each p2p query on
the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Correctness checking files
(.p2p.chk files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the checking file refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (p2pfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Distance
lines 
The line specifies the distance from node X
to node Y computed by the solver in the graph specified by the previous
graph line. The goal of this line is to help in checking the correctness
of the solver. The line corresponds to a query operation in the input problem
specification file. 

Allpairs shortest path problem

The goal of the allpairs (AP) shortest paths problem is to find shortest paths
between each pair of nodes in the input graph. This problem is completely specified
by the graph files. No problem specification file is required. The nonnegative
allpairs (NAP) shortest paths problem is the same as the more general AP problem,
with the understanding that all arc weights in the input graph are nonnegative.
Performance report files (.ap.res
files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (p2pfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the time T in milliseconds required
by the solver to perform the allpairs computation on the graph specified
by the previous graph line. 

Space
lines 
The line (optional) specifies the space S in kilobytes
required by the data structures used by the solver to perform the allpairs
computation on the graph specified by the previous graph line. 

Node
scan lines 
The line (optional) specifies the number count of
nodes scanned by the solver to perform the allpairs computation on the
graph specified by the previous graph line. 

Arc
scan lines 
The line (optional) specifies the number count of
arcs scanned by the solver to perform the allpairs computation on the graph
specified by the previous graph line. 

Improvement
lines 
The line (optional) specifies the number count of
distance improvements done by the solver to perform the allpairs computation
on the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Correctness checking files
(.ap.chk files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the checking file refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Checksum
lines 
The line specifies the sum (checksum) modulo 2^{62}
of the distances between each pair of connected nodes computed by the solver
in the graph specified by the previous graph line. The each sum operation
must be performed modulo 2^{62} using 64bit variables so as to
avoid overflow problems. The goal of this line is to help in checking the
correctness of the solver. 

Negative cycle detection problem

The goal of the negative cycle detection (NCD) problem is to find a negative
cycle in the input graph, if one exists. This problem is completely specified
by the graph files. No problem specification file is required.
Performance report files (.ncd.res
files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the average time T in milliseconds
required by the solver to perform each singlesource computation on the
graph specified by the previous graph line. 

Space
lines 
The line (optional) specifies the maximum space S
in kilobytes required by the data structures maintained by the solver to
perform each singlesource computation on the graph specified by the previous
graph line. 

Node
scan lines 
The line (optional) specifies the average number count
of nodes scanned by the solver to perform each singlesource computation
on the graph specified by the previous graph line. 

Arc
scan lines 
The line (optional) specifies the average number count
of arcs scanned by the solver to perform each singlesource computation
on the graph specified by the previous graph line. 

Improvement
lines 
The line (optional) specifies the average number count
of distance improvements done by the solver to perform each singlesource
computation on the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Correctness checking files
(.ncd.chk files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the checking file refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Negative
cycle lines 
The line specifies whether a negative cycle has been found
in the graph specified by the previous graph line. In particular, flag=1
if there is a negative cycle, and flag=0 otherwise. 

Dynamic singlesource shortest
path problem

Given a fixed source node s, the goal of the dynamic singlesource (DSS) shortest
path problem is to maintain a data structure for a graph that supports any intermixed
sequence of the following operations:
insert(x,y,w) 
inserts arc (x,y) with weight w into the graph 
delete(x,y) 
deletes arc (x,y) from the graph 
update(x,y,w) 
changes the weight of arc (x,y) to the new value w 
query(v) 
reports the distance from the source s to node v 
The dynamic nonnegative singlesource (DNSS) shortest paths problem is the
same as the more general DSS problem, with the understanding that all arc weights
are nonnegative.
Problem specification files
(.dss files)


The auxiliary file for the problem should have
the extension .dss. Line types are as follows. In the format descriptions
below, bold characters should appear exactly as typed: 
Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The problem line is unique and must appear as the first
noncomment line. This line has the format on the right, where S is the
source node and n is the number of operation lines that follow. 

Arc
insert
lines 
Each insert line specifies an operation that inserts a new
arc (X,Y) into the graph with weight W 

Arc
delete
lines 
Each delete line specifies an operation that deletes arc
(X,Y) from the graph 

Arc
update
lines 
Each update line specifies an operation that changes the
weight of arc (X,Y) to the new value W. The operation can be either an arc
weight increase or an arc weight decrease, depending on the previous value. 

Query
lines 
Each query line specifies a query operation that asks for
the distance of node V from source S 

Performance report files (.dss.res
files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (dssfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the average time T in milliseconds
required by the solver to perform each operation on the graph specified
by the previous graph line. 

Space
lines 
The line (optional) specifies the maximum space S
in kilobytes required by the data structures maintained by the solver to
perform each operation on the graph specified by the previous graph line. 

Node
scan lines 
The line (optional) specifies the average number count
of nodes scanned by the solver to perform each operation on the graph specified
by the previous graph line. 

Arc
scan lines 
The line (optional) specifies the average number count
of arcs scanned by the solver to perform each operation on the graph specified
by the previous graph line. 

Improvement
lines 
The line (optional) specifies the average number count
of distance improvements done by the solver to perform each operation on
the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Correctness checking files
(.dss.chk files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the checking file refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (dssfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Distance
lines 
The line specifies the distance from source S
to node V computed by the solver in the graph specified by the
previous graph line. The goal of this line is to help in checking the correctness
of the solver. The line corresponds to a query operation in the input problem
specification file. 

Dynamic allpairs shortest path
problem

The goal of the dynamic allpairs (DAP) shortest path problem is to maintain
a data structure for a graph that supports any intermixed sequence of the following
operations:
insert(x,y,w) 
inserts arc (x,y) with weight w into the graph 
delete(x,y) 
deletes arc (x,y) from the graph 
update(x,y,w) 
changes the weight of arc (x,y) to the new value w 
query(x,y) 
reports the distance from node x to node y 
The dynamic nonnegative allpairs (DNAP) shortest paths problem is the same
as the more general DAP problem, with the understanding that all arc weights
are nonnegative.
Problem specification files
(.dap files)


The auxiliary file for the problem should have
the extension .dap. Line types are as follows. In the format descriptions
below, bold characters should appear exactly as typed: 
Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The problem line is unique and must appear as the first
noncomment line. This line has the format on the right, where n is the
number of operation lines that follow. 

Arc
insert
lines 
Each insert line specifies an operation that inserts a new
arc (X,Y) into the graph with weight W 

Arc
delete
lines 
Each delete line specifies an operation that deletes arc
(X,Y) from the graph 

Arc
update
lines 
Each update line specifies an operation that changes the
weight of arc (X,Y) to the new value W. The operation can be either an arc
weight increase or an arc weight decrease, depending on the previous value. 

Query
lines 
Each query line specifies a query operation that asks for
the distance from node X to node Y 

Performance report files (.dap.res
files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the report refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (dapfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Time
lines 
The line specifies the average time T in milliseconds
required by the solver to perform each operation on the graph specified
by the previous graph line. 

Space
lines 
The line (optional) specifies the maximum space S
in kilobytes required by the data structures maintained by the solver to
perform each operation on the graph specified by the previous graph line. 

Node
scan lines 
The line (optional) specifies the average number count
of nodes scanned by the solver to perform each operation on the graph specified
by the previous graph line. 

Arc
scan lines 
The line (optional) specifies the average number count
of arcs scanned by the solver to perform each operation on the graph specified
by the previous graph line. 

Improvement
lines 
The line (optional) specifies the average number count
of distance improvements done by the solver to perform each operation on
the graph specified by the previous graph line. 

Userdefined
lines 
One may add more algorithmdependent lines, which should
start with u. 

Correctness checking files
(.dap.chk files)


Comment
lines 
Comment lines can appear anywhere and are ignored by programs. 

Problem
line 
The line, which must appear as the first noncomment line,
specifies the nature of the problem solved and the name (solvername)
of the solver the checking file refers to. 

Input
filename lines 
The line (optional) specifies the name of a graph file
(grfilename) and the name of a problem specification file (dapfilename). 

Graph
detail lines 
The line specifies the details of a graph: n, m,
min and max are the number of nodes, the number of arcs, the
minimum arc weight, and the maximum arc weight of the graph, respectively. 

Distance
lines 
The line specifies the distance from node X to
node Y computed by the solver in the graph specified by the previous
graph line. The goal of this line is to help in checking the correctness
of the solver. The line corresponds to a query operation in the input problem
specification file. 
