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)		View sample.gr
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)		View sample.co
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)		View sample.ss
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)		View sample.ss.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 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)		View sample.ss.chk
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)		View sample.p2p
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)		View sample.p2p.p.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 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)		View sample.p2p.q.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 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)		View sample.p2p.chk
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.

Correctness checking files (.ap.chk files)		View sample.ap.chk
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.

Correctness checking files (.ncd.chk files)		View sample.ncd.chk
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)		View sample.dss
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)		View sample.dss.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 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)		View sample.dss.chk
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)		View sample.dap
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)		View sample.dap.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 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)		View sample.dap.chk
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

Goals | Papers | Competition | Photos | Organizers | File formats | Download | Workshop | Mailing list | Links