The makefile separates by experiment. To run the experiments, run the following commands, respectively
$ make chaotic
$ make delta
$ make dijkstra
$ make deltaOptimal
- CSR.cpp/h
- Compressed Sparse Row class
- Parser.cpp/h
- Parsing input class, returns an instance of CSR
- SSSP.cpp/h
- Contains delta step algorithm
- Worklist.cpp/h
- Worklist class, abstracts a map of 'buckets'
- *Experiment.cpp
- Different runners for the various experiments
- Sets x,y in the adjaceny matrix to val
- x is from edge, y is to edge
- Returns the weight for edge x->y
- Returns a vector of vectors
- Each vector will have the format <u, v, weight>
- print all the labels for each of given nodes
- returns the tentative cost of node u
- set the tentative cost of node u to cost val
- print out the inner workings of the CSR
- IA, JA, and the values
- returns true if all the nodes out of
node
have been relaxed
- sets the edge as relaxed
- returns true if there are still items in a bucket
- returns the index of the first non-empty bucket
- returns the bucket stored at i
- puts a set of nodes at bucket i
- relaxes the set of nodes in
req
, shuffles with seedseed
- prints the number of edge and node relaxations
- returns the light edges
- sets the light edges to set
s
- returns the heavy edges
- sets the heavy edges to
s
- returns a set to be relaxed, the nodes in both
bucket
ands
- Constructor
- takes in a CSR graph, step size, and a seed for shuffling
- Runs the delta step algorithm
- If
printNLabels
is true, the node labels are printed - If
printRelaxCount
is true, the number of relaxations are printed
- returns a created CSR from the input file
- Measures clock time and node relaxations across different seeds
- Seeds: 10, 20, 50
- Measures node relaxations across different step sizes
- Prints out node labels and number of steps
- Runs dijkstra by setting delta to 1
- prints out node labels and node relaxations
- runs the optimal delta across all the different graphs
- prints node relaxations and clock time
The graph is represented by a NxN
matrix, where the rows represent from
vertices and the columns represent the to
vertices.
Therefore, if A[u][v] = w
, there is edge from u
to v
with edge weight w
.
With this definition, calculating the highest outdegree is equivalent to finding the row with the most non-zero entries.
The number of non-zero entries can be computed with the IA
vector of Compressed Sparse Row.
The IA
vector has the following definition:
- IA[0] = 0
- IA[i] = IA[i - 1] + number of non-zero entries for row i - 1
for(int i = 0; i < numRows){
int currDegree = IA[i + 1] - IA[i];
if(currDegree > oldDegree){
row = i;
oldDegree = currDegree;
}
}
return row;