TORSCHE Scheduling
Toolbox for Matlab

TORSCHE – Graph Algorithms

Scheduling algorithms have very close relation to graph algorithms. Scheduling toolbox offer an object graph (see section Chapter 6, Graphs) with several graph algorithms.

1. List of Algorithms

List of algorithms related to operations with object graph are summarized in Table 9.1, “List of algorithms”.

algorithmcommandnote
Minimum spanning treespanningtreePolynomial
Dijkstra's algorithmdijkstraPolynomial
FloydfloydPolynomial
Minimum Cost FlowmincostflowUsing LP
Critical Circuit RatiocriticalcircuitratioUsing LP
Hamilton circuithamiltoncircuitNP-hard
Quadratic Assignment ProblemqapNP-hard

Table 9.1. List of algorithms

2. Minimum Spanning Tree

Spanning tree of the graph is a subgraph which is a tree and connects all the vertices together. A minimum spanning tree is then a spanning tree with minimal sum of the edges cost. A greedy algorithm with polynomial complexity is used to solve this problem (for more details see Demel02). The toolbox function has following syntax:

gmin = spanningtree(g)
gmin

minimum spanning tree represented by graph

g

input graph

>> A = [inf   1  2  inf  7;...
        inf inf  3   4  inf;...
        inf  9  inf  1   1;...
         8   5  inf inf inf;...
         7  inf  4   5  inf];
>> g = graph(A);
>> gmin = spanningtree(g);
>> graphedit(gmin);

Figure 9.1. Spanning tree example

Example of minimum spanning tree

Figure 9.2. Example of minimum spanning tree

3. Dijkstra's Algorithm

Dijkstra's algorithm is an algorithm that solves the single-source cost of shortest path for a directed graph with nonnegative edge weights. Inptut of this algorithm is a directed graph with costs of invidual edges and reference node r from which we want to find shortest path to other nodes. Output is an array with distances to other nodes.

distances = dijkstra(g,r)
g

graph object

r

reference node

>> A = [inf   1  2  inf  7;...
        inf inf  3   4  inf;...
        inf  9  inf  1   1;...
         8   5  inf inf inf;...
         7  inf  4   5  inf];
>> g = graph(A);
>> distances = dijkstra(g,2)

distances =

    11     0     3     4     4

Figure 9.3. Dijkstra's algorithm example

4. Floyd's Algorithm

Floyd is a well known algorithm from the graph theory [Diestel00]. This algorithm finds a matrix of shortest paths for a given graph. Input to the algorithm is an object graph, where the weights of edges are set in UserParam variables of edges. Output is a matrix of shortest paths (U) and optionally matrix of the vertex predecessors (P) in the shortest path and adjacency matrix of lengths (M). Algorithm can be run as follows:

[U,P,M] = floyd(g)

The variable g is an instance of graph object.

5. Strongly Connected Components

The Strongly Connected Components (SCC) of a directed graph are maximal subgraphs for which hold every couple of nodes u and v there is a path from u to v and a path from v to u. For SCC searching Tarjan algorithm is usullay used.

The algorithm is based on depth-first search where the nodes are placed on a stack in the order in which they are visited. When the search returns from a subtree, it is determined whether each node is the root of a SCC. If a node is the root of a SCC, then it and all of the nodes taken off before it form that SCC. The detailed describtion of the algorithm is in [DSVF06]. SCC in a graph G can be found as follows:

scc = tarjan(g)

where scc is a vector where the element scc(i) is number of component where the node i belongs to. For graph in Figure 9.5, “A simple network with optimal flow in the fourth user parameter on edges” the algorithm returns fllowing results.

>> tarjan(g)
ans =
     2     2     2     1

Figure 9.4. Strongly Connected Components example.

A simple network with optimal flow in the fourth user parameter on edges

Figure 9.5. A simple network with optimal flow in the fourth user parameter on edges

6. Minimum Cost Flows

The minimum cost flow model is the most fundamental of all network flow problems. In this problem we wish to determine a least cost shipment of a commodity through a network in order to satisfy demands at certain nodes from available supplies at other nodes [Ahuja93]. Let G=(N,A) be a directed network defined by set N of n nodes and a set A of m directed edges. Each edge (i,j)isinA has an associated cost cij that denotes the cost per unit flow on that arc. We also associate with each edge a capacity uij that denotes the maximum amount that can flow on the arc and a lower bound lij that denotes the minimum amount that must flow on the arc. We associate with each node iisinN an integer number b(i) representing its suply/demand. If b(i)>0, node i is a supply node; If b(i)<0, node i is a demand of -b(i); and if b(i)=0, node i is a transshipment node. The problem can be solved using function mincostflow:

gminf=mincostflow(g)

where g is a graph, where suply/demand b(i) is stored in the first user parameter (UserParam) of nodes. Parameters (cij, lij, uij) are given in the first, second and third user parameter (UserParam) of corresponding edge eij. The function returns graph G_minf where the optimal flow fij is stored in the fourth user parameter (UserParam) on edge eij. A simple example is shown in Figure 9.6, “Mincostflow example.” and Figure 9.7, “A simple network with optimal flow in the fourth user parameter on edges”.

>> gminf=mincostflow(g);
>> graphedit(gminf);

Figure 9.6. Mincostflow example.

A simple network with optimal flow in the fourth user parameter on edges

Figure 9.7. A simple network with optimal flow in the fourth user parameter on edges

Note

The algorithm use function 'ilinprog' from the TORSCHE. Solver GLPK must be installed. Installation of TORSCHE

7. The Critical Circuit Ratio

This problem is also called minimum cost-to-time ratio cycle problem [Ahuja93]. The algorithm assumes graph G where edges are weighted by a couple of constants length l and height h. The objective is to find the critical circuit ratio defined as

where C is a cycle of graph G. The circuit C with maximal circuit ratio is called critical circuit. Function

rho=criticalcircuitratio(G)

finds minimal circuit ratio in a graph G, where length l and height h are specified in the first and the second user parameters on edges (UserParam). Graph weighted by a couple l, h can be created from matrices L and H as shown in Example Critical circuit ratio where element L(i,j), H(i,j) contains length, height of edge e(i,j) respectively.

>> L=[inf 2 inf;2 inf 1; 1 inf inf]
L =
   Inf     2   Inf
     2   Inf     1
     1   Inf   Inf
>> H=[inf 0 inf;1 inf 0;2 inf inf]
H =
   Inf     0   Inf
     1   Inf     0
     2   Inf   Inf
>> G=graph((L~=inf)*1)
 
 adjacency matrix:
     0     1     0
     1     0     1
     1     0     0
>> G=matrixparam2edges(G,L,1);
>> G=matrixparam2edges(G,H,2);
>> rho=criticalcircuitratio(G)
rho =
    4.0000

Figure 9.8. Critical circuit ratio.

8. Hamilton Circuits

A Hamilton circuit in a graph G, is a graph cycle through G that visits each node exactly once. The general problem of finding a Hamilton circuit is NP-complete [Diestel00]. The solution in the toolbox is based on Integer Linear Programming.

gham=hamiltoncircuit(g,edgesdirection)
gham

hamilton circuit represented by a graph

g

input graph G

edgesdirection

specifies whether g is undirected ('u') or directed ('d') (directed graphs are default)

A simple example representing a traffic network in Czech Republic is shown in Example Hamilton Circuit Identification and Figure 9.10, “An example of Hamilton circuit.”.

>> load <Matlab root>\toolbox\scheduling\stdemos\...
   benchmarks\tsp\czech_rep
>> gham=hamiltoncircuit(g,'u');
>> graphedit(gham);

Figure 9.9. Hamilton circuit identification example.

An example of Hamilton circuit.

Figure 9.10. An example of Hamilton circuit.

Note

The algorithm use function 'ilinprog' from the Scheduling toolbox. Solver GLPK must be installed. Installation of TORSCHE.

9. Graph coloring

Graph coloring is assignment of values representing colors to nodes in a graph. Any two nodes, which are connected by an edge, cannot be assigned (colored) the same value. Graphcoloring algorithm is intended to colour graph by minimal number of colors. The least number of colors needed for coloring is called chromatic number of the graph χ. This algorithm, based on backtracking, was taken over from Demel02. Assigned values are of integer type saved as user parameter of each node and RGB color for nodes graphical representation.

G2 = graphcoloring(G1, userparamposition)
G1

input graph

G2

colored graph

userparamposition

specifies position (index) in userparam of node to save "color". This parameter is optional. Default index is 1.

>> A = [0 0 1 0 1 0;
        1 0 0 1 1 0;
        0 1 0 1 0 1;
        0 0 0 0 1 0;
        0 0 1 0 0 1;
        1 1 0 0 0 0];
>> g1 = graph('adj',A);
>> g2 = graphcoloring(g1);
>> graphedit(g2);

Example 9.1. Graph Coloring example

An example of Graph coloring

Figure 9.11. An example of Graph coloring

10. The Quadratic Assignment Problem

This algorithm solves the Quadratic Assignment Problem (QAP) Stützle99. The problem can be stated as follows. Consider a set of n activities that have to be assigned to n locations (or vice versa). A matrix D= [dih]n,n gives distances between locations, where dih is distance between location i and location h, and a matrix F = [fjk]n,n characterizes flows among activities (transfer of data, material, etc.), where fjk is the flow between activity j and activity k. An assignment is a permutation π of {1,...,n}, where π(i) is the activity that is assigned to location i. The problem is to find a permutation πm such that the product of the flows among activities is minimized by the distances between their locations. Formally, the QAP can be formulated as the problem of finding the permutation π which minimizes the following objective function:

The optimal permutation πopt is defined by where Π(n) is the set of all permutations of {1,...,n}.

The problem can be reformulated to show the quadratic nature of the objective function: solving the problem means identifying a permutation matrix X of dimension n × n (whose elements xij are 1 if the activity j is assigned to location i and 0 in the other cases) such that:

subject to the constraints and . In the toolbox the problem can be solved using Mixed Integer Quadratic Programming (MIQP).

[xmin,fmin,status,extra]=qap(distancesgraph,flowsgraph)

The function returns a nonempty output if a solution is found. Matrix xmin is optimal value of decision variables, fmin is equal to 0.5 times optimal value of the objective function, status is a status of the optimization (1-solution is optimal) and extra is a data structure containing field time - time (in seconds) used for solving. Parameters distancesgraph and flowsgraph are graphs, where distances and flows are specified in first user parameter on edges (UserParam). Graphs can be created form matrices D and F as shown in Quadratic Assignment Problem example in Quadratic Assignment Problem. Some benchmark instances QAPLIB06 are located in \scheduling\stdemos\benchmarks\qap\ directory.

>> D = [0 1 1 2 3;1 0 2 1 2;1 2 0 1 2;2 1 1 0 1;3 2 2 1 0]
D =
     0     1     1     2     3
     1     0     2     1     2
     1     2     0     1     2
     2     1     1     0     1
     3     2     2     1     0

>> F = [0 5 2 4 1;5 0 3 0 2;2 3 0 0 0;4 0 0 0 5;1 2 0 5 0]
F =
     0     5     2     4     1
     5     0     3     0     2
     2     3     0     0     0
     4     0     0     0     5
     1     2     0     5     0

%Create graph of distances
>> distancesgraph=graph('adj', 1*(D~=0));

%Insert distances into the graph
>> distancesgraph=matrixparam2edges(distancesgraph,D,1,0);

%Create graph of flow
>> flowsgraph=graph('adj', 1*(F~=0));

%Insert flows into the graph
>> flowsgraph=matrixparam2edges(flowsgraph,F,1,0);

>> [xmin,fmin,status,extra]=qap(distancesgraph,flowsgraph)
xmin =
     0     1     0     0     0
     0     0     0     1     0
     0     0     0     0     1
     1     0     0     0     0
     0     0     1     0     0
fmin =
    25
status =
     1
extra = 
    time: 1.2660

Figure 9.12. Quadratic Assignment Problem.

Note

The algorithm use function iquadprog from the toolbox.

Note

Smaller benchmark instance (not presented in QAPLIB06) can be found e.g. on http://ina2.eivd.ch/collaborateurs/etd/problemes.dir/qap.dir/qap.html.

Webmaster - Jan Dvořák (2004 - 2019)