bfs.c

Go to the documentation of this file.

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
 
/******************************************
 
        Breadth First Search
        Computes single-source distances for
        unweighted graphs
 
******************************************/
 
#include <neatogen/bfs.h>
#include <stdbool.h>
#include <stdlib.h>
#include <util/alloc.h>
 
void bfs(int vertex, vtx_data *graph, int n, DistType *dist)
 /* compute vector 'dist' of distances of all nodes from 'vertex' */
{
    int closestVertex, neighbor;
    DistType closestDist = INT_MAX;
 
    /* initial distances with edge weights: */
    for (int i = 0; i < n; i++)
        dist[i] = -1;
    dist[vertex] = 0;
 
    Queue Q;
    mkQueue(&Q, n);
    initQueue(&Q, vertex);
 
    if (graph[0].ewgts == NULL) {
        while (deQueue(&Q, &closestVertex)) {
            closestDist = dist[closestVertex];
            for (size_t i = 1; i < graph[closestVertex].nedges; i++) {
                neighbor = graph[closestVertex].edges[i];
                if (dist[neighbor] < -0.5) {    /* first time to reach neighbor */
                    dist[neighbor] = closestDist + 1;
                    enQueue(&Q, neighbor);
                }
            }
        }
    } else {
        while (deQueue(&Q, &closestVertex)) {
            closestDist = dist[closestVertex];
            for (size_t i = 1; i < graph[closestVertex].nedges; i++) {
                neighbor = graph[closestVertex].edges[i];
                if (dist[neighbor] < -0.5) {    /* first time to reach neighbor */
                    dist[neighbor] =
                        closestDist +
                        (DistType) graph[closestVertex].ewgts[i];
                    enQueue(&Q, neighbor);
                }
            }
        }
    }
 
    /* For dealing with disconnected graphs: */
    for (int i = 0; i < n; i++)
        if (dist[i] < -0.5)     /* 'i' is not connected to 'vertex' */
            dist[i] = closestDist + 10;
 
    freeQueue(&Q);
}
 
void mkQueue(Queue * qp, int size)
{
    qp->data = gv_calloc(size, sizeof(int));
    qp->queueSize = size;
    qp->start = qp->end = 0;
}
 
void freeQueue(Queue * qp)
{
    free(qp->data);
}
 
void initQueue(Queue * qp, int startVertex)
{
    qp->data[0] = startVertex;
    qp->start = 0;
    qp->end = 1;
}
 
bool deQueue(Queue * qp, int *vertex)
{
    if (qp->start >= qp->end)
        return false;           /* underflow */
    *vertex = qp->data[qp->start++];
    return true;
}
 
bool enQueue(Queue * qp, int vertex)
{
    if (qp->end >= qp->queueSize)
        return false;           /* overflow */
    qp->data[qp->end++] = vertex;
    return true;
}