Coffman–Graham algorithm
Encyclopedia
In job shop scheduling
and graph drawing
, the Coffman–Graham algorithm is an algorithm
, named after Edward G. Coffman, Jr. and Ronald Graham
, for arranging the elements of a partially ordered set
into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound . When , it uses the minimum possible number of distinct levels, and in general it uses at most times as many levels as necessary.
In the layered graph drawing
framework outlined by and implemented in systems such as Microsoft Automatic Graph Layout
, the input is a directed graph
, and a drawing of a graph is constructed in several stages:
In this framework, the -coordinate assignment again involves grouping elements of a partially ordered set (the vertices of the graph, with the reachability
ordering on the vertex set) into layers (sets of vertices with the same -coordinate), which is the problem solved by the Coffman–Graham algorithm. Although there exist alternative approaches than the Coffman–Graham algorithm to the layering step, these alternatives in general are either not able to incorporate a bound on the maximum width of a level or rely on complex integer programming
procedures.
More abstractly, both of these problems can be formalized as a problem in which the input consists of a partially ordered set and an integer . The desired output is an assignment of integer level numbers to the elements of the partially ordered set such that, if is an ordered pair of related elements of the partial order, the number assigned to is smaller than the number assigned to , such that at most elements are assigned the same number as each other, and minimizing the difference between the smallest and the largest assigned numbers.
, or belongs to several related classes of partial orders, the Coffman–Graham algorithm finds a solution with the minimum number of levels regardless of its width bound.
As well as finding schedules with small makespan, the Coffman–Graham algorithm (modified from the presentation here so that it topologically orders the reverse graph of and places the vertices as early as possible rather than as late as possible) minimizes the total flow time of two-processor schedules, the sum of the completion times of the individual jobs. A related algorithm can be used to minimize the total flow time for a version of the problem in which preemption of jobs is allowed.
and state the time complexity of the Coffman–Graham algorithm, on an -element partial order, to be . However, this analysis omits the time for constructing the transitive reduction, which is not known to be possible within this bound. shows how to implement the topological ordering stage of the algorithm in linear time, based on the idea of partition refinement
. Sethi also shows how to implement the level assignment stage of the algorithm efficiently by using a disjoint-set data structure
. In particular, with a version of this structure published later by , this stage also takes linear time.
Job Shop Scheduling
Job shop scheduling is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:...
and graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
, the Coffman–Graham algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, named after Edward G. Coffman, Jr. and Ronald Graham
Ronald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
, for arranging the elements of a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound . When , it uses the minimum possible number of distinct levels, and in general it uses at most times as many levels as necessary.
Problem statement and applications
In the version of the job shop scheduling problem solved by the Coffman–Graham algorithm, one is given a set of jobs , together with a system of precedence constraints requiring that job be completed before job begins. Each job is assumed to take unit time to complete. The scheduling task is to assign each of these jobs to time slots on a system of identical processors, minimizing the makespan of the assignment (the time from the beginning of the first job until the completion of the final job). Abstractly, the precedence constraints define a partial order on the jobs, so the problem can be rephrased as one of assigning the elements of this partial order to levels (time slots) in such a way that each time slot has at most as many jobs as processors (at most elements per level), respecting the precendence constraints. This application was the original motivation for Coffman and Graham to develop their algorithm.In the layered graph drawing
Layered graph drawing
Layered graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards...
framework outlined by and implemented in systems such as Microsoft Automatic Graph Layout
Microsoft Automatic Graph Layout
Microsoft Automatic Graph Layout is a .NET library for automatic graph layout.It was created by Lev Nachmanson at Microsoft Research.Earlier versions carried the name GLEE .- Contents :...
, the input is a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
, and a drawing of a graph is constructed in several stages:
- A feedback arc setFeedback arc setIn graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph . One way to do this is simply to drop edges from the graph to break the cycles...
is chosen, and the edges of this set reversed, in order to convert the input into a directed acyclic graphDirected acyclic graphIn mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
. - The vertices of the graph are given integer -coordinates in such a way that, for each edge, the starting vertex of the edge has a higher coordinate than the ending vertex, with at most vertices sharing the same -coordinate.
- Dummy vertices are introduced within each edge so that the subdivided edges all connect pairs of vertices that are in adjacent levels of the drawing.
- Within each group of vertices with the same -coordinate, the vertices are permutedPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
in order to minimize the number of crossingsCrossing number (graph theory)In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
in the resulting drawing, and the vertices are assigned -coordinates consistently with this permutation. - The vertices and edges of the graph are drawn with the coordinates assigned to them.
In this framework, the -coordinate assignment again involves grouping elements of a partially ordered set (the vertices of the graph, with the reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
ordering on the vertex set) into layers (sets of vertices with the same -coordinate), which is the problem solved by the Coffman–Graham algorithm. Although there exist alternative approaches than the Coffman–Graham algorithm to the layering step, these alternatives in general are either not able to incorporate a bound on the maximum width of a level or rely on complex integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
procedures.
More abstractly, both of these problems can be formalized as a problem in which the input consists of a partially ordered set and an integer . The desired output is an assignment of integer level numbers to the elements of the partially ordered set such that, if is an ordered pair of related elements of the partial order, the number assigned to is smaller than the number assigned to , such that at most elements are assigned the same number as each other, and minimizing the difference between the smallest and the largest assigned numbers.
The algorithm
The Coffman–Graham algorithm performs the following steps.- Represent the partial order by its transitive reductionTransitive reductionIn mathematics, a transitive reduction of a binary relation R on a set X is a minimal relation R' on X such that the transitive closure of R' is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then R' is unique...
or covering relationCovering relationIn mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours...
, a directed acyclic graph that has an edge from x to y whenever and there does not exist any third element of the partial order for which . In the graph drawing applications of the Coffman–Graham algorithm, the resulting directed acyclic graph may not be the same as the graph being drawn, and in the scheduling applications it may not have an edge for every precedence constraint of the input: in both cases, the transitive reduction removes redundant edges that are not necessary for defining the partial order. - Construct a topological orderingTopological sortingIn computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...
of in which the vertices are ordered lexicographically by the set of positions of their incoming neighbors. To do so, add the vertices one at a time to the ordering, at each step choosing a vertex to add such that the incoming neighbors of are all already part of the partial ordering, and such that the most recently added incoming neighbor of is earlier than the most recently added incoming neighbor of any other vertex that could be added in place of . If two vertices have the same most recently added incoming neighbor, the algorithm breaks the tie in favor of the one whose second most recently added incoming neighbor is earlier, etc. - Assign the vertices of to levels in the reverse of the topological ordering constructed in the previous step. For each vertex , add to a level that is at least one step higher than the highest level of any outgoing neighbor of , that does not already have elements assigned to it, and that is as low as possible subject to these two constraints.
Analysis
As originally proved, their algorithm computes an optimal assignment for ; that is, for scheduling problems with unit length jobs on two processors, or for layered graph drawing problems with at most two vertices per layer. A closely related algorithm also finds the optimal solution for scheduling of jobs with varying lengths, allowing pre-emption of scheduled jobs, on two processors. For , the Coffman–Graham algorithm uses a number of levels (or computes a schedule with a makespan) that is within a factor of of optimal. For instance, for , this means that it uses at most times as many levels as is optimal. When the partial order of precedence constraints is an interval orderInterval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...
, or belongs to several related classes of partial orders, the Coffman–Graham algorithm finds a solution with the minimum number of levels regardless of its width bound.
As well as finding schedules with small makespan, the Coffman–Graham algorithm (modified from the presentation here so that it topologically orders the reverse graph of and places the vertices as early as possible rather than as late as possible) minimizes the total flow time of two-processor schedules, the sum of the completion times of the individual jobs. A related algorithm can be used to minimize the total flow time for a version of the problem in which preemption of jobs is allowed.
and state the time complexity of the Coffman–Graham algorithm, on an -element partial order, to be . However, this analysis omits the time for constructing the transitive reduction, which is not known to be possible within this bound. shows how to implement the topological ordering stage of the algorithm in linear time, based on the idea of partition refinement
Partition refinement
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also...
. Sethi also shows how to implement the level assignment stage of the algorithm efficiently by using a disjoint-set data structure
Disjoint-set data structure
In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
. In particular, with a version of this structure published later by , this stage also takes linear time.