20-CS-4003-001 Organization of Programming Languages Fall 2017
Topological Sort

Lambda calculus, Type theory, Formal semantics, Program analysis

All lectures        Code                     Code considerations           Demo

Topological Sort Without If or Loop Statements

import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.applet.*;
import java.net.*;

class Cell {
   Cell next;
   Node node;

   public void exec () {}
   public Cell() { next = null; node = null; }
}

class Neighbor extends Cell {

   public Neighbor (Node node, Cell next) {
      this.node = node;
      this.next = next;
   }

   public void exec () {
      node.topo.exec();
      next.exec();
   }
}

class Node {
   String id;       // The identity of this Node
   Cell neighbors;  // A linked list of Cells, each
                    // pointing to a neighbor Node
   Topo topo;       // Pointer to object of one of
                    // three classes, each defining
                    // some segment of function topo()
                    // for this Node object

   // Constructor
   Node (String id, TopoFrame f) {
      neighbors = new Cell();
      this.id = id;
      topo = new Visit(this, f); // 1st node visit
   }

   // Neighbor added to the neighborhood of this node
   void greaterThan (Node node) {
      neighbors = new Neighbor(node, neighbors);
   }

   // Get the identity of this node
   String getID () { return id; }
}

// This class is subclassed by the Cycle and Visit
// classes.  An object of those classes overrides
// the exec() method for a single Node object.
// The exec() of Visit objects explores the Node's
// neighborhood, the exec() of Cycle objects output
// a "cycle" message and exit.  The exec() of Topo
// objects act as "Done" objects and signal that the
// associated Node has already been output by having
// exec() return without any action performed.  The
// exec() method that is invoked the first time for
// a Node is the "visit" function, before the
// neighborhood is explored it is changed to the
// "cycle" function, then after the Node's id is
// output it is changed to a "done" function (see
// the Node constructor.
class Topo {
   TopoFrame frame;

   public Topo (TopoFrame f) { frame = f; }
   void exec () {}
}

class Cycle extends Topo {
   public Cycle (TopoFrame f) { super(f); }

   public void exec () {
      frame.text.append("You've hit a loop!\n");
   }
}

class Visit extends Topo {
   Node node;

   public Visit (Node node, TopoFrame frame) {
      super(frame);
      this.node = node;
   }

   // Sequence of actions:
   //  1. Replace 'visit' with 'cycle' function
   //  2. Invoke the 'topo' of all neighbors
   //  3. Replace 'cycle' with 'done' function
   //  4. Output the node's identity
   public void exec () {
      node.topo = new Cycle(frame);
      node.neighbors.exec();
      node.topo = new Topo(frame);
      frame.text.append(node.getID()+"\n");
   }
}

class TopoFrame 
   extends JFrame implements ActionListener {
   JTextArea text;
   JButton button;
   JComboBox combo;
   int count = 0;
   Vector >Node< nodes;
   Cell head;

   public TopoFrame () {
      setLayout(new FlowLayout());
      add(new JScrollPane(text=new JTextArea(30,20)));
      text.setFont(new Font("TimesRoman",Font.PLAIN,18));
      JPanel p = new JPanel();
      p.setLayout(new GridLayout(1,2));
      p.add(combo = new JComboBox());
      p.add(button = new JButton("Press Me"));
      add(p);
      combo.addItem("topo.0.dat");
      combo.addItem("topo.1.dat");
      button.addActionListener(this);
   }

   public void actionPerformed (ActionEvent evt) {
      count = 0;
      nodes = new Vector <Node> ();
      head = new Cell();
      Object s;

      text.setText("");

      // Read data from file
      // Assume format of input file:
      //   name1 name2 name3 ...
      //   name1_depend1 name1_depend2 ... name1_dependk1
      //   name2_depend1 name2_depend2 ... name2_dependk2
      //   ...
      //   namen_depend1 namen_depend2 ... name2n_dependkn
      try {
         String file = (String)combo.getSelectedItem();
         String dir = "http://gauss.ececs.uc.edu/Courses/"+
                      "c4003/java/";
         String line = null;

         URL url =
            new URL(dir+"DataDriven/Topological/"+file);
         InputStream is = (InputStream)url.getContent();
         ViewFrame vf = new ViewFrame(file,this);
         BufferedReader br =
            new BufferedReader(new InputStreamReader(is));
         try {
            line = br.readLine();
            vf.append(line);
            StringTokenizer t=new StringTokenizer(line," ");
            while (true) {
               String token = t.nextToken();
               Node node = new Node(token, this);
               nodes.add(node);
               head = new Neighbor(node, head);
            }
         } catch (Exception e) { }

         count = 0;
         try {
            while (true) {
               line = br.readLine();
               vf.append(line);
               StringTokenizer t =
                  new StringTokenizer(line," ");
               try {
                  while (true) {
                     int n = Integer.parseInt(t.nextToken());
                     Node nd = (Node)nodes.get(count);
                     nd.greaterThan(nodes.get(n));
                  }
               } catch (Exception f) { }
               count++;
            }
         }  catch (Exception e) { }
      } catch (Exception e) {
         text.append("Error: "+e.toString()+"\n");
      }

      // Done reading data from file.
      // Do the topological sort.
      head.exec();
   }
}

class ViewFrame extends JFrame {
   TopoFrame topo;
   JTextArea text;

   public ViewFrame (String file, TopoFrame t) {
      super(file);
      topo = t;
      add(new JScrollPane(text = new JTextArea(80,24)));
      setSize(500,500);
      setVisible(true);
   }

   public void append(String str) {
      text.append(str+"\n");
   }
}

public class TopoNoIf
   extends Applet implements ActionListener {
   JButton go;

   public void init () {
      setLayout(new BorderLayout());
      setBackground(new Color(255,255,223));
      add("Center", go = new JButton("Applet"));
      go.addActionListener(this);
   }

   public void actionPerformed (ActionEvent evt) {
      TopoFrame solver = new TopoFrame();
      solver.setSize(400,750);
      solver.setVisible(true);
   }
}
 -  There is a Node object for each 'item' in the partial order. A Node object maintains a neighborhood of items that are all directly known to be 'less than' the item of the Node object (these are direct 'dependencies' of the item). A Node object also holds an object of the Topo class.

A Topo object has an exec() function which can operate either as a 'visit' function, a 'cycle' function, or a 'done' function. During execution the function is changed on-the-fly to match the situation at an item as follows:

  1. If the item has not yet been visited, the function is the 'visit' function
  2. If the neighbors are being visited the function is the 'cycle' function
  3. If all neighbors have been visited the function is the 'done' function.
If a 'cycle' function is encountered during execution, a cycle has been found and the program is terminated. If a 'done' function is encountered, execution returns to the caller. Otherwise, the 'visit' function is changed to the 'cycle' function, the neighborhood is visited - that is, the exec() functions are invoked for all neighbors, if the neighbor is visited without exiting, the item's identity is output, and finally the 'cycle' function is replaced by the 'done' function.

The classes Visit and Cycle subclass Topo. Each re-implements exec() as a 'visit' or 'cycle' described above. The 'done' function is obtained using Topo directly. Getting the exec() function to change during execution is accomplished merely by replacing Topo objects - replace a Visit object with a Cycle object then a Topo object. This is seen in the exec() function of the Visit class. Initially, the Topo object is set to a Visit object in the constructor of class Node.

For each Node object a linked list of Cell objects is constructed, one for each neighbor (meaning 'this' item is directly 'greater' than the neighbor). Each Cell object has an exec() function which, similar to Topo objects, may take two forms depending on whether it is subclassed by a Neighbor object. If a Neighbor object, exec() first executes the exec() of the neighbor and then invokes exec() of the next Cell object in the list (see method exec() in class Neighbor). At the end of the list is a Cell object whose exec() terminates the traversal through the list.

When input from file, all Node objects carrying items are placed in Neighbor objects (also of type Cell) and linked, with the last object in the list being a Cell object. Clicking the "Press Me" button initiates a walk through the list, invoking exec() of each Node object, and terminating with the exec() call of a Cell object. This is shown in exec() of class Neighbor.