-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.c
134 lines (119 loc) · 3.69 KB
/
graph.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
* Our graph implementation.
*
* Author: A. Tafliovich.
*/
#include "graph.h"
/*********************************************************************
** Helper function provided in the starter code
*********************************************************************/
void printEdge(Edge* edge) {
if (edge == NULL)
printf("NULL");
else
printf("(%d -- %d, %d)", edge->fromVertex, edge->toVertex, edge->weight);
}
void printEdgeList(EdgeList* head) {
while (head != NULL) {
printEdge(head->edge);
printf(" --> ");
head = head->next;
}
printf("NULL");
}
void printVertex(Vertex* vertex) {
if (vertex == NULL) {
printf("NULL");
} else {
printf("%d: ", vertex->id);
printEdgeList(vertex->adjList);
}
}
void printGraph(Graph* graph) {
if (graph == NULL) {
printf("NULL");
return;
}
printf("Number of vertices: %d. Number of edges: %d.\n\n", graph->numVertices,
graph->numEdges);
for (int i = 0; i < graph->numVertices; i++) {
printVertex(graph->vertices[i]);
printf("\n");
}
printf("\n");
}
/*********************************************************************
** Required functions
*********************************************************************/
/* Returns a newly created Edge from vertex with ID 'fromVertex' to vertex
* with ID 'toVertex', with weight 'weight'.
*/
Edge* newEdge(int fromVertex, int toVertex, int weight) {
Edge *new = (Edge*)malloc(sizeof(Edge)); //allocate on the heap
if (new == NULL) return NULL; //no space
new->fromVertex = fromVertex; //initialize
new->toVertex = toVertex;
new->weight=weight;
return new; //return
}
/* Returns a newly created EdgeList containing 'edge' and pointing to the next
* EdgeList node 'next'.
*/
EdgeList* newEdgeList(Edge* edge, EdgeList* next) {
EdgeList *new = (EdgeList*)malloc(sizeof(EdgeList)); //allocate on heap
if (new == NULL) return NULL; //no space
new->edge = edge; //initialize
new->next = next;
return new; //return
}
/* Returns a newly created Vertex with ID 'id', value 'value', and adjacency
* list 'adjList'.
* Precondition: 'id' is valid for this vertex
*/
Vertex* newVertex(int id, void* value, EdgeList* adjList) {
Vertex *new = (Vertex*)malloc(sizeof(Vertex)); //allocate on heap
if (new == NULL) return NULL; //no space
new->id = id; //initialize
new->value = value;
new->adjList = adjList;
return new; //return
}
/* Returns a newly created Graph with space for 'numVertices' vertices.
* Precondition: numVertices >= 0
*/
Graph* newGraph(int numVertices) {
Graph *new = (Graph*)malloc(sizeof(Graph)); //allocate on heap
if (new == NULL) return NULL; //no space
new->numEdges = 0; //initialize
new->numVertices = numVertices;
if (numVertices == 0) new->vertices = NULL; //cant calloc block of 0 size
else {
new->vertices = (Vertex**)calloc(numVertices, sizeof(Vertex)); //list of vertices is pointers on heap
}
return new;
}
/* Frees memory allocated for EdgeList starting at 'head'.
*/
void deleteEdgeList(EdgeList* head) {
if (head != NULL) {
EdgeList* temp = head->next; //store next value
free(head->edge);
free(head); //free current
deleteEdgeList(temp); //if next value exists, delete it recursively
}
}
/* Frees memory allocated for 'vertex' including its adjacency list.
*/
void deleteVertex(Vertex* vertex) {
deleteEdgeList(vertex->adjList); //delete the vertex's adjlist
free(vertex); //free vertex
}
/* Frees memory allocated for 'graph'.
*/
void deleteGraph(Graph* graph) {
for (int i=0; i<graph->numVertices; i++) { //for each node (ids go from 0 to numVertices-1)
deleteVertex(graph->vertices[i]); //remove it and its list
}
free(graph->vertices);
free(graph); //free graph
}