topSort.c: C code that uses DFS to find a topological sort of a directed, unweig

Question

topSort.c: C code that uses DFS to find a topological sort of a directed, unweighted graph.

topSort.c:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

// max number of vertices
#define MAXV 1024
// max number of char in one input line
#define BUFFER_LEN 1024

// nodes in adjacency lists of the graph
typedef struct node node;
struct node {
int v;
struct node *next;
};

// this is for a directed, unweighted graph
typedef struct {
node *adjList[MAXV];
int outDeg[MAXV];
int numVertices;
int numEdges;
} graph;

void init(int argc, char *argv[], graph *g);
void initGraph(graph *g);
int readGraph(graph *g, char *filename);
void addEdge(graph *g, int u, int v);

typedef enum {UNDISCOVERED, DISCOVERED, PROCESSED} statusT;
typedef enum {UNKNOWN, TREE, BACK, FORWARD, CROSS} edgeClassT;

// data for topological sort using DFS on a directed graph
typedef struct {
int clock;
statusT status[MAXV];
int entryTime[MAXV];
int exitTime[MAXV];
int parent[MAXV];
int inDeg[MAXV];
int stack[MAXV];
int stackSize;
} dfsDataT;

void initDFS(graph *g, dfsDataT *data);
void topSort(graph *g);
void dfs(graph *g, int u, dfsDataT *data);
edgeClassT classifyEdge(int u, int v, dfsDataT *data);

int main(int argc, char *argv[]){
graph g;

init(argc, argv, &g);
topSort(&g);
return 0;
}

void topSort(graph *g){
dfsDataT data;
int i;

initDFS(g, &data);
for (i=0;
//all vertices are in the stack when stackSize == numVertices
(i<g->numVertices) && (data.stackSize < g->numVertices);
i++){
//start DFS from a vertex with in-degree 0
if (data.inDeg[i] == 0)
dfs(g, i, &data);
}

if (data.stackSize < g->numVertices)
printf("Not a DAG, some vertices are in a cycle ");

//not really popping the stack
//just printing vertices in the stack
printf("topological sort:");
for (i=data.stackSize-1; i>=0; i--)
printf(" %d", data.stack[i]);
printf(" ");
}

void dfs(graph *g, int u, dfsDataT *data){
node *ptr;
int v;
edgeClassT class;

//timestamp on entering
data->clock++;
data->entryTime[u] = data->clock;
data->status[u] = DISCOVERED;

//walk through the adjacency list
ptr = g->adjList[u];
while (ptr != NULL){
v = ptr->v;
if (data->status[v] == UNDISCOVERED){
data->parent[v] = u;
dfs(g, v, data);
}
else if (data->status[v] != PROCESSED){ // == DISCOVERED
class = classifyEdge(u, v, data);
if (class == BACK)
   printf("Warning: a cycle is found, not a DAG ");
}
ptr = ptr->next;
}

//push u into the stack, for reverse printing of topological sort
data->stack[data->stackSize++] = u;

//timestamp on leaving
data->clock++;
data->exitTime[u] = data->clock;
data->status[u] = PROCESSED;
}

edgeClassT classifyEdge(int u, int v, dfsDataT *data){
if (data->parent[v] == u)
return(TREE);
if (data->status[v] == DISCOVERED)
return(BACK);
if (data->status[v] == PROCESSED &&
(data->entryTime[v] > data->entryTime[u]))
return(FORWARD);
if (data->status[v] == PROCESSED &&
(data->entryTime[v] < data->entryTime[u]))
return(CROSS);

//impossible
printf("can't classify edge (%d, %d) ", u, v);
return(UNKNOWN);
}

void initDFS(graph *g, dfsDataT *data){
int i;
node *ptr;

data->clock = 0;
data->stackSize = 0;

for (i=0; i<g->numVertices; i++){
data->status[i] = UNDISCOVERED;
data->entryTime[i] = -1;
data->exitTime[i] = -1;
data->parent[i] = -1;
data->inDeg[i] = 0;
}

//walk through all adjacency lists, count in-degrees of all vertices
//later on, start DFS with a vertex of in-degree 0
for (i=0; i<g->numVertices; i++){
ptr = g->adjList[i];
while (ptr != NULL){
data->inDeg[ptr->v]++;
ptr = ptr->next;
}
}
}

void initGraph(graph *g){
int i;

g->numVertices = 0;
g->numEdges = 0;
for (i=0; i<MAXV; i++){
g->outDeg[i] = 0;
g->adjList[i] = NULL;
}
}

void addEdge(graph *g, int u, int v){
node *ptr;

ptr = (node*)malloc(sizeof(node));
ptr->v = v;
ptr->next = g->adjList[u];
g->adjList[u] = ptr;
g->outDeg[u]++;
}

int readGraph(graph *g, char *filename){
int i, u, v;
char buffer[BUFFER_LEN];
FILE *fp = NULL;

initGraph(g);
fp = fopen(filename, "r");
if (!fp) //file is not opened
return -1;

//first line: numVertices, numEdges
if (!fgets(buffer, BUFFER_LEN, fp))
return -1;
sscanf(buffer, "%d %d", &(g->numVertices), &(g->numEdges));
if (g->numVertices < 1 || g->numVertices > MAXV || g->numEdges < 1)
return -1;

//input the edges, one at a time
for (i=0; i<g->numEdges; i++){
if (!fgets(buffer, BUFFER_LEN, fp))
return -1;
sscanf(buffer, "%d %d", &u, &v);
if (u < 0 || u >= g->numVertices || v < 0 || v >= g->numVertices)
return -1;
addEdge(g, u, v);
}

fclose(fp);

return g->numVertices;
}

void init(int argc, char *argv[], graph *g){
int c;
char filename[BUFFER_LEN];

strcpy(filename, "oneTopSort.txt");

//process the command line
//only one option is accepted for now: "./topSort -f filename"
//maybe -d for debugging
while ((c = getopt(argc, argv, "f:")) != -1){
switch (c){
case 'f':
//guard against buffer overflow attack
if (strlen(optarg) > BUFFER_LEN-1)
   printf("filename too long ");
else
   strcpy(filename, optarg);
break;
default:
break;
}
}

printf("Input file is %s ", filename);
c = readGraph(g, filename);
if (c < 1){
printf("File %s doesn't exist, or it is in the wrong format. ",
   filename);
exit(1);
}
printf("The graph has %d vertices and %d edges ", c, g->numEdges);
}

Explanation / Answer

// Copyright 2004 The Trustees of Indiana University. // Use, modification and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // Authors: Douglas Gregor // Andrew Lumsdaine #include #include #include #include #include #include #include #include #include #include using namespace boost; const double error_tolerance = 0.001; typedef property EdgeProperties; struct weighted_edge { int source, target; double weight; }; template void run_weighted_test(Graph*, int V, weighted_edge edge_init[], int E, double correct_centrality[]) { Graph g(V); typedef typename graph_traits::vertex_descriptor Vertex; typedef typename graph_traits::vertex_iterator vertex_iterator; typedef typename graph_traits::edge_descriptor Edge; std::vector vertices(V); { vertex_iterator v, v_end; int index = 0; for (boost::tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) { put(vertex_index, g, *v, index); vertices[index] = *v; } } std::vector edges(E); for (int e = 0; e

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.