title: Trying to do a topological sort of a graph in c?
body: <p>I'm working on code for a topological sort program for graphs. I've implemented the algorithm by doing a depth-first search of the graph, putting each vertex value into a stack, and the popping the values off of the stack and printing them out. This should be producing a topological sort, but so far I consistently get one value less than I put in as far as number of vertices, and none of the number match those I've inputted.</p>
  
  <pre><code>status topological_search(graph G, vertex vertex_number, bool visited[], status
   (*p_func_f)()){
  
    edge *p_edge = NULL;
    int *temp ;
    stack S ;
  
    init_stack(&amp;S) ;
    temp = (int *) malloc(sizeof(int)) ;
  
    while((p_edge = edge_iterator(G, vertex_number, p_edge)) != NULL){
      if(visited[VERTEX(p_edge)] == FALSE){
  
        visited[VERTEX(p_edge)] = TRUE ;
        *temp = VERTEX(p_edge) ;
        push(&amp;S, (generic_ptr) temp) ;
        vertex_number = VERTEX(p_edge) ;
      }
    }
    while(!empty_stack(&amp;S)){
      pop(&amp;S, (generic_ptr) &amp;temp) ;
      (*p_func_f)(*temp) ;
    }
    return OK ;
  }
  </code></pre>
  
  <p>My stack function all work normally, they've been tested in other programs. Edge_iterator is straight from the textbook and functions normally. Any advice on where my sort is getting the wrong number would be greatly appreciated.</p>
  
  <p>EDIT: I've reedited the code to reflect the changes suggested to vertex_number and the while{..} loop. However now the program will only print he first vertex and nothing else. I can see how before the loop would not visit every node in the graph, however now it only visits one before stopping? Where is this being stopped?</p>
  
  <p>Here's Edge_iterator </p>
  
  <pre><code>edge *edge_iterator(graph G, vertex vertex_number, edge *p_last_return){
  
    vertex other_vertex ;
    if(vertex_number &lt; 0 || vertex_number &gt;= G-&gt;number_of_vertices) return NULL ;
  
    if(p_last_return == NULL) other_vertex = 0 ;
    else other_vertex = VERTEX(p_last_return) + 1 ;
  
    for( ; other_vertex &lt; G-&gt;number_of_vertices; other_vertex++){
      if(G-&gt;matrix[vertex_number][other_vertex].weight != UNUSED_WEIGHT)
        return &amp;G-&gt;matrix[vertex_number][other_vertex] ;
    }
    return NULL ;
  }
  </code></pre>
  
  <p>and the graph implementation.</p>
  
  <pre><code>typedef int vertex ;
  typedef struct {int weight; vertex vertex_number ;} edge ;
  
  #define UNUSED_WEIGHT (32767)
  #define WEIGHT(p_e) ((p_e) -&gt; weight)
  #define VERTEX(p_e) ((p_e) -&gt; vertex_number)
  
  typedef enum {directed, undirected} graph_type ;
  typedef enum {DEPTH_FIRST, TOPOLOGICAL } searchorder ;
  
  typedef struct {
    graph_type type ;
    int number_of_vertices ;
    edge **matrix ;
  }graph_header, *graph ;
  </code></pre>