| @@ -0,0 +1,235 @@ | ||
| #include <stdlib.h> | ||
| #include <stdio.h> | ||
| #include <math.h> | ||
| #include <string.h> | ||
| #include <assert.h> | ||
| #include "graph.h" | ||
|
|
||
| /* PARTIAL IMPLEMENTATION OF graph.h *************************************** */ | ||
|
|
||
| /* list node to represent an edge, for adjacency list */ | ||
| struct eNode { | ||
| float wt; | ||
| int target; | ||
| struct eNode* next; | ||
| }; | ||
| typedef struct eNode* ENode; | ||
|
|
||
| /* The graph; see graph.h for type Graph. | ||
| Depending on the repType field, one of the fields adjM or aLists is not used. | ||
| (We could use a union for this, but it's not worth the trouble.) | ||
| Invariant: each adjacency list begins with a dummy node. | ||
| */ | ||
| struct graph { | ||
| short repType; /* MATRIX or LIST representation */ | ||
| int numVerts; | ||
| float* adjM; /* the adjacency matrix, size numVerts*numVerts */ | ||
| ENode* aList; /* array of adjacency lists; length numVerts */ | ||
| }; | ||
|
|
||
|
|
||
| /* Make an empty graph with n vertices, using either adjacency matrix | ||
| or adjacency lists depending on whether rep==MATRIX or rep==LIST. | ||
| Precondition: n>=1 and rep is MATRIX or LIST. | ||
| */ | ||
| Graph makeGraph(int n, int rep) { | ||
| Graph g = (Graph) malloc(sizeof(struct graph)); | ||
| g->numVerts = n; | ||
| g->repType = rep; | ||
| if (rep == MATRIX) { | ||
| g->aList = NULL; | ||
| g->adjM = (float*) malloc(n * n * sizeof(float)); | ||
| for (int src = 0; src < n; src++) | ||
| for (int trg = 0; trg < n; trg++) | ||
| *(g->adjM + (n*src) + trg) = INFINITY; // (g->adjM)[src][trg] = INFINITY; | ||
| } else { // repType is LIST | ||
| g->adjM = NULL; | ||
| g->aList = (ENode*) malloc(n * sizeof(ENode)); | ||
| // initialize with dummy nodes | ||
| for (int src = 0; src < n; src++) { | ||
| ENode node = (ENode) malloc(sizeof(struct eNode)); | ||
| node->wt = 0.0; | ||
| node->target = 0; | ||
| node->next = NULL; | ||
| *(g->aList + src) = node; | ||
| } | ||
| } | ||
| return g; | ||
| } | ||
|
|
||
|
|
||
| /* make a copy of g, but using the representation | ||
| specified by rep (which is assumed to be MATRIX or LIST) | ||
| Known bug: not implemented | ||
| */ | ||
| Graph cloneGraph(Graph g, int rep){ | ||
| printf("cloneGraph not supported.\n"); | ||
| exit(1); | ||
| } | ||
|
|
||
|
|
||
| /* free the graph object and all its resources. | ||
| Postcondition: g is no longer a valid pointer. | ||
| Alert: the caller should set their variable to null. | ||
| Known bug: does not free nodes of adjacency lists. | ||
| */ | ||
| void disposeGraph(Graph g) { | ||
| if (g->repType == MATRIX) | ||
| free(g->adjM); | ||
| else { // repType is LIST | ||
| free(g->aList); | ||
| } | ||
| free(g); | ||
| } | ||
|
|
||
|
|
||
| /* number of vertices */ | ||
| int numVerts(Graph g){ | ||
| return g->numVerts; | ||
| } | ||
|
|
||
|
|
||
| /* add edge from source to target with weight w, and return | ||
| OK, if source and target are valid vertex numbers and | ||
| there was no edge from source to target initially. | ||
| Otherwise, make no change and return ERROR. | ||
| */ | ||
| int addEdge(Graph g, int source, int target, float w) { | ||
| int n = g->numVerts; | ||
| if (source < 0 || source >= n || target < 0 || target >= n) | ||
| return ERROR; | ||
| if (g->repType == MATRIX) { | ||
| if ( *(g->adjM + (n*source) + target) != INFINITY ) | ||
| return ERROR; // an edge was already present | ||
| *(g->adjM + (n*source) + target) = w; | ||
| } else { // rep is LIST; attach at end of list | ||
| ENode p = *(g->aList + source); | ||
| while (p->next != NULL && p->next->target != target) | ||
| p = p->next; | ||
| if (p->next != NULL ) | ||
| return ERROR; // an edge was already present | ||
| else { | ||
| ENode node = (ENode) malloc(sizeof(struct eNode)); | ||
| p->next = node; | ||
| node->wt = w; | ||
| node->target = target; | ||
| node->next = NULL; | ||
| } | ||
| } | ||
| return OK; | ||
| } | ||
|
|
||
| /* delete edge from source to target, and return | ||
| OK, if there was an edge from source. | ||
| Otherwise, make no change and return ERROR. | ||
| */ | ||
| int delEdge(Graph g, int source, int target) { | ||
| int n = g->numVerts; | ||
| if (source < 0 || source >= n || target < 0 || target >= n) | ||
| return ERROR; | ||
| if (g->repType == MATRIX) { | ||
| if ( *(g->adjM + (n*source) + target) == INFINITY ) | ||
| return ERROR; | ||
| *(g->adjM + (n*source) + target) = INFINITY; | ||
| } else { // LIST | ||
| ENode follow = *(g->aList + source); | ||
| ENode p = follow->next; // skip dummy node | ||
| while (p != NULL && p->target != target) { | ||
| follow = p; | ||
| p = p->next; | ||
| } | ||
| if (p == NULL) | ||
| return ERROR; | ||
| else { | ||
| follow->next = p->next; | ||
| free(p); | ||
| } | ||
| } | ||
| return OK; | ||
| } | ||
|
|
||
|
|
||
| /* return weight of the edge from source to target, | ||
| if there is one; otherwise return INFINITY. | ||
| Return -1.0 if source or target are out of range. | ||
| */ | ||
| float edge(Graph g, int source, int target) { | ||
| int n = g->numVerts; | ||
| if (source < 0 || source >= n || target < 0 || target >= n) | ||
| return -1.0; | ||
| if (g->repType == MATRIX) { | ||
| return *(g->adjM + (n * source) + target); | ||
| } else { // LIST | ||
| ENode p = *(g->aList + source); | ||
| p = p->next; // skip dummy node | ||
| while (p != NULL && p->target != target) | ||
| p = p->next; | ||
| if (p == NULL) | ||
| return INFINITY; | ||
| else | ||
| return p->wt; | ||
| } | ||
| } | ||
|
|
||
|
|
||
| /* a freshly allocated array with the successor | ||
| vertices of source, if any, followed by an entry with -1 | ||
| to indicate end of sequence. | ||
| Precondition: source is in range. | ||
| */ | ||
| int* successors(Graph g, int source) { | ||
| int n = g->numVerts; | ||
| int succ[n]; // temporary array, on the stack, big enough for all possible successors | ||
| int nsucc = 0; // actual number of successors | ||
|
|
||
| /* get precedessors into temporary array in the current stack frame */ | ||
| if (g->repType == MATRIX) { | ||
| for (int trg = 0; trg < g->numVerts; trg++) | ||
| if ( *(g->adjM + (n*source) +trg) != INFINITY ) | ||
| succ[nsucc++] = trg; | ||
| } else { // LIST | ||
| ENode p = *(g->aList + source); | ||
| p = p->next; // skip dummy node | ||
| while (p != NULL ) { | ||
| succ[nsucc++] = p->target; | ||
| p = p->next; | ||
| } | ||
| } | ||
| /* allocate and return an array the right size */ | ||
| int* result = (int*) malloc((nsucc + 1) * sizeof(int)); | ||
| for (int i = 0; i < nsucc; i++) | ||
| result[i] = succ[i]; | ||
| result[nsucc] = -1; | ||
| return result; | ||
| } | ||
|
|
||
|
|
||
| /* a freshly allocated array with the predecessor | ||
| vertices of target, if any, followed by an entry with -1 | ||
| to indicate end of sequence. | ||
| Precondition: target is in range. | ||
| Known bug: not implemented for LIST. | ||
| */ | ||
| int* predecessors(Graph g, int target) { | ||
| if (g->repType == LIST) { | ||
| fprintf(stderr, "graph predecessors not implemented for LIST representation.\n"); | ||
| exit(1); | ||
| } // else MATRIX | ||
| /* get precedessors into temporary array in the current stack frame */ | ||
| int n = g->numVerts; | ||
| int pred[n]; // temporary array, big enough for all possible predecessors | ||
| int npred = 0; // number of predecessors | ||
| for (int src = 0; src < g->numVerts; src++) | ||
| if ( *(g->adjM + (n*src) +target) != INFINITY ) | ||
| pred[npred++] = src; | ||
| /* allocate and return an array the right size */ | ||
| int* result = (int*) malloc((npred + 1) * sizeof(int)); | ||
| for (int i = 0; i < npred; i++) | ||
| result[i] = pred[i]; | ||
| result[npred] = -1; | ||
| return result; | ||
| } | ||
|
|
||
|
|
||
|
|
||
|
|
| @@ -0,0 +1,77 @@ | ||
| /* Simple interface for weighted directed graphs. | ||
| The vertices are numbered 0 .. n-1 for some fixed n. | ||
| Edges have nonnegative weights. | ||
| The two standard graph representations are supported. | ||
| Function cloneGraph() can be used to convert between | ||
| representations. | ||
| Precondition: all functions except makeGraph assume their | ||
| Graph argument is non-null. | ||
| */ | ||
|
|
||
| #define MATRIX 0 | ||
| #define LIST 1 | ||
|
|
||
| #define OK 0 | ||
| #define ERROR 1 | ||
|
|
||
| struct graph; | ||
| typedef struct graph* Graph; | ||
|
|
||
| /* make an empty graph with n vertices, | ||
| using either adjacency matrix or adjacency lists | ||
| depending on whether rep==MATRIX or rep==LIST | ||
| Precondition: n>=1 and rep is MATRIX or LIST. | ||
| */ | ||
| Graph makeGraph(int n, int rep); | ||
|
|
||
| /* make a copy of G, but using the representation | ||
| specified by rep (which is assumed to be MATRIX or LIST) | ||
| */ | ||
| Graph cloneGraph(Graph G, int rep); | ||
|
|
||
| /* free the graph object and all its resources. | ||
| Postcondition: G is no longer a valid pointer. | ||
| Alert: the caller should set their variable to null. | ||
| */ | ||
| void disposeGraph(Graph G); | ||
|
|
||
| /* number of vertices */ | ||
| int numVerts(Graph G); | ||
|
|
||
| /* add edge from source to target with weight w, and return | ||
| OK, if source and target are valid vertex numbers and | ||
| there was no edge from source to target initially. | ||
| Otherwise, make no change and return ERROR. | ||
| */ | ||
| int addEdge(Graph G, int source, int target, float w); | ||
|
|
||
| /* delete edge from source to target, and return | ||
| OK, if there was an edge from source. | ||
| Otherwise, make no change and return ERROR. | ||
| */ | ||
| int delEdge(Graph G, int source, int target); | ||
|
|
||
| /* return weight of the edge from source to target, | ||
| if there is one; otherwise return INFINITY. | ||
| Return -1 if source or target are out of range. | ||
| */ | ||
| float edge(Graph G, int source, int target); | ||
|
|
||
| /* a freshly allocated array with the successor | ||
| vertices of source, if any, followed by an entry with -1 | ||
| to indicate end of sequence. | ||
| Precondition: source is in range. | ||
| */ | ||
| int* successors(Graph G, int source); | ||
|
|
||
| /* a freshly allocated array with the predecessor | ||
| vertices of target, if any, followed by an entry with -1 | ||
| to indicate end of sequence. | ||
| Precondition: target is in range. | ||
| */ | ||
| int* predecessors(Graph G, int target); | ||
|
|
| @@ -0,0 +1,48 @@ | ||
| 16 | ||
| cs115 | ||
| cs135 | ||
| cs146 | ||
| cs284 | ||
| cs306 | ||
| cs347 | ||
| cs385 | ||
| cs334 | ||
| cs335 | ||
| cs370 | ||
| cs383 | ||
| cs392 | ||
| cs423 | ||
| cs442 | ||
| cs492 | ||
| cs496 | ||
|
|
||
| cs115 cs284 | ||
|
|
||
| cs115 cs334 | ||
| cs135 cs334 | ||
|
|
||
| cs334 cs496 | ||
| cs385 cs496 | ||
|
|
||
| cs385 cs442 | ||
|
|
||
| cs383 cs492 | ||
|
|
||
| cs385 cs392 | ||
|
|
||
| cs385 cs492 | ||
|
|
||
| cs135 cs347 | ||
| cs284 cs347 | ||
|
|
||
| cs385 cs423 | ||
| cs347 cs423 | ||
|
|
||
| cs385 cs370 | ||
|
|
||
| cs284 cs383 | ||
|
|
||
| cs284 cs385 | ||
|
|
||
|
|
||
|
|
| @@ -0,0 +1,161 @@ | ||
| 51 | ||
| AL | ||
| AK | ||
| AZ | ||
| AR | ||
| CA | ||
| CO | ||
| CT | ||
| DC | ||
| DE | ||
| FL | ||
| GA | ||
| HI | ||
| ID | ||
| IL | ||
| IN | ||
| IA | ||
| KS | ||
| KY | ||
| LA | ||
| ME | ||
| MD | ||
| MA | ||
| MI | ||
| MN | ||
| MS | ||
| MO | ||
| MT | ||
| NE | ||
| NV | ||
| NH | ||
| NJ | ||
| NM | ||
| NY | ||
| NC | ||
| ND | ||
| OH | ||
| OK | ||
| OR | ||
| PA | ||
| RI | ||
| SC | ||
| SD | ||
| TN | ||
| TX | ||
| UT | ||
| VT | ||
| VA | ||
| WA | ||
| WV | ||
| WI | ||
| WY | ||
|
|
||
|
|
||
| AL FL | ||
| AL GA | ||
| AL MS | ||
| AL TN | ||
| AR LA | ||
| AR MO | ||
| AR MS | ||
| AR OK | ||
| AR TN | ||
| AR TX | ||
| AZ CA | ||
| AZ NM | ||
| AZ NV | ||
| AZ UT | ||
| CA NV | ||
| CA OR | ||
| CO KS | ||
| CO NE | ||
| CO NM | ||
| CO OK | ||
| CO UT | ||
| CO WY | ||
| CT MA | ||
| CT NY | ||
| CT RI | ||
| DC MD | ||
| DC VA | ||
| DE MD | ||
| DE NJ | ||
| DE PA | ||
| FL GA | ||
| GA NC | ||
| GA SC | ||
| GA TN | ||
| IA IL | ||
| IA MN | ||
| IA MO | ||
| IA NE | ||
| IA SD | ||
| IA WI | ||
| ID MT | ||
| ID NV | ||
| ID OR | ||
| ID UT | ||
| ID WA | ||
| ID WY | ||
| IL IN | ||
| IL KY | ||
| IL MO | ||
| IL WI | ||
| IN KY | ||
| IN MI | ||
| IN OH | ||
| KS MO | ||
| KS NE | ||
| KS OK | ||
| KY MO | ||
| KY OH | ||
| KY TN | ||
| KY VA | ||
| KY WV | ||
| LA MS | ||
| LA TX | ||
| MA NH | ||
| MA NY | ||
| MA RI | ||
| MA VT | ||
| MD PA | ||
| MD VA | ||
| MD WV | ||
| ME NH | ||
| MI OH | ||
| MI WI | ||
| MN ND | ||
| MN SD | ||
| MN WI | ||
| MO NE | ||
| MO OK | ||
| MO TN | ||
| MS TN | ||
| MT ND | ||
| MT SD | ||
| MT WY | ||
| NC SC | ||
| NC TN | ||
| NC VA | ||
| ND SD | ||
| NE SD | ||
| NE WY | ||
| NH VT | ||
| NJ NY | ||
| NJ PA | ||
| NM OK | ||
| NM TX | ||
| NV OR | ||
| NV UT | ||
| NY PA | ||
| NY VT | ||
| OH PA | ||
| OH WV | ||
| OK TX | ||
| OR WA | ||
| PA WV | ||
| SD WY | ||
| TN VA | ||
| UT WY | ||
| VA WV |
| @@ -0,0 +1,6 @@ | ||
| # topo sort - without depth-first search | ||
| topocycle: graph.c dfs.c topocycletest.c | ||
| clang -g -O0 -o topocycletest graph.c topocycletest.c | ||
|
|
||
| testtopocycle: topocycle | ||
| ./topocycletest |
| @@ -0,0 +1,76 @@ | ||
| /* Simple interface for weighted directed graphs. | ||
| The vertices are numbered 0 .. n-1 for some fixed n. | ||
| Edges have nonnegative weights. | ||
| The two standard graph representations are supported. | ||
| Function cloneGraph() can be used to convert between | ||
| representations. | ||
| Precondition: all functions except makeGraph assume their | ||
| Graph argument is non-null. | ||
| */ | ||
|
|
||
| #define MATRIX 0 | ||
| #define LIST 1 | ||
|
|
||
| #define OK 0 | ||
| #define ERROR 1 | ||
|
|
||
| struct graph; | ||
| typedef struct graph* Graph; | ||
|
|
||
| /* Make an empty graph with n vertices, using either adjacency matrix | ||
| or adjacency lists depending on whether rep==MATRIX or rep==LIST. | ||
| Precondition: n>=1 and rep is MATRIX or LIST. | ||
| */ | ||
| Graph makeGraph(int n, int rep); | ||
|
|
||
| /* make a copy of g, but using the representation | ||
| specified by rep (which is assumed to be MATRIX or LIST) | ||
| */ | ||
| Graph cloneGraph(Graph G, int rep); | ||
|
|
||
| /* free the graph object and all its resources. | ||
| Postcondition: g is no longer a valid pointer. | ||
| Alert: the caller should set their variable to null. | ||
| */ | ||
| void disposeGraph(Graph G); | ||
|
|
||
| /* number of vertices */ | ||
| int numVerts(Graph G); | ||
|
|
||
| /* add edge from source to target with weight w, and return | ||
| OK, if source and target are valid vertex numbers and | ||
| there was no edge from source to target initially. | ||
| Otherwise, make no change and return ERROR. | ||
| */ | ||
| int addEdge(Graph G, int source, int target, float w); | ||
|
|
||
| /* delete edge from source to target, and return | ||
| OK, if there was an edge from source. | ||
| Otherwise, make no change and return ERROR. | ||
| */ | ||
| int delEdge(Graph G, int source, int target); | ||
|
|
||
| /* return weight of the edge from source to target, | ||
| if there is one; otherwise return INFINITY. | ||
| Return -1.0 if source or target are out of range. | ||
| */ | ||
| float edge(Graph G, int source, int target); | ||
|
|
||
| /* a freshly allocated array with the successor | ||
| vertices of source, if any, followed by an entry with -1 | ||
| to indicate end of sequence. | ||
| Precondition: source is in range. | ||
| */ | ||
| int* successors(Graph G, int source); | ||
|
|
||
| /* a freshly allocated array with the predecessor | ||
| vertices of target, if any, followed by an entry with -1 | ||
| to indicate end of sequence. | ||
| Precondition: target is in range. | ||
| */ | ||
| int* predecessors(Graph G, int target); | ||
|
|
| @@ -0,0 +1,128 @@ | ||
| #include <stdlib.h> | ||
| #include <stdio.h> | ||
| #include <string.h> | ||
| #include <assert.h> | ||
| #include "graph.h" | ||
|
|
||
|
|
||
| /*************************************************************** | ||
| * Topological sort using the 'delete sources' method, | ||
| * not DFS. That is: repeatedly find and then delete a vertex | ||
| * that is a 'source', i.e., has no predecessors. | ||
| * Assumes the file is valid, acyclic graph. | ||
| ****************************************************************/ | ||
|
|
||
| /**************************************************************** | ||
| Read graph from file, with strings for vertex names. | ||
| File format is assumed to be: | ||
| - first line is a nonnegative integer N in decimal | ||
| - following N lines each have one vertex name (a sequence of | ||
| non-blank chars, at most MAX_NAMELEN of them). | ||
| - remainder of the file can have blank lines; non-blank lines | ||
| have either two or three non-blank elements, in the form: | ||
| S T W | ||
| where S and T are vertex names and W is a decimal weight. | ||
| If omitted, the weight is interpreted as DEFAULT_WEIGHT. | ||
| ******************************************************************/ | ||
| #define DEFAULT_WEIGHT 1.0 | ||
| #define MAX_NAMELEN 32 /* max length of a vertex name */ | ||
|
|
||
|
|
||
| /* A graph together with names for its vertices. | ||
| */ | ||
| struct graphinfo { | ||
| Graph graph; | ||
| char **vertnames; //array of numVerts vertex names | ||
| }; | ||
| typedef struct graphinfo* GraphInfo; | ||
|
|
||
|
|
||
| /* Index of a given vertex name, or -1 if not found. */ | ||
| int indexOf(GraphInfo gi, char* name) { | ||
| int i = 0; | ||
| int n = numVerts(gi->graph); | ||
| while ( i < n && strcmp(gi->vertnames[i], name) ) | ||
| i++; | ||
| if (i < n) | ||
| return i; | ||
| else return -1; | ||
| } | ||
|
|
||
|
|
||
| /* attempt to open a file; halt execution if fail */ | ||
| FILE* tryOpen(char* path, char* mode) { | ||
| FILE* file = fopen(path, mode); | ||
| if (file == NULL) { | ||
| fprintf(stderr, "tryOpen fatal error: could not open file %s\n", path); | ||
| exit(1); | ||
| } | ||
| return file; | ||
| } | ||
|
|
||
| /* Read a graph from a text file, using the given representation. | ||
| Assumes path is a null-terminated string that is valid file path. | ||
| Assumes file has the specified format. | ||
| */ | ||
| GraphInfo readGraph(char* path, int repType) { | ||
|
|
||
| /* open file, get number of vertices, allocate and initialize GraphInfo */ | ||
| FILE* infile = tryOpen(path, "r"); | ||
| int numVerts; | ||
| fscanf(infile, "%i", &numVerts); | ||
|
|
||
| GraphInfo gi = (GraphInfo) malloc(sizeof(struct graphinfo)); | ||
| gi->graph = makeGraph(numVerts, repType); | ||
| char **vertnames = (char**) malloc(numVerts * sizeof(char *)); | ||
| gi->vertnames = vertnames; | ||
|
|
||
| /* get vertex names */ | ||
| char source[MAX_NAMELEN + 1]; | ||
| int i = 0; | ||
| while( i < numVerts && fscanf(infile, "%s", source) != EOF ) { | ||
| // read, determine length, and make copy in the heap | ||
| vertnames[i] = (char *) malloc(strlen(source)); | ||
| strcpy(vertnames[i], source); | ||
| i++; | ||
| } | ||
|
|
||
| /* get the edges */ | ||
| char target[MAX_NAMELEN + 1]; | ||
| float weight; | ||
| int result = fscanf(infile, "%s %s %f", source, target, &weight); | ||
| while( result != EOF) { | ||
| if (result >= 2 ) { // read at least two items | ||
| if (result == 2) // weight not included | ||
| weight = DEFAULT_WEIGHT; | ||
| addEdge(gi->graph, indexOf(gi, source), indexOf(gi, target), weight); | ||
| result = fscanf(infile, "%s %s %f", source, target, &weight); | ||
| } else { | ||
| fprintf(stderr, "readGraph fatal error: unexpected file format in %s\n", path); | ||
| exit(1); | ||
| } | ||
| } | ||
|
|
||
| /* clean up and return */ | ||
| fclose(infile); | ||
| return gi; | ||
| } | ||
|
|
||
|
|
||
|
|
||
| void toposort2(char * filepath) { | ||
| GraphInfo gi = readGraph(filepath, MATRIX); // DN's implementation supports precessors only for MATRIX | ||
| Graph g = gi->graph; | ||
| int numV = numVerts(g); | ||
|
|
||
|
|
||
| /* YOUR CODE GOES HERE */ | ||
|
|
||
|
|
||
| } | ||
|
|
||
|
|
||
| int main() { | ||
| toposort2("LevitinTopo.txt"); | ||
| toposort2("prereqs.txt"); | ||
| return 0; | ||
| } |
| @@ -0,0 +1,7 @@ | ||
| /* Assume the file exists and has the format described in dfstest.c. | ||
| Read the file and run depth-first search. | ||
| Based on the DFS info, check whether the graph has a cycle. | ||
| If so, print the vertices of a cycle. (Just one cycle, even if there are several.) | ||
| If not, print all the vertices, topologically sorted. | ||
| */ | ||
| void topocycle(char * filepath); |