Repository navigation
Expand file tree
/
Copy pathgraphalgorithms.h
More file actions
188 lines (175 loc) · 6.97 KB
/
Copy pathgraphalgorithms.h
File metadata and controls
188 lines (175 loc) · 6.97 KB
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#ifndef GRAPHALGORITHMS_JL
#define GRAPHALGORITHMS_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#include "../../DataStructures/NonLinearDataStructures/Graph/GraphMatrix/graphmatrix.h"
#include "../../DataStructures/NonLinearDataStructures/Tree/PriorityQueue/priorityqueue.h"
#include "../../DataStructures/NonLinearDataStructures/Graph/DisjointSet/disjointset.h"
#define GRAPH_INFINITY INT_MAX // The distance to a vertex that can't be reached.
// Define how a weighted edge is structured. Used by Kruskal to sort the edges and to return the tree.
typedef struct{
int from; // The first vertex of the edge.
int to; // The second vertex of the edge.
int weight; // The weight of the edge.
} WeightedEdge;
/********************/
/* DIJKSTRA */
/********************/
// Dijkstra: the shortest distance from a source vertex to every other vertex. The weights must be positive.
// It always takes the closest vertex that is not finished yet from a Priority Queue.
// O(V^2 + E log E): with an adjacency matrix we check V possible neighbours for each vertex.
// distance[v] is GRAPH_INFINITY if v can't be reached; previous[v] is the vertex before v in its shortest path (-1 if none).
// Returns 1 if successful or 0 if the source is invalid or the priority queue is full.
int dijkstra(GraphMatrix *graph, int source, int *distance, int *previous){
if(!isValidVertexMatrix(graph, source)){
return 0;
}
int finished[GRAPH_MATRIX_MAX_VERTICES] = {0};
for(int i = 0; i < graph->vertices; i++){
distance[i] = GRAPH_INFINITY;
previous[i] = -1;
}
PriorityQueue pq;
initPQ(&pq);
distance[source] = 0;
enqueuePQ(&pq, source, 0);
int vertex, currentDistance;
while(dequeuePQ(&pq, &vertex, ¤tDistance)){
// A vertex can be in the queue more than once: we only use its first (shortest) appearance.
if(finished[vertex]){
continue;
}
finished[vertex] = 1;
for(int next = 0; next < graph->vertices; next++){
int weight = graph->matrix[vertex][next];
if(weight != 0 && !finished[next] && currentDistance + weight < distance[next]){
distance[next] = currentDistance + weight;
previous[next] = vertex;
if(!enqueuePQ(&pq, next, distance[next])){
return 0;
}
}
}
}
return 1;
}
// Build the Path from the Source to a Target using the previous array returned by Dijkstra.
// Returns 1 if successful (the path from source to target and its number of vertices) or 0 if the target can't be reached.
int getPathDijkstra(int *previous, int *distance, int target, int *path, int *length){
*length = 0;
if(distance[target] == GRAPH_INFINITY){
return 0;
}
// We follow the previous vertices from the target to the source, and then we reverse the path.
for(int vertex = target; vertex != -1; vertex = previous[vertex]){
path[(*length)++] = vertex;
}
for(int i = 0; i < *length/2; i++){
int temp = path[i];
path[i] = path[*length-1-i];
path[*length-1-i] = temp;
}
return 1;
}
/********************/
/* PRIM */
/********************/
// Prim: the minimum spanning tree (the edges that connect every vertex with the smallest total weight).
// It grows the tree from vertex 0, always adding the cheapest edge that reaches a new vertex. O(V^2).
// parent[v] is the vertex that connects v to the tree (-1 for the root, vertex 0).
// Returns 1 if successful or 0 if the graph is directed or not connected.
int primMST(GraphMatrix *graph, int *parent, int *totalWeight){
if(graph->directed){
return 0;
}
int inTree[GRAPH_MATRIX_MAX_VERTICES] = {0};
int cost[GRAPH_MATRIX_MAX_VERTICES];
for(int i = 0; i < graph->vertices; i++){
cost[i] = GRAPH_INFINITY;
parent[i] = -1;
}
cost[0] = 0;
*totalWeight = 0;
for(int added = 0; added < graph->vertices; added++){
// Choose the cheapest vertex that is not in the tree yet.
int vertex = -1;
for(int i = 0; i < graph->vertices; i++){
if(!inTree[i] && (vertex == -1 || cost[i] < cost[vertex])){
vertex = i;
}
}
if(cost[vertex] == GRAPH_INFINITY){
return 0;
}
inTree[vertex] = 1;
*totalWeight += cost[vertex];
// Update the cost of its neighbours.
for(int next = 0; next < graph->vertices; next++){
int weight = graph->matrix[vertex][next];
if(weight != 0 && !inTree[next] && weight < cost[next]){
cost[next] = weight;
parent[next] = vertex;
}
}
}
return 1;
}
/********************/
/* KRUSKAL */
/********************/
// Compare Two Edges for qsort: by weight, and by vertices when the weights are equal (so the result is always the same).
int compareWeightedEdges(const void *a, const void *b){
const WeightedEdge* x = (const WeightedEdge*)a;
const WeightedEdge* y = (const WeightedEdge*)b;
if(x->weight != y->weight){
return (x->weight > y->weight) - (x->weight < y->weight);
}
if(x->from != y->from){
return (x->from > y->from) - (x->from < y->from);
}
return (x->to > y->to) - (x->to < y->to);
}
// Kruskal: the minimum spanning tree, built by taking the edges from the lightest to the heaviest and
// skipping the ones that would make a cycle (checked with a Disjoint Set). O(E log E).
// Writes the edges of the tree (vertices-1 edges) and their total weight.
// Returns 1 if successful or 0 if the graph is directed or not connected.
int kruskalMST(GraphMatrix *graph, WeightedEdge *tree, int *edgeCount, int *totalWeight){
*edgeCount = 0;
*totalWeight = 0;
if(graph->directed){
return 0;
}
// Collect every edge once (i < j) and sort them by weight with qsort (O(E log E)).
WeightedEdge edges[GRAPH_MATRIX_MAX_VERTICES * GRAPH_MATRIX_MAX_VERTICES / 2];
int total = 0;
for(int i = 0; i < graph->vertices; i++){
for(int j = i+1; j < graph->vertices; j++){
if(graph->matrix[i][j] != 0){
edges[total].from = i;
edges[total].to = j;
edges[total].weight = graph->matrix[i][j];
total++;
}
}
}
qsort(edges, total, sizeof(WeightedEdge), compareWeightedEdges);
DisjointSet ds;
initDisjointSet(&ds, graph->vertices);
for(int i = 0; i < total && *edgeCount < graph->vertices-1; i++){
// If both vertices are already connected, this edge would make a cycle.
if(unionDisjointSet(&ds, edges[i].from, edges[i].to)){
tree[(*edgeCount)++] = edges[i];
*totalWeight += edges[i].weight;
}
}
if(*edgeCount != graph->vertices-1){
return 0;
}
else{
return 1;
}
}
#endif //GRAPHALGORITHMS_JL