Goals
Papers
Competition
Photos
Organizers
File formats
Download
Workshop
Mailing list
Links
9th DIMACS Implementation Challenge - Shortest Paths

Challenge file formats

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:

General conventions

Files consist of ASCII characters (plain text files)
The file content consists of several types of lines
Each line begins with a one-character line type designator
Line fields are separated by at least one blank space
Each line ends with a newline separator
Numerical values stored in the file (e.g., arc weights, node ids, etc.) may be strings of digits of any length. Programs should make sure to load them into large enough memory words (e.g., 32 or 64 bits depending on the context).

The following table summarizes all standard file formats defined for the Challenge:

File formats summary

Input files

Output files

Graph specification files

Problem specification files

Performance report files

Correctness checking files

.gr files (nodes, arcs, arc weights)
.ss files (single-source) .ss.res files (single-source) .ss.chk files (single-source)
.co files (node coordinates) .p2p files (point-to-point)

.p2p.p.res files (point-to-point prepr.)
.p2p.q.res files (point-to-point query)

.p2p.chk files (point-to-point)
  .dss files (dynamic single-source) .dss.res files (dynamic single-source) .dss.chk files (dynamic single-source)
.dap files (dynamic all-pairs) .dap.res files (dynamic all-pairs) .dap.chk files (dynamic all-pairs)
  .ap.res files (all-pairs) .ap.chk files (all-pairs)
.ncd.res files (neg. cycle detection) .ncd.chk files (neg. cycle detection)

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.

Problems addressed

Single-source shortest paths Dynamic single-source shortest paths
All-pairs shortest paths Dynamic all-pairs shortest paths
Point-to-point shortest paths Negative cycle detection


Graph specification formats

Graph (.gr files)

A graph contains n nodes and m arcs
Nodes are identified by integers 1...n
Graphs can be interpreted as directed or undirected, depending on the problem being studied
Graphs can have parallel arcs and self-loops
Arc weights are signed integers
By convention, shortest path graph file names should have the suffix .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.
c This is a comment
Problem
line
The problem line is unique and must appear as the first non-comment line. This line has the format on the right, where n and m are the number of nodes and the number of arcs, respectively.
p sp n m
Arc
descriptor lines
Arc descriptors are of the form on the right, where U and V are the tail and the head node ids, respectively, and W is the arc weight.
a U V W

Node coordinates (.co files)

X-Y 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.
c This is a comment
Problem
line
The problem line is unique and must appear as the first non-comment line. This line has the format on the right, where n is the number of coordinate lines that follow.
p aux sp co n
Coord
lines
Coordinate lines are of the form on the right, where id , X and Y are the id of the node, its X-coordinate, and its Y-coordinate, respectively.
v id X Y


Single-source shortest path problem

The goal of the single-source (SS) shortest paths problem is to find shortest paths between a specified source node and all other nodes in the input graph. The non-negative single-source (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 non-negative.

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.
c This is a comment
Problem
line
The problem line is unique and must appear as the first non-comment line. This line has the format on the right, where n is the number of source lines that follow.
p aux sp ss n
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.
s S

Performance report files (.ss.res files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the report refers to.
p res sp ss solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (ssfilename).
f grfilename 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.
g n m min max
Time lines The line specifies the average time T in milliseconds required by the solver to perform each single-source computation on the graph specified by the previous graph line.
t T
Space lines The line (optional) specifies the maximum space S in kilobytes required by the data structures maintained by the solver to perform each single-source computation on the graph specified by the previous graph line.
s S
Node scan lines The line (optional) specifies the average number count of nodes scanned by the solver to perform each single-source computation on the graph specified by the previous graph line.
v count
Arc scan lines The line (optional) specifies the average number count of arcs scanned by the solver to perform each single-source computation on the graph specified by the previous graph line.
e count
Improvement lines The line (optional) specifies the average number count of distance improvements done by the solver to perform each single-source computation on the graph specified by the previous graph line.
i count
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

Correctness checking files (.ss.chk files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the checking file refers to.
p chk sp ss solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (ssfilename).
f grfilename 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.
g n m min max
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.
D flag
Checksum lines The line (which should appear only if there are no negative cycles) specifies the sum (checksum) modulo 262 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 262 using 64-bit 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 single-source computation as specified in the input problem specification file.
d S checksum


Point-to-point shortest path problem

The goal of the point-to-point (P2P) shortest path problem is to find a shortest path between a specified pair of nodes in the input graph. The non-negative point-to-point (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 non-negative.

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 lower-case character c and can appear anywhere. Comment lines are ignored by programs.
c This is a comment
Problem
line
The problem line is unique and must appear as the first non-comment line. This line has the format on the right, where n is the number of query lines that follow.
p aux sp p2p n
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.
q S T

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.
c This is a comment
Problem line The line, which must appear as the first non-comment 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).
f 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.
g n m min max
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.
t T
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.
s S
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

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

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment 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).
f grfilename 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.
g n m min max
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.
t T
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.
s S
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.
v count
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.
e count
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.
i count
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

Correctness checking files (.p2p.chk files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the checking file refers to.
p chk sp p2p solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (p2pfilename).
f grfilename 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.
g n m min max
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.
d X Y distance


All-pairs shortest path problem

The goal of the all-pairs (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 non-negative all-pairs (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 non-negative.

Performance report files (.ap.res files)

View sample.ap.res
Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the report refers to.
p res sp ap solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (p2pfilename).
f grfilename apfilename
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.
g n m min max
Time lines The line specifies the time T in milliseconds required by the solver to perform the all-pairs computation on the graph specified by the previous graph line.
t T
Space lines The line (optional) specifies the space S in kilobytes required by the data structures used by the solver to perform the all-pairs computation on the graph specified by the previous graph line.
s S
Node scan lines The line (optional) specifies the number count of nodes scanned by the solver to perform the all-pairs computation on the graph specified by the previous graph line.
v count
Arc scan lines The line (optional) specifies the number count of arcs scanned by the solver to perform the all-pairs computation on the graph specified by the previous graph line.
e count
Improvement lines The line (optional) specifies the number count of distance improvements done by the solver to perform the all-pairs computation on the graph specified by the previous graph line.
i count
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

Correctness checking files (.ap.chk files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the checking file refers to.
p chk sp ap solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename).
f 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.
g n m min max
Checksum lines The line specifies the sum (checksum) modulo 262 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 262 using 64-bit variables so as to avoid overflow problems. The goal of this line is to help in checking the correctness of the solver.
d checksum


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)

View sample.ncd.res
Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the report refers to.
p res sp ncd solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename)
f 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.
g n m min max
Time lines The line specifies the average time T in milliseconds required by the solver to perform each single-source computation on the graph specified by the previous graph line.
t T
Space lines The line (optional) specifies the maximum space S in kilobytes required by the data structures maintained by the solver to perform each single-source computation on the graph specified by the previous graph line.
s S
Node scan lines The line (optional) specifies the average number count of nodes scanned by the solver to perform each single-source computation on the graph specified by the previous graph line.
v count
Arc scan lines The line (optional) specifies the average number count of arcs scanned by the solver to perform each single-source computation on the graph specified by the previous graph line.
e count
Improvement lines The line (optional) specifies the average number count of distance improvements done by the solver to perform each single-source computation on the graph specified by the previous graph line.
i count
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

Correctness checking files (.ncd.chk files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the checking file refers to.
p chk sp ncd solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename).
f 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.
g n m min max
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.
D flag


Dynamic single-source shortest path problem

Given a fixed source node s, the goal of the dynamic single-source (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 non-negative single-source (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.
c This is a comment
Problem
line
The problem line is unique and must appear as the first non-comment 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.
p aux sp dss S n
Arc insert
lines
Each insert line specifies an operation that inserts a new arc (X,Y) into the graph with weight W
i X Y W
Arc delete
lines
Each delete line specifies an operation that deletes arc (X,Y) from the graph
d X Y
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.
u X Y W
Query
lines
Each query line specifies a query operation that asks for the distance of node V from source S
q V

Performance report files (.dss.res files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the report refers to.
p res sp dss solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (dssfilename).
f grfilename 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.
g n m min max
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.
t T
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.
s S
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.
v count
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.
e count
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.
i count
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

Correctness checking files (.dss.chk files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the checking file refers to.
p chk sp dss solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (dssfilename).
f grfilename 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.
g n m min max
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.
d S V distance


Dynamic all-pairs shortest path problem

The goal of the dynamic all-pairs (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 non-negative all-pairs (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.
c This is a comment
Problem
line
The problem line is unique and must appear as the first non-comment line. This line has the format on the right, where n is the number of operation lines that follow.
p aux sp dap n
Arc insert
lines
Each insert line specifies an operation that inserts a new arc (X,Y) into the graph with weight W
i X Y W
Arc delete
lines
Each delete line specifies an operation that deletes arc (X,Y) from the graph
d X Y
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.
u X Y W
Query
lines
Each query line specifies a query operation that asks for the distance from node X to node Y
q X Y

Performance report files (.dap.res files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the report refers to.
p res sp dap solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (dapfilename).
f grfilename 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.
g n m min max
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.
t T
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.
s S
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.
v count
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.
e count
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.
i count
User-defined lines One may add more algorithm-dependent lines, which should start with u.
u user-defined-info

Correctness checking files (.dap.chk files)

Comment
lines
Comment lines can appear anywhere and are ignored by programs.
c This is a comment
Problem line The line, which must appear as the first non-comment line, specifies the nature of the problem solved and the name (solvername) of the solver the checking file refers to.
p chk sp dap solvername
Input filename lines The line (optional) specifies the name of a graph file (grfilename) and the name of a problem specification file (dapfilename).
f grfilename 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.
g n m min max
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.
d X Y distance


Page maintained by Camil Demetrescu - last revised on Oct 21, 2006