1/*
2 * Copyright 2017-2018 Uber Technologies, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16/** @file vertexGraph.c
17 * @brief Data structure for storing a graph of vertices
18 */
19
20#include "vertexGraph.h"
21#include <assert.h>
22#include <math.h>
23#include <stdint.h>
24#include <stdio.h>
25#include <stdlib.h>
26#include "geoCoord.h"
27
28/**
29 * Initialize a new VertexGraph
30 * @param graph Graph to initialize
31 * @param numBuckets Number of buckets to include in the graph
32 * @param res Resolution of the hexagons whose vertices we're storing
33 */
34void initVertexGraph(VertexGraph* graph, int numBuckets, int res) {
35 if (numBuckets > 0) {
36 graph->buckets = calloc(numBuckets, sizeof(VertexNode*));
37 assert(graph->buckets != NULL);
38 } else {
39 graph->buckets = NULL;
40 }
41 graph->numBuckets = numBuckets;
42 graph->size = 0;
43 graph->res = res;
44}
45
46/**
47 * Destroy a VertexGraph's sub-objects, freeing their memory. The caller is
48 * responsible for freeing memory allocated to the VertexGraph struct itself.
49 * @param graph Graph to destroy
50 */
51void destroyVertexGraph(VertexGraph* graph) {
52 VertexNode* node;
53 while ((node = firstVertexNode(graph)) != NULL) {
54 removeVertexNode(graph, node);
55 }
56 free(graph->buckets);
57}
58
59/**
60 * Get an integer hash for a lat/lon point, at a precision determined
61 * by the current hexagon resolution.
62 * TODO: Light testing suggests this might not be sufficient at resolutions
63 * finer than 10. Design a better hash function if performance and collisions
64 * seem to be an issue here.
65 * @param vertex Lat/lon vertex to hash
66 * @param res Resolution of the hexagon the vertex belongs to
67 * @param numBuckets Number of buckets in the graph
68 * @return Integer hash
69 */
70uint32_t _hashVertex(const GeoCoord* vertex, int res, int numBuckets) {
71 // Simple hash: Take the sum of the lat and lon with a precision level
72 // determined by the resolution, converted to int, modulo bucket count.
73 return (uint32_t)fmod(fabs((vertex->lat + vertex->lon) * pow(10, 15 - res)),
74 numBuckets);
75}
76
77void _initVertexNode(VertexNode* node, const GeoCoord* fromVtx,
78 const GeoCoord* toVtx) {
79 node->from = *fromVtx;
80 node->to = *toVtx;
81 node->next = NULL;
82}
83
84/**
85 * Add a edge to the graph
86 * @param graph Graph to add node to
87 * @param fromVtx Start vertex
88 * @param toVtx End vertex
89 * @return Pointer to the new node
90 */
91VertexNode* addVertexNode(VertexGraph* graph, const GeoCoord* fromVtx,
92 const GeoCoord* toVtx) {
93 // Make the new node
94 VertexNode* node = malloc(sizeof(VertexNode));
95 assert(node != NULL);
96 _initVertexNode(node, fromVtx, toVtx);
97 // Determine location
98 uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);
99 // Check whether there's an existing node in that spot
100 VertexNode* currentNode = graph->buckets[index];
101 if (currentNode == NULL) {
102 // Set bucket to the new node
103 graph->buckets[index] = node;
104 } else {
105 // Find the end of the list
106 do {
107 // Check the the edge we're adding doesn't already exist
108 if (geoAlmostEqual(&currentNode->from, fromVtx) &&
109 geoAlmostEqual(&currentNode->to, toVtx)) {
110 // already exists, bail
111 free(node);
112 return currentNode;
113 }
114 if (currentNode->next != NULL) {
115 currentNode = currentNode->next;
116 }
117 } while (currentNode->next != NULL);
118 // Add the new node to the end of the list
119 currentNode->next = node;
120 }
121 graph->size++;
122 return node;
123}
124
125/**
126 * Remove a node from the graph. The input node will be freed, and should
127 * not be used after removal.
128 * @param graph Graph to mutate
129 * @param node Node to remove
130 * @return 0 on success, 1 on failure (node not found)
131 */
132int removeVertexNode(VertexGraph* graph, VertexNode* node) {
133 // Determine location
134 uint32_t index = _hashVertex(&node->from, graph->res, graph->numBuckets);
135 VertexNode* currentNode = graph->buckets[index];
136 int found = 0;
137 if (currentNode != NULL) {
138 if (currentNode == node) {
139 graph->buckets[index] = node->next;
140 found = 1;
141 }
142 // Look through the list
143 while (!found && currentNode->next != NULL) {
144 if (currentNode->next == node) {
145 // splice the node out
146 currentNode->next = node->next;
147 found = 1;
148 }
149 currentNode = currentNode->next;
150 }
151 }
152 if (found) {
153 free(node);
154 graph->size--;
155 return 0;
156 }
157 // Failed to find the node
158 return 1;
159}
160
161/**
162 * Find the Vertex node for a given edge, if it exists
163 * @param graph Graph to look in
164 * @param fromVtx Start vertex
165 * @param toVtx End vertex, or NULL if we don't care
166 * @return Pointer to the vertex node, if found
167 */
168VertexNode* findNodeForEdge(const VertexGraph* graph, const GeoCoord* fromVtx,
169 const GeoCoord* toVtx) {
170 // Determine location
171 uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);
172 // Check whether there's an existing node in that spot
173 VertexNode* node = graph->buckets[index];
174 if (node != NULL) {
175 // Look through the list and see if we find the edge
176 do {
177 if (geoAlmostEqual(&node->from, fromVtx) &&
178 (toVtx == NULL || geoAlmostEqual(&node->to, toVtx))) {
179 return node;
180 }
181 node = node->next;
182 } while (node != NULL);
183 }
184 // Iteration lookup fail
185 return NULL;
186}
187
188/**
189 * Find a Vertex node starting at the given vertex
190 * @param graph Graph to look in
191 * @param fromVtx Start vertex
192 * @return Pointer to the vertex node, if found
193 */
194VertexNode* findNodeForVertex(const VertexGraph* graph,
195 const GeoCoord* fromVtx) {
196 return findNodeForEdge(graph, fromVtx, NULL);
197}
198
199/**
200 * Get the next vertex node in the graph.
201 * @param graph Graph to iterate
202 * @return Vertex node, or NULL if at the end
203 */
204VertexNode* firstVertexNode(const VertexGraph* graph) {
205 VertexNode* node = NULL;
206 int currentIndex = 0;
207 while (node == NULL) {
208 if (currentIndex < graph->numBuckets) {
209 // find the first node in the next bucket
210 node = graph->buckets[currentIndex];
211 } else {
212 // end of iteration
213 return NULL;
214 }
215 currentIndex++;
216 }
217 return node;
218}
219