⟦efb9bd03e⟧

TextFile

// Date: Sun, 18 Sep 88 15:57:31 -0700
// From: "Douglas C. Schmidt" <schmidt%crimee.ics.uci.edu@ORION.CF.UCI.EDU>

// I wrote the following useful
// tool to perform topological sorting in O(n + m) average-time (n == #
// of vertices, m == # of edges).  Feel free to add it, or any of its
// components parts to the libg++ library in any shape or form you
// desire.

// If you happen to have Andrew Koenig's Summer USENIX '88 article on
// Associative Arrays in C++ it is interesting to compare his solution to
// mine.  Basically, my version, which uses hashing as opposed to his AVL
// trees, should be *much* faster on the average (it would be interesting
// to compare the two).  In fact, if you test the code below against the
// standard UNIX tsort routine, you should be *amazed* at how much faster
// it is (several orders of magnitude on large input files)!

#include <stream.h>
#include <String.h>

#define NIL(TYPE) ((TYPE *)0)

class Vertex_Node;  // forward decls
class Assoc_Array;
class Assoc_Iter;

// Note: Most of the pointer types, like the **Hash_Table should probably be
// typedeffed.  Unfortunately, this breaks the G++ 1.27 compiler!

class Adjacency_Node 
{
  // Defines and implements the adjacency list abstraction that contains the list
  // of vertices that are incident to given vertex.  Note that we store Vertex_Node
  // pointers here, rather than vertex *Names*.  This allows us to find a particular
  // vertex in the Hash_Table in O(1) time, without having to perform the usual
  // hash lookup (compare this with Andrew Koenig's implementation from the Summer
  // USENIX '88 proceedings!)

private:
   Vertex_Node    *Item_Ptr;
   Adjacency_Node *Next_Ptr;

public:

   Adjacency_Node (Vertex_Node *New_Item,Adjacency_Node *Head): 
   Item_Ptr (New_Item), Next_Ptr (Head)
     {
       // The constructor simply orders the adjacency list as a stack.
       ;
     }
   
   Vertex_Node *Item (void) 
     {
       return this->Item_Ptr;
     }
   
   Adjacency_Node *Next (void) 
     {
       return this->Next_Ptr;
     }
 };

class Vertex_Node 
{
  // The Hash_Table is composed of these Vertex_Nodes.  Each Vertex_Node contains
  // an adjacency list of successor nodes, and an In_Degree count.  Each operation
  // is extremely concise and self-explanatory, with the exception of the overloaded
  // ``+='' operator, which essentially means ``Add the successor node to the successor
  // list (OK, so this is an abuse of overloading!)
  
private:
friend class Vertex_Node& Assoc_Array::Lookup_In_Hash_Table (String& Index);
friend class Vertex_Node *Assoc_Iter::operator ()(void);
  
  int             In_Degree;
  String          Name;    // Using (char *) here is faster, but less abstract!
  Adjacency_Node *Succ_List;
  Vertex_Node    *Next;
  
public:
  
  Vertex_Node (String Item,Vertex_Node *N = NIL (Vertex_Node)):
  In_Degree (0), Name (Item), Next (N), Succ_List (NIL (Adjacency_Node)) { }
  
  int In_Degree_Count (void) 
    {
      return In_Degree;
    }
  
  Adjacency_Node *Get_Succ_List (void) 
    {
      return Succ_List;
    }
  
  Vertex_Node& operator ++ (void)
    {
      In_Degree++;
      return *this;
    }
  
  int operator -- (void)
    {
      return --In_Degree;
    }
  
  Vertex_Node& operator += (Vertex_Node& Succ_Node)
    {
      Succ_List = new Adjacency_Node (&Succ_Node,Succ_List);
      return *this;
    }
  
  String Item (void) 
    {
      return Name;
    }
  
  friend ostream& operator << (ostream& Stream,Vertex_Node& Output)
    {
      return Stream << Output.In_Degree;
    }
  
};

class Assoc_Array
{
  // Here's the main data structure.  It is simply a Hash_Table of Vertex_Nodes.
  // I make use of hashpjw from the libg++ builtin library.  Nothing too tricky
  // here....  I overload the [] operator to provide the classic ``associative
  // array'' touch.
  
private:
friend class Vertex_Node *Assoc_Iter::operator ()(void);
  
  int           Total_Size;
  int           Current_Size;
  Vertex_Node **Hash_Table;
  
  Vertex_Node& Lookup_In_Hash_Table (String& Index)
    {
      int          Location = hashpjw (Index) % Total_Size;
      Vertex_Node *Head     = Hash_Table[Location];
      
      if (!Head)
        {
          Current_Size++;
          return *(Hash_Table[Location] = new Vertex_Node (Index));
        }
      else 
        {
        
          while (Head)
            {
              if (Head->Name == Index) 
                return *Head;
              Head = Head->Next;
            }
        
          Current_Size++;
          return *(Hash_Table[Location] = new Vertex_Node (Index,Hash_Table[Location]));
        }
    }
  
public:
  Assoc_Array (int Size = 100): Current_Size (0),Total_Size (Size)
    {
      Hash_Table = new Vertex_Node *[Size];         
      bzero (Hash_Table,Size * sizeof (Vertex_Node *));
    }
  
  Vertex_Node& operator[](String Index)
    {
      return Lookup_In_Hash_Table (Index);
    }
  
  int Array_Size (void)
    {
      return Current_Size;
    }
  
  int Max_Size (void)
    {
      return Total_Size;
    }
  
};

class Assoc_Iter
{
  // This is a neat class, which implements an iterator for the Hash_Table used
  // for the associative array.  It would be faster to search the table directly,
  // without using an iterator, but this is a neat feature of C++ that fits too
  // nicely into the overall abstraction to pass up!
  
private:
  Assoc_Array *Assoc;
  Vertex_Node *Curr;
  int          Curr_Table_Pos;
  
public:
  Assoc_Iter (Assoc_Array& Array,int Items): 
  Assoc (&Array), Curr (NIL (Vertex_Node)), Curr_Table_Pos (Items - 1) { }
  
  Vertex_Node *operator ()(void)
    {
      if (Curr_Table_Pos <= 0)  // we're at the end of the table, quit.
        return NIL (Vertex_Node);
      else if (!Curr)
        {                       // need to find a new bucket list to search.
          
          while (Curr_Table_Pos >= 0 && !Assoc->Hash_Table[Curr_Table_Pos])
            Curr_Table_Pos--;
          
          if (Curr_Table_Pos < 0) 
            return NIL (Vertex_Node);
          else 
            Curr = Assoc->Hash_Table[Curr_Table_Pos];
        }
      
      Vertex_Node *Temp = Curr;
      if (!(Curr = Curr->Next)) // try to update Curr for next call.
        Curr_Table_Pos--;
      
      return Temp;
    }
};

class Node_Stack
{
  // Yawn.... This is a very simple stack abstraction.  I probably should have 
  // used some generic routine from libg++.... ;-)  Doesn't perform error checking.
  
private:
  int           Top;
  int           Max_Node_Stack_Size;
  Vertex_Node **Node_Stack_Items;
  
public:
  Node_Stack (int Size): Top (Size), Max_Node_Stack_Size (Size)
    {
      Node_Stack_Items = new Vertex_Node *[Size];
    }
  
  int  Empty ()
    {
      return Top >= Max_Node_Stack_Size;
    }
  
  void Push (Vertex_Node *Item)
    {
      Node_Stack_Items[--Top] = Item;
    }
  
  Vertex_Node *Pop (void)
    {
      return Node_Stack_Items[Top++];
    }
};

const int Default_Size = 200;

main (int argc,char *argv[])
{
  Assoc_Array A ((argc > 1) ? atoi (argv[1]) : Default_Size);
  String Prev;
  String Succ;
  
  // The use of ``+='' below is rather obscure.  It simply means ``prepend the
  // address of A[Succ] to the adjacency list of A[Prev].  See the comment in
  // the member definition for class Vertex_Node.  Note that the ++ operator
  // has also been overloaded.  This allows concise, extremely efficient mechanism
  // to enter the Prev and Succ items into the associative array.
  
  while (cin >> Prev >> Succ) 
    if (Prev == Succ)       // Just record existence of identical tokens.
      A[Prev];
    else 
      A[Prev] += ++A[Succ];
  
  Assoc_Iter   Next (A,A.Max_Size ());
  Node_Stack   Stack (A.Array_Size ());
  Vertex_Node *Node_Ptr;
  
  // Iterate through all the items in the associative array, performing the
  // typical topological sort trick of pushing all ``sources'' onto a stack.
  // This gives us an order of magnitude win over the standard UNIX tsort
  // routine, which has quadratic average time complexity (in the number of
  // verticies!!!!).
  
  while (Node_Ptr = Next ()) 
    if (Node_Ptr->In_Degree_Count () == 0) 
      Stack.Push (Node_Ptr);
  
  // The following code is straight-forward, but the one line with the expression
  // --(*List->Item ()) == 0 is rather cryptic.  It is simply dereferencing a pointer
  // to a Vertex_Node, and then passing this by reference to the overloaded --
  // operator from the Vertex_Node class (yes, it *is* easy to abuse this
  // technique!).
  
  for (int Items = 0; !Stack.Empty (); Items++)
    {
      Node_Ptr = Stack.Pop ();
      cout << Node_Ptr->Item () << "\n";
      
      for (Adjacency_Node *List = Node_Ptr->Get_Succ_List (); List; List = List->Next ())
        if (--*List->Item () == 0) 
          Stack.Push (List->Item ());                         
      
    }
  
  if (Items != A.Array_Size ())
    cout << "Error, directed graph has a cycle!\n";
  return 0;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦efb9bd03e⟧ TextFile

Derivation

TextFile
