#include <stdlib.h>
#include <stdio.h>
#define PONDERED_GRAPH 1
#define UNPONDERED_GRAPH 0
#define INT_MAX 2147483647
typedef struct
{
///graph vertex information
int id; //the id of the node
int distance; //distance from a source
int discoverTime; //the discovery time in a search algorythm
int finishTime; //the finish time in a search algorythm
int visited; //1 if the node was visited
}VERTEX;
typedef struct
{
///contains the information about the adjacency list of a vertex
///contains the adjacent vertices as a list
VERTEX* mainVertex; //the vertex for which we construct the adjacency list
int elemCount; //the number of adjacent vertices
int capacity; //the capacity of the vertex list and weight list
VERTEX** vertexList; //pointer to the list of vertex pointers
int* weight; //the weight from mainVertex to actual vertex
}ADJACENCY_LIST;
typedef struct
{
//graph information
int edgeCount; //the number of nodes
int vertexCount; //the number of vertices
ADJACENCY_LIST** adjList; //the list of edges
}GRAPH;
#define ADJ_LIST_RESIZE_FACTOR 10
/////////////////////// VERTEX FUNCTIONS ///////////////////////
VERTEX* vertexCreate(int id)
{
///creates a vertex
///params - node id
///returns the vertex pointer
VERTEX* newVertex = (VERTEX*)malloc(sizeof(VERTEX));
if (newVertex == NULL) //allocation error
return NULL;
newVertex->id = id;
newVertex->distance = INT_MAX; //set the attributes
newVertex->discoverTime = 0;
newVertex->finishTime = 0;
newVertex->visited = 0;
return newVertex; //return the pointer
}
int vertexDestroy(VERTEX* vertex)
{
///destroys a vertex
///frees the memory ocupied by the structure
free(vertex);
return 0;
}
/////////////////////// ADJACENCY LIST FUNCTIONS ///////////////////////
ADJACENCY_LIST* adjListCreate(VERTEX* mainVertex)
{
///creates an empty adjacency list
///params -valid vertex pointer
ADJACENCY_LIST* newAdjList = (ADJACENCY_LIST*)malloc(sizeof(ADJACENCY_LIST));
if (newAdjList == NULL) //allocation error
return NULL;
newAdjList->capacity = 0;
newAdjList->elemCount = 0;
newAdjList->vertexList = NULL;
newAdjList->mainVertex = mainVertex;
newAdjList->weight = NULL;
return newAdjList;
}
int adjListDestroy(ADJACENCY_LIST* adjList)
{
///destroys an adjacency list
///frees the memory allocated by the structure
if (adjList == NULL)
return -1;
free(adjList->weight); //frees the weight list
free(adjList->vertexList);
vertexDestroy(adjList->mainVertex);
free(adjList);
return 0;
}
int adjListResize(ADJACENCY_LIST* adjList)
{
///resizez the weight list and the vertex pointers list if the capacity is equal to the elemCount
///initializez it to 2 or doubles the capacity
///params - valid adjacency list pointer
///returns - 0 if succes
/// - -1 if allocation error
if (adjList->elemCount < adjList->capacity) //no need of resize
return 0;
int newSize;
if (adjList->capacity == 0)
newSize = 2000; //determines te new size
else if (adjList->capacity == adjList->elemCount)
newSize = adjList->capacity * ADJ_LIST_RESIZE_FACTOR;
adjList->weight = (int*)realloc(adjList->weight, newSize * sizeof(int));
adjList->vertexList = (VERTEX**)realloc(adjList->vertexList, newSize * sizeof(VERTEX*));
adjList->capacity = newSize;
if (adjList->vertexList == NULL || adjList->weight == NULL)
return -1;
return 0;
}
/////////////////////// GRAPH FUNCTIONS ///////////////////////
VERTEX* graphGetNthVertex(GRAPH* graph, int n)
{
///returns pointer to the Nth vertex or NULL if N is greater than vertex count
///params - valid graph pointer
/// - n , integer from [1, graphVertexCount]
///return - pointer to vertex if N is a valid vertex number
/// - NULL otherwise
if (n > graph->vertexCount || n < 1 || graph->adjList == NULL)
return NULL; //does not exist
return graph->adjList[n - 1]->mainVertex; //returns the pointer
}
int graphCreate(GRAPH** graph, int vertexCount, int edgeCount)
{
///creates a new empty graph and assigns it to the param double pointer to graph
///params - valid pointer to graph pointer
/// - the vertex count
/// - the edge count
///return - 0 if succes
/// - -1 if allocation error
GRAPH* newGraph = (GRAPH*)malloc(sizeof(GRAPH));
if (newGraph == NULL) //allocation error
return -1;
newGraph->edgeCount = edgeCount;
newGraph->vertexCount = vertexCount; //sets the atributes
newGraph->adjList = (ADJACENCY_LIST**)malloc(vertexCount * sizeof(ADJACENCY_LIST*)); //creates the list of adj lists
if (newGraph->adjList == NULL)
{
free(newGraph); //frees the memory allocated so far
return -1; //allocation error
}
int i = 0;
for (i = 0; i < newGraph->vertexCount; i++)
{
newGraph->adjList[i] = adjListCreate(vertexCreate(i + 1)); //inits the adjLists with main vertices with ordered id's
if (graphGetNthVertex(newGraph, i + 1) == NULL) //allocation error for the crt node
{
int j;
for (j = 0; j < i; j++)
free(graphGetNthVertex(newGraph, j + 1)); //clean the memory previously allocated
free(newGraph);
return -1;
}
}
*graph = newGraph; //if succes, set the double graph pointer to te newGraph pointer
return 0;
}
int graphDestroy(GRAPH* graph)
{
///destroys the graph and all the subcomponents
///params - valid graph pointer
///return - 0 if succes
/// - negative if error
if (graph == NULL)
return 0;
int i = 0;
for (i = 0; i < graph->vertexCount; i++)
{
int adjListDestroyStatus = adjListDestroy(graph->adjList[i]); //destroy the adjacency list
}
free(graph->adjList);
free(graph);
return 0;
}
int graphAddEdge(GRAPH* graph, VERTEX* v1, VERTEX* v2, int weight)
{
///adds the edge between two vertices to the graph
///adds v2 to the adjList of v1; if this list does not exist, creates one;
///if the list of v1 is full, resizes it
///params - valid graph pointer
/// - two valid vertex pointers
/// - weight of v1 ~-> v2 edge
///return - 0 if succes
/// - negative if error
if (v1 == NULL || v2 == NULL || graph == NULL)
return -1;
ADJACENCY_LIST* crtAdjList = graph->adjList[(v1->id) - 1];
if (crtAdjList == NULL) //if it does not exist
{
graph->adjList[v1->id] = adjListCreate(v1); //creates a new list
}
if (crtAdjList->elemCount == crtAdjList->capacity) //if the list is full or null, resizes it
adjListResize(crtAdjList);
crtAdjList->vertexList[crtAdjList->elemCount] = v2;
crtAdjList->weight[crtAdjList->elemCount] = weight; //adds the node and increments the
crtAdjList->elemCount += 1;
return 0;
}
int graphReadFromFileWWeight(GRAPH* graphPtr, char* fileName, int vertexCount, int edgeCount)
{
///reads the graph information from file; pondered graph
///the file contains
///params - valid pointer to graph pointer
/// - valid string pointer to the filename
/// - positive vertex count
/// - positive edgeCount
///return - 0 if succes
/// - negative if error
if (graphPtr == NULL || fileName == NULL) //invalid parameters
return -1;
FILE* inFile = NULL;
inFile = fopen(fileName, "r");
if (inFile == NULL)
return -1;
int aux;
fscanf(inFile, "%d %d %d", &aux, &aux, &aux);
GRAPH* graph = graphPtr; //extracts the graph structure pointer
int i = 0;
for (i = 0; i < graph->edgeCount; i++) //reads the data for each edge
{
int node1Id = 0, node2Id = 0, weight = 0; //the read data
VERTEX* v1;
VERTEX* v2; //the vertices pointers
fscanf(inFile, "%d %d %d", &node1Id, &node2Id, &weight); //read the data
v1 = graphGetNthVertex(graph, node1Id);
v2 = graphGetNthVertex(graph, node2Id);
graphAddEdge(graph, v1, v2, weight);
}
fclose(inFile);
return 0;
}
int graphReadFromFileWoWeight(GRAPH* graphPtr, char* fileName, int vertexCount, int edgeCount)
{
///reads the graph information from file; unpondered graph
///the file contains
///params - valid pointer to graph pointer
/// - valid string pointer to the filename
/// - positive vertex count
/// - positive edgeCount
///return - 0 if succes
/// - negative if error
if (graphPtr == NULL || fileName == NULL) //invalid parameters
return -1;
FILE* inFile = NULL;
inFile = fopen(fileName, "r");
if (inFile == NULL)
return -1;
int aux;
fscanf(inFile, "%d %d %d", &aux, &aux, &aux);
GRAPH* graph = graphPtr; //extracts the graph structure pointer
int i = 0;
for (i = 0; i < graph->edgeCount; i++) //reads the data for each edge
{
int node1Id = 0, node2Id = 0; //the read data
VERTEX* v1;
VERTEX* v2; //the vertices pointers
fscanf(inFile, "%d %d", &node1Id, &node2Id); //read the data
v1 = graphGetNthVertex(graph, node1Id);
v2 = graphGetNthVertex(graph, node2Id);
graphAddEdge(graph, v1, v2, 1);
}
fclose(inFile);
return 0;
}
int graphReadFromFile(GRAPH* graphPtr, char* fileName, int vertexCount, int edgeCount, int graphType)
{
///reads the graph information from file
///calls the function that readts this type of graph
if (graphType == PONDERED_GRAPH)
return graphReadFromFileWWeight(graphPtr, fileName, vertexCount, edgeCount);
else if (graphType == UNPONDERED_GRAPH)
return graphReadFromFileWoWeight(graphPtr, fileName, vertexCount, edgeCount);
}
/////////////////////// UTILITIES ///////////////////////
int** graphGetAdjMatrix(GRAPH* graph)
{
///returns the matrix of adjacency of the graph
///params - valid graph pointer
///returns - pointer to adjMatrix of dimension vertexCount * vertexCount
/// - NULL if error
///for the unadjacent nodes the distance is INT_MAX
if (graph == NULL) //invalid params
return NULL;
int** adjMatrix = (int**)malloc(graph->vertexCount * sizeof(int*)); //alloocates the list pointers
if (adjMatrix == NULL)
return NULL;
int i, j;
for (i = 0; i < graph->vertexCount; i++)
{
adjMatrix[i] = (int*)malloc(graph->vertexCount * sizeof(int)); //alocatesthe matrix rows
if (adjMatrix[i] == NULL)
{
int j;
for (j = 0; j < i; j++)
free(adjMatrix[j]);
free(adjMatrix);
return NULL;
}
}
for (i = 0; i < graph->vertexCount; i++)
{
ADJACENCY_LIST* crtList = graph->adjList[i];
VERTEX** adjVertices = crtList->vertexList;
for (j = 0; j < graph->vertexCount; j++)
adjMatrix[i][j] = INT_MAX;
adjMatrix[i][i] = 0;
for (j = 0; j < crtList->elemCount; j++)
adjMatrix[i][adjVertices[j]->id - 1] = crtList->weight[j]; //sets the weight in the matrix
}
return adjMatrix; //return the result pointer
}
void adjMatrixDestroy(int** adjMatrix, int lines)
{
///destroys the adjacency matrix
///frees the memory for the matrix
///params - valid adjMatrix pointer
if (adjMatrix == NULL)
return;
int i;
for (i = 0; i < lines; i++)
{
int* crtPointer = adjMatrix[i]; //frees every line
free(crtPointer);
}
free(adjMatrix); //frees the matrix double pointer
}
VERTEX** graphGetAdjNodes(GRAPH* graph, VERTEX* vertex)
{
///returns a list of adjacent VERTEX pointers
///params - valid graph pointer
/// - valid vertex pointer
///return - list of pointer to vertex pointers
if (graph == NULL || vertex == NULL)
return NULL;
int vertexId = vertex->id;
return graph->adjList[vertexId - 1]->vertexList; //returns the existing list
}
typedef struct QUEUE_NODE QUEUE_NODE;
struct QUEUE_NODE
{
VERTEX* vertex;
QUEUE_NODE* next;
};
typedef struct
{
QUEUE_NODE* firstNode;
QUEUE_NODE* lastNode;
}QUEUE;
void enqueueVertex(QUEUE* queue, VERTEX* vertex)
{
///adds the vertex to the queue
QUEUE_NODE* newNode = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE));
newNode->next = NULL;
newNode->vertex = vertex;
if (queue->firstNode == NULL) //empty queue
{
queue->firstNode = newNode;
queue->lastNode = newNode;
}
else
{
queue->lastNode->next = newNode;
queue->lastNode = newNode;
}
}
VERTEX* dequeueVertex(QUEUE* queue)
{
//dequeues the first vertex
QUEUE_NODE* node = queue->firstNode;
if (node == NULL)
return NULL;
else
{
queue->firstNode = queue->firstNode->next; //changes the first node
VERTEX* vertex = node->vertex; //extracts the vertex
if (node->next == NULL)
{
queue->firstNode = NULL; //the only node in the queue
queue->lastNode = NULL;
}
free(node); //free the node
return vertex;
}
}
void BFS(GRAPH* graph, VERTEX* sourceVertex, FILE* outFile)
{
///runs DFS on the grap and writes the output in the file transmited as a pointer
///params - valid graph pointer
/// - valid source vertex pointer
/// - valid file pointer
if (graph == NULL || sourceVertex == NULL || outFile == NULL)
return;
QUEUE* queue = (QUEUE*)calloc(1, sizeof(QUEUE)); //creates a queue
enqueueVertex(queue, sourceVertex); //adds the source in the queue
sourceVertex->distance = 0;
sourceVertex->visited = 1;
while (queue->firstNode != NULL) //while not an empty queue
{
VERTEX* crtVertex = queue->firstNode->vertex;
VERTEX** list = graphGetAdjNodes(graph, crtVertex); //gets the list of adjNodes
int i;
for (i = 0; i < graph->adjList[crtVertex->id - 1]->elemCount; i++)
{
VERTEX* adjVertex = list[i];
if (adjVertex->visited == 0) //not visited
{
adjVertex->visited = 1; //mark as visited
adjVertex->distance = crtVertex->distance + graph->adjList[crtVertex->id - 1]->weight[i]; //set the distance
enqueueVertex(queue, adjVertex);
}
else //previously visited
{
if (adjVertex->distance > crtVertex->distance + graph->adjList[crtVertex->id - 1]->weight[i]) //update the distance if necessary
adjVertex->distance = crtVertex->distance + graph->adjList[crtVertex->id - 1]->weight[i];
}
}
dequeueVertex(queue);
}
int i;
for (i = 0; i < graph->vertexCount; i++)
{
int distance = graphGetNthVertex(graph, i + 1)->distance;
if (distance == INT_MAX)
distance = -1;
fprintf(outFile, "%d ", distance);
}
free(queue); //frees the queue
return;
}
int main()
{
GRAPH* graph = NULL;
int vertexCount, edgeCount, sourceNode;
FILE* inFile;
FILE* outFile;
inFile = fopen("bfs.in", "r");
fscanf(inFile, "%d %d %d", &vertexCount, &edgeCount, &sourceNode); //reads the data
fclose(inFile);
graphCreate(&graph, vertexCount, edgeCount); //creates a graph
graphReadFromFile(graph, "bfs.in", vertexCount, edgeCount, UNPONDERED_GRAPH); //reads the data from file
outFile = fopen("bfs.out", "w");
VERTEX* sourceVertex = graphGetNthVertex(graph, sourceNode);
BFS(graph, sourceVertex, outFile);
fclose(outFile);
graphDestroy(graph); //frees the graph
return 0;
}
Mihai Anton MihaiAnton