DS Topological Sorting

Section 7.17 Topological Sorting

To demonstrate that computer scientists can turn just about anything into a graph problem, let’s consider the difficult problem of stirring up a batch of pancakes. The recipe is really quite simple: 1 egg, 1 cup of pancake mix, 1 tablespoon oil, and \(3 \over 4\) cup of milk. To make pancakes you must heat the griddle, mix all the ingredients together, and spoon the mix onto a hot griddle. When the pancakes start to bubble you turn them over and let them cook until they are golden brown on the bottom. Before you eat your pancakes you are going to want to heat up some syrup. Figure 7.17.1 illustrates this process as a dependency graph.

Figure 7.17.1. The Steps for Making Pancakes

The difficult thing about making pancakes is knowing what to do first. As you can see from Figure 7.17.1 you might start by heating the griddle or by adding any of the ingredients to the pancake mix. To help us decide the precise order in which we should do each of the steps required to make our pancakes, we turn to a graph algorithm called the topological sort.

A topological sort takes a directed acyclic graph and produces a linear ordering of all its vertices such that if the graph \(G\) contains an edge \((v, w)\) then the vertex \(v\) comes before the vertex \(w\) in the ordering. Directed acyclic graphs are used in many applications to indicate the precedence of events. Making pancakes is just one example; other examples include software project schedules, precedence charts for optimizing database queries, and multiplying matrices.

The topological sort is a simple but useful adaptation of a depth-first search. The algorithm for the topological sort is as follows:

Call dfs(g) for some graph g. The main reason we want to call depth-first search is to compute the closing times for each of the vertices.
Store the vertices in a list in decreasing order of the closing time.
Return the ordered list as the result of the topological sort.

Figure 7.17.2 shows the depth-first forest constructed by dfs on the pancake-making graph shown in Figure 7.17.1.

Figure 7.17.2. Result of Depth-First Search on the Pancake Graph

Finally, Figure 7.17.3 shows the results of applying the topological sort algorithm to our graph. Now all the ambiguity has been removed and we know exactly the order in which to perform the pancake-making steps.

Figure 7.17.3. Result of Topological Sort on Directed Acyclic Graph

Listing 7.17.4 gives the corresponding code for this example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;
import java.util.NoSuchElementException;

class Graph<T extends Comparable<T>> {
    
    HashMap<T, Vertex<T>> vertices;
    
    public Graph() {
        this.vertices = new HashMap<T, Vertex<T>>();
    }

public void setVertex(T key) {
        Vertex<T> v = new Vertex<T>(key);
        vertices.put(key, v);
    }
    
    public Vertex<T> getVertex(T key) {
        return vertices.get(key);
    }

public boolean containsVertex(T key) {
        return vertices.containsKey(key);
    }
    
    public void addEdge(T fromVertex, T toVertex) {
        addEdge(fromVertex, toVertex, 0);
    }
    
    public void addEdge(T fromVertex, T toVertex,
        Integer weight) {
        if (!vertices.containsKey(fromVertex)) {
            setVertex(fromVertex);
        }
        if (!vertices.containsKey(toVertex)) {
            setVertex(toVertex);
        }
        Vertex<T> from = vertices.get(fromVertex);
        Vertex<T> to = vertices.get(toVertex);
        from.setNeighbor(to, weight);
    }
    
    public HashMap<T, Vertex<T>> getVertices() {
        return this.vertices;
    }
    
    public ArrayList<Vertex<T>> getVertexList() {
        ArrayList<Vertex<T>> result = new ArrayList<>();
        for (T key: vertices.keySet()) {
            result.add(vertices.get(key));
        }
        return result;
    }
    
    public Set<T> getVertexKeys() {
        return this.vertices.keySet();
    }
    
    public void bfs(Vertex<T> start) {
        start.color = VertexColor.GRAY;
        start.distance = 0;
        start.previous = null;
        
        Queue<Vertex<T>> vertexQueue = new Queue<>();
        vertexQueue.enqueue(start);
        while (vertexQueue.size() > 0) {
            Vertex<T> current = vertexQueue.dequeue();
            for (Vertex<T> neighbor: current.getNeighbors()) {
                if (neighbor.color == VertexColor.WHITE) {
                    neighbor.color = VertexColor.GRAY;
                    neighbor.distance = current.distance + 1;
                    neighbor.previous = current;
                    vertexQueue.enqueue(neighbor);
                }
            }
                    
            current.color = VertexColor.BLACK;
        }
    }
}

class Vertex<T extends Comparable<T>>
    implements Comparable<Vertex<T>> {
    
    T key;
    HashMap<Vertex<T>, Integer> neighbors;
    
    int distance;
    Vertex<T> previous;
    VertexColor color;
    
    int discoveryTime;
    int closingTime;
    
    public Vertex(T key) {
        this.key = key;
        this.neighbors = new HashMap<Vertex<T>, Integer>();
        this.distance = 0;
        this.previous = null;
        this.color = VertexColor.WHITE;
        this.discoveryTime = 0;
        this.closingTime = 0;
    }

/*
     * Get the weight of the edge from this vertex
     * to the other vertex. Returns null if there is no
     * connection to the other vertex.
     */
    Integer getNeighbor(Vertex<T> other) {
        return neighbors.get(other);
    }
    
    /*
     * Set a connection from this vertex to the other
     * vertex with a weight of zero
     */
    void setNeighbor(Vertex<T> other) {
        setNeighbor(other, 0);
    }
    
    /*
     * Set a connection from this vertex to the other
     * vertex with the given weight
     */
    void setNeighbor(Vertex<T> other, Integer weight) {
        neighbors.put(other, weight);
    }
    
    /*
     * Return a Set of the neighbor vertices.
     */
    Set<Vertex<T>> getNeighbors() {
        return neighbors.keySet();
    }

/*
     * Return the key for this vertex.
     */
    T getKey() {
        return key;
    }
    
    public Vertex<T> getPrevious() {
        return this.previous;
    }
    
    public void setPrevious(Vertex<T> v) {
        this.previous = v;
    }
    
    
    public VertexColor getColor() {
        return this.color;
    }
    
    public void setColor(VertexColor color) {
        this.color = color;
    }
    
    public String toString() {
        String result = this.key.toString();
        if (neighbors.size() > 0) {
            result = result + " connected to: ";
            for (Vertex<T> vertex: this.getNeighbors()) {
                result = result + vertex.key + ", ";
            }
            result = result.substring(0, result.length() - 2);
        } else {
            result = result + " has no connections";
        }
        return result;
    }
    
    public int compareTo(Vertex<T> other) {
        return this.key.compareTo(other.key);
    }

static class ByDiscoveryTime implements Comparator<Vertex> {
        public int compare(Vertex a, Vertex b) {
            return a.discoveryTime - b.discoveryTime;
        }
    }

static class ByClosingTime implements Comparator<Vertex> {
        public int compare(Vertex a, Vertex b) {
            return a.closingTime - b.closingTime;
        }
    }
}

class Queue<T> {

ArrayList<T> items;

public Queue() {
        this.items = new ArrayList<T>();
    }

public boolean isEmpty() {
        return (this.items.isEmpty());
    }

public void enqueue(T item) {
        this.items.add(0, item);
    }

public T dequeue() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return this.items.remove(this.size() - 1);
    }

public T peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return this.items.get(this.size() - 1);
    }

public int size() {
        return this.items.size();
    }

public String toString() {

if (!this.items.isEmpty()) {
            String arrString = this.items.toString();
            return "tail ->" + arrString + "-> head";
        } else {
            return "<<empty queue>>";
        }
    }
}

enum VertexColor {
    WHITE, GRAY, BLACK
}

class DFSGraph<T extends Comparable<T>> extends Graph<T> {

int time;
    
    public DFSGraph() {
        super();
    }

public void dfs() {
        time = 0;
        Vertex<T> vertex;
        
        for (T key: getVertexKeys()) {
            vertex = vertices.get(key);
            vertex.setColor(VertexColor.WHITE);
            vertex.setPrevious(null);
        }
        
        for (T key: getVertexKeys()) {
            vertex = vertices.get(key);
            if (vertex.color == VertexColor.WHITE) {
                dfsVisit(vertex);
            }
        }
    }

void dfsVisit(Vertex<T> startVertex) {
        startVertex.setColor(VertexColor.GRAY);
        time = time + 1;
        startVertex.discoveryTime = time;
        for (Vertex<T> nextVertex: startVertex.getNeighbors()) {
            if (nextVertex.color == VertexColor.WHITE) {
                nextVertex.previous = startVertex;
                dfsVisit(nextVertex);
            }
        }
        startVertex.setColor(VertexColor.BLACK);
        time = time + 1;
        startVertex.closingTime = time;
    }
}

^^^^
public class Pancakes {

public static void main(String[] args) {
        DFSGraph<String> pancake = new DFSGraph<String>();
        pancake.addEdge("3/4 cup milk", "1 cup mix");
        pancake.addEdge("1 egg", "1 cup mix");
        pancake.addEdge("1 Tbsp oil", "1 cup mix");
        pancake.addEdge("1 cup mix", "pour 1/4 cup");
        pancake.addEdge("1 cup mix", "heat syrup");
        pancake.addEdge("heat griddle", "pour 1/4 cup");
        pancake.addEdge("pour 1/4 cup", "turn when bubbly");
        pancake.addEdge("turn when bubbly", "eat");
        pancake.addEdge("heat syrup", "eat");
        pancake.dfs();

ArrayList<Vertex<String>> sortList = pancake.getVertexList();
        Collections.sort(sortList, new Vertex.ByClosingTime());
        Collections.reverse(sortList);
        for (Vertex<String> v: sortList) {
            System.out.println(v.key + " (" + v.discoveryTime +
                "/" + v.closingTime + ")");
        }
   }
}

Listing 7.17.4.

Note 7.17.5. Java Note.

In line 20 of Listing 7.17.4, we call the sort method with two parameters. The first is the collection to sort; the second is a comparator, a class that gives the criteria for determining sorting order. A comparator implements a compare method that compares its two parameters. It returns a negative value if the first object is “less than” the second, zero if they are equal, and positive if the first object is “greater than” the second. Listing 7.17.6 shows the two comparators which we have added to the Vertex.java file. These are nested classes.

static class ByDiscoveryTime implements Comparator<Vertex> {
    public int compare(Vertex a, Vertex b) {
        return a.discoveryTime - b.discoveryTime;
    }
}

static class ByClosingTime implements Comparator<Vertex> {
    public int compare(Vertex a, Vertex b) {
        return a.closingTime - b.closingTime;
    }
}

Listing 7.17.6.

You have attempted of activities on this page.

Prev Top Next