@i gb_types.w

\def\title{TOP\_\,ORD}

@* Topological ordering.  This is a short demonstration of how to sort the
vertices of an acyclic directed graph in {\it topological order\/}, that is,
how to enumerate the vertices in such a way that all arcs go ``from left to
right''.  This program assumes that the input graphs are produced by the
|prod()| routine in |GB_GATES|.  In fact, the user may give in the command
line the parameters~|n| and~|m| to be fed to |prod()|, and can also recover a
graph (assumed to have been produced by |prod()|) from a file giving the name
of the file.

@p
#include "gb_graph.h" /* we use the {\sc GB\_\,GRAPH} data structures */
#include "gb_gates.h" /* we use, as default, the graphs produced by |prod()| */ 
#include "gb_save.h" /* and we save our results in ASCII format */

@#
#define source @[a.V /* util field |a| keeps the source of edge */@]
#define back_next @[b.A /* util field |b| points to the next back arc
                    in the list */@]
#define back_arcs @[w.A /* util field |w| keeps the first back arc at a
                    vertex */@]

@#
#define sorv_list @[yy.V /* we shall keep a linked list of the 
                    current sinks */@] 
#define sorv_next @[v.V /* for the linked list of the current sinks */@]

@#
#define out_deg @[u.I /* we keep the out degree of the vertices 
                  at every stage */@]

@#
#define top_order @[xx.V /* the topological ordering of the vertices will be
                    built in this list */@]
#define top_next @[v.V /* for the linked list of the vertices in topological
                   order */@] 
                  
@#
main(argc,argv)
  int argc; /* the number of command-line arguments */
  char *argv[]; /* an array of strings containing those arguments */
{@+Graph *g;
  unsigned long n=2; /* the number of bits in the first factor */
  unsigned long m=2; /* the number of bits in the second factor */
  long print_graph=1; /* if to print; default "yes" */
  long print_order=1; /* if to print the topological ordering; default "yes" */ 
  long save_top_ordered_graph=1; /* if to save the graph with the vertices
                                    topologically ordered; default "yes" */   
  char *file_name=NULL; /* external graph to be restored */ 

  @<Scan the command-line options@>;
  @<Build the graph |g| to work with@>;
  @<Print the vertices and edges of |g|@>;
  @<Build the linked list of the vertices of |g| in topological order@>;
  @<Print the vertices of |g| in the topological order we built@>;
  @<Save the graph with the linked list of topologically sorted vertices@>; 
  return 0; /* normal exit */
}

@ @<Scan the command-line options@>=
while (--argc) {
  if (sscanf(argv[argc],"-n%lu",&n)==1) ;
  else if (sscanf(argv[argc],"-m%lu",&m)==1) ;
  else if (strcmp(argv[argc],"--no_graph")==0) print_graph=0;
  else if (strcmp(argv[argc],"--no_top")==0) print_order=0;
  else if (strcmp(argv[argc],"--dont_save")==0) save_top_ordered_graph=0; 
  else if (strncmp(argv[argc],"-g",2)==0) file_name=argv[argc]+2;
  else {
    fprintf(stderr,
             "Usage: %s [-nN][-mN][--no_graph][--no_top][--dont_save][-gfoo]\n",
             argv[0]);
    return -2;
  }
}

@ @<Build the graph |g| to work with@>=
if (file_name)
  g=restore_graph(file_name);
else
  g=prod(n,m); /* the circuit graph */

@ This is a program to check whether we're doing things right.  So, actually,
in this section we print the `physical' addresses of the vertices and of the
vertices to which our vertices send edges, by which we mean the following.
If~|v| points to the vertex structure |g->vertices[k]|, then we say that |v|'s
physical address is~|k|.  Below, we print these physical addresses for our
vertices.  The physical address of a vertex may be computed if we know the
memory address of this vertex, the memory address of the the first vertex of
the graph, and the amount of space that a vertex structure takes up in memory.

The point is the following: the graphs produced by |prod()| have their
vertices in {\it reverse topological order} (all edges go from ``right to
left'').  So we can check whether our output is correct!

@<Print the vertices of |g| in the topological order we built@>=   
if (print_order) {
  register Vertex *v;
  register siz_t physical_add; 
  long k;
  for (v=g->top_order,k=1; v; v=v->top_next,k++) {
    physical_add=((siz_t)(v)-(siz_t)(g->vertices))/((siz_t)(sizeof(Vertex))); 
    printf("(vertex number %ld) %s [%ld]\n", k, v->name, physical_add);
    @<Print the physical address of the vertices to which |v| sends arcs@>;
  }
}       

@ @<Print the physical address of the vertices to which |v| sends arcs@>={@+
  register Arc *a;
  printf("  ->");
  for (a=v->arcs; a; a=a->next) {
    register siz_t physical_add_tip;
    physical_add_tip=((siz_t)(a->tip)-(siz_t)(g->vertices))
             /((siz_t)(sizeof(Vertex))); 
    printf(" %ld", physical_add_tip);
    if (physical_add_tip>physical_add) {
      printf("Error: just found an arc going the wrong way!");
      return -1;
    }
  }
  printf("\n");
}

@ @<Save the graph with the linked list of topologically sorted vertices@>=  
if (save_top_ordered_graph) {
  strcpy(g->util_types,"IVAIIVVAZZZVVA");
  save_graph(g,"top_sorted.gb"); /* generate an ASCII file for |g| */
}

@ @<Print the vertices and edges of |g|@>=
if (print_graph) {
  if (g==NULL) printf("Something went wrong (panic code %ld)!\n", panic_code);
  else {
    register Vertex *v; /* current vertex being visited */
    printf("  The graph whose official name is\n%s\n", g->id);
    printf("  has %ld vertices and %ld arcs:\n\n", g->n, g->m);
    for (v=g->vertices; v<g->vertices+g->n; v++) {
      register Arc *a; /* current arc from |v| */
      printf("%s\n", v->name);
      for (a=v->arcs; a; a=a->next)
        printf("  -> %s\n", a->tip->name);
    }
  }
}

@* The topological sorting algorithm.  We use the standard algorithm.
 
@<Build the linked list of the vertices of |g| in topological order@>={@+
 long k; /* This is the "rank" of the vertex we are putting into the topological */
         /* order linked list.  The last vertex in the order has |k=g->n|. */
 @<Initialize the list of vertices of |g| in top order@>;
 @<Compute the out degrees and initialize the linked list of sinks@>;
 @<Add the linked lists of backward arcs at all vertices of |g|@>;
 for (k=g->n; k>0; k--) 
   if (!g->sorv_list)
     @<Report invalid input and stop@> @;
   else { 
     register Vertex *y;
     @<Pick a sink |y| and let it be the |k|th vertex in the top order@>;
     @<Update the out degrees and sinks list@>;
   }
}

@ @<Initialize the list of vertices of |g| in top order@>=
g->top_order=NULL;

@ @<Compute the out degrees and initialize the linked list of sinks@>={@+
  register Vertex *v;  
  g->sorv_list=NULL;
  for (v=g->vertices; v<g->vertices+g->n; v++) {
    register long d=0;
    register Arc *a;
    for (a=v->arcs; a; a=a->next) d++;
    v->out_deg=d;
    if (d==0) {
      v->sorv_next=g->sorv_list;
      g->sorv_list=v;
    }
  }
}

@ @<Pick a sink |y| and let it be the |k|th vertex in the top order@>=
y=g->sorv_list;
g->sorv_list=y->sorv_next;

y->top_next=g->top_order;
g->top_order=y;

@ @<Update the out degrees and sinks list@>={@+
  register Arc *a;
  for (a=y->back_arcs; a; a=a->back_next)
    if (--a->source->out_deg==0) {
      /* We add |a->source| to the list of current sinks */
      a->source->sorv_next=g->sorv_list;
      g->sorv_list=a->source;
    }
}  
        
@ @<Add the linked lists of backward arcs at all vertices of |g|@>={@+
  Vertex *v;
  Arc *a;

  for (v=g->vertices; v<g->vertices+g->n; v++)
    v->back_arcs=NULL;
  for (v=g->vertices; v<g->vertices+g->n; v++)
    for (a=v->arcs; a; a=a->next) {
      register Vertex *u;
      a->source=v;
      u=a->tip;
      a->back_next=u->back_arcs;
      u->back_arcs=a;
    }
}

@ This part could be improved: instead of simply saying something went wrong,
we could write some code to find a closed directed cycle in the input graph,
thus showing that the input graph admits no topological ordering of its
vertices.

@<Report invalid input and stop@>={@+
  printf("Error: the set of current sinks became empty before the right time!\n");
  return -1;
}

@* Index.