Download Visualising the `Shifting Bottleneck` Scheduling Algorithm

5.1.3
Internal Graph Representation
The internal graph representation is held in a class named GraphHandler which contains the graph
data structure itself as one of its attributes, and implements methods for adding and removing edges, and
additionally methods to call the longest path and layout algorithms. The disjunctive graph data structure
is built upon the BGL’s adjacency list data type as follows:
typedef adjacency_list <
listS,
// Store out-edges in a std::list
vecS,
// Store vertices in a std::vector
directedS,
// The graph is directed
property<operation, std::string>, // name of a node
property < edge_weight_t, int >
// weight of each edge
> DisjunctiveGraph;{
There are additonal type defintions to set up the vertex and edge descriptors, and the PositionMap
used by the layout algorithm. An adjacency list represents a graph by way of a list of edges for each
vertex. As the disjunctive graph model is directional, the lists can be further limited to just edges leaving
vertices, as this will cover all edges in the graph.
5.1.4
Longest Path Algorithm
As was detailed in section 4.1.2, the Directed Acyclic Graph shortest-path algorithm provided by the
BGL is trivially converted to a longest path algorithm by negating all edge weights. The algorithm is
accessed via two methods of the GraphHandler class. The first of which is:
bool GraphHandler::doLongestPath(int source) {
vertex_descriptor s = vertex(source, disGraph);
dag_shortest_paths(disGraph, s, predecessor_map(&parents[0])
.distance_map(&distances[0]));
return true;
}
This initialises a vertex as the source of the longest (shortest) path algorithm, and then passes the graph
representation object disGraph and the source to the algorithm. The other function parameter is the
29