h3_vertexGraph.c

/*
 * Copyright 2017-2018, 2020-2021 Uber Technologies, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/** @file vertexGraph.c
 * @brief   Data structure for storing a graph of vertices
 */

#include "h3_vertexGraph.h"

#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#include "h3_alloc.h"
#include "h3_latLng.h"

/**
 * Initialize a new VertexGraph
 * @param graph       Graph to initialize
 * @param  numBuckets Number of buckets to include in the graph
 * @param  res        Resolution of the hexagons whose vertices we're storing
 */
void initVertexGraph(VertexGraph *graph, int numBuckets, int res) {
    if (numBuckets > 0) {
        graph->buckets = H3_MEMORY(calloc)(numBuckets, sizeof(VertexNode *));
        assert(graph->buckets != NULL);
    } else {
        graph->buckets = NULL;
    }
    graph->numBuckets = numBuckets;
    graph->size = 0;
    graph->res = res;
}

/**
 * Destroy a VertexGraph's sub-objects, freeing their memory. The caller is
 * responsible for freeing memory allocated to the VertexGraph struct itself.
 * @param graph Graph to destroy
 */
void destroyVertexGraph(VertexGraph *graph) {
    VertexNode *node;
    while ((node = firstVertexNode(graph)) != NULL) {
        removeVertexNode(graph, node);
    }
    H3_MEMORY(free)(graph->buckets);
}

/**
 * Get an integer hash for a lat/lng point, at a precision determined
 * by the current hexagon resolution.
 * TODO: Light testing suggests this might not be sufficient at resolutions
 * finer than 10. Design a better hash function if performance and collisions
 * seem to be an issue here.
 * @param  vertex     Lat/lng vertex to hash
 * @param  res        Resolution of the hexagon the vertex belongs to
 * @param  numBuckets Number of buckets in the graph
 * @return            Integer hash
 */
uint32_t _hashVertex(const LatLng *vertex, int res, int numBuckets) {
    // Simple hash: Take the sum of the lat and lng with a precision level
    // determined by the resolution, converted to int, modulo bucket count.
    return (uint32_t)fmod(fabs((vertex->lat + vertex->lng) * pow(10, 15 - res)),
                          numBuckets);
}

void _initVertexNode(VertexNode *node, const LatLng *fromVtx,
                     const LatLng *toVtx) {
    node->from = *fromVtx;
    node->to = *toVtx;
    node->next = NULL;
}

/**
 * Add a edge to the graph
 * @param graph   Graph to add node to
 * @param fromVtx Start vertex
 * @param toVtx   End vertex
 * @return        Pointer to the new node
 */
VertexNode *addVertexNode(VertexGraph *graph, const LatLng *fromVtx,
                          const LatLng *toVtx) {
    // Make the new node
    VertexNode *node = H3_MEMORY(malloc)(sizeof(VertexNode));
    assert(node != NULL);
    _initVertexNode(node, fromVtx, toVtx);
    // Determine location
    uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);
    // Check whether there's an existing node in that spot
    VertexNode *currentNode = graph->buckets[index];
    if (currentNode == NULL) {
        // Set bucket to the new node
        graph->buckets[index] = node;
    } else {
        // Find the end of the list
        do {
            // Check the the edge we're adding doesn't already exist
            if (geoAlmostEqual(&currentNode->from, fromVtx) &&
                geoAlmostEqual(&currentNode->to, toVtx)) {
                // already exists, bail
                H3_MEMORY(free)(node);
                return currentNode;
            }
            if (currentNode->next != NULL) {
                currentNode = currentNode->next;
            }
        } while (currentNode->next != NULL);
        // Add the new node to the end of the list
        currentNode->next = node;
    }
    graph->size++;
    return node;
}

/**
 * Remove a node from the graph. The input node will be freed, and should
 * not be used after removal.
 * @param graph Graph to mutate
 * @param node  Node to remove
 * @return      0 on success, 1 on failure (node not found)
 */
int removeVertexNode(VertexGraph *graph, VertexNode *node) {
    // Determine location
    uint32_t index = _hashVertex(&node->from, graph->res, graph->numBuckets);
    VertexNode *currentNode = graph->buckets[index];
    int found = 0;
    if (currentNode != NULL) {
        if (currentNode == node) {
            graph->buckets[index] = node->next;
            found = 1;
        }
        // Look through the list
        while (!found && currentNode->next != NULL) {
            if (currentNode->next == node) {
                // splice the node out
                currentNode->next = node->next;
                found = 1;
            }
            currentNode = currentNode->next;
        }
    }
    if (found) {
        H3_MEMORY(free)(node);
        graph->size--;
        return 0;
    }
    // Failed to find the node
    return 1;
}

/**
 * Find the Vertex node for a given edge, if it exists
 * @param  graph   Graph to look in
 * @param  fromVtx Start vertex
 * @param  toVtx   End vertex, or NULL if we don't care
 * @return         Pointer to the vertex node, if found
 */
VertexNode *findNodeForEdge(const VertexGraph *graph, const LatLng *fromVtx,
                            const LatLng *toVtx) {
    // Determine location
    uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);
    // Check whether there's an existing node in that spot
    VertexNode *node = graph->buckets[index];
    if (node != NULL) {
        // Look through the list and see if we find the edge
        do {
            if (geoAlmostEqual(&node->from, fromVtx) &&
                (toVtx == NULL || geoAlmostEqual(&node->to, toVtx))) {
                return node;
            }
            node = node->next;
        } while (node != NULL);
    }
    // Iteration lookup fail
    return NULL;
}

/**
 * Find a Vertex node starting at the given vertex
 * @param  graph   Graph to look in
 * @param  fromVtx Start vertex
 * @return         Pointer to the vertex node, if found
 */
VertexNode *findNodeForVertex(const VertexGraph *graph, const LatLng *fromVtx) {
    return findNodeForEdge(graph, fromVtx, NULL);
}

/**
 * Get the next vertex node in the graph.
 * @param  graph Graph to iterate
 * @return       Vertex node, or NULL if at the end
 */
VertexNode *firstVertexNode(const VertexGraph *graph) {
    VertexNode *node = NULL;
    int currentIndex = 0;
    while (node == NULL) {
        if (currentIndex < graph->numBuckets) {
            // find the first node in the next bucket
            node = graph->buckets[currentIndex];
        } else {
            // end of iteration
            return NULL;
        }
        currentIndex++;
    }
    return node;
}