<commit_before>//
//  main.c
//  route-between-nodes: check is there is a route between two nodes in a given directed graph
//
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define EMPTY_NODE (struct node *) 0
#define ADJ_LIST_END (struct adjListNode *) 0

enum statuses {unvisited, visited, visiting};

// vertex node
struct node {
    int nodeId;
    enum statuses status;

    struct node *next; // for supporting queue
    struct adjListNode *adjList; // holding all the edges/adjacencies
};

// A structure for holding adjacencies (edges) of a vertex node
struct adjListNode {
    int destNode;
    struct adjListNode *next;
};

// helper for creating an adjListNode
struct adjListNode *createAdjNode(int destNodeId) {
    struct adjListNode *newNode = (struct adjListNode *) malloc(sizeof(struct adjListNode));
    newNode->destNode = destNodeId;
    newNode->next = ADJ_LIST_END;

    return newNode;
};
 
// A structure to represent a directed graph. A graph is a list (array of adjacency lists)
struct graph {
    int vertices;
    struct node *nodes;
};

// a queue for BFS
struct queue {
    struct node *head;
    struct node *tail;
};

// create a new graph with number of node = vertices and empty adjacency lists
struct graph *createGraph(int vertices) {
    struct graph *newGraph = (struct graph *) malloc(sizeof(struct graph));

    // create all vertices/nodes for the graph
    newGraph->vertices = vertices;
    newGraph->nodes = (struct node *) malloc(vertices * sizeof(struct node));

    for (int i = 0; i < vertices; i++) {
        struct node *nd = newGraph->nodes;

        (newGraph->nodes + i)->nodeId = i;
        (newGraph->nodes + i)->adjList = ADJ_LIST_END; // by default no adjacencies
    }

    return newGraph;
}

// add new edge to the directed graph g
void addEdge(struct graph *g, int srcNodeId, int dstNodeId) {
    struct adjListNode *newNode = createAdjNode(dstNodeId);
 
    // add the edge to the head of node's adjacency list
    newNode->next = g->nodes[srcNodeId].adjList;
    g->nodes[srcNodeId].adjList = newNode;
}

// printing the graph and all its nodes adjacencies
void printGraph(struct graph *g) {
    for (int i = 0; i < g->vertices; i++) {
        struct node *v = (g->nodes + i);
        struct adjListNode *adj = v->adjList;

        printf("Adjacency list of vertex (node) %i:\n", v->nodeId);
        printf("\thead");
        while(adj != ADJ_LIST_END) {
            printf(" -> %i", adj->destNode);
            adj = adj->next;
        }

        printf("\n");
    }
}

// create a new queue for storing graph's nodes during BFS
struct queue *createQueue(void) {
    struct queue *q = malloc(sizeof(struct queue));
    q->head = EMPTY_NODE;
    q->tail = EMPTY_NODE;

    return q;
}

// add a new node to the queue and update tail and head
void queueAdd(struct queue **q, struct node *n) {
    if ((*q)->tail == EMPTY_NODE) {
        (*q)->head = n;
        (*q)->tail = (*q)->head;
    } else {
        (*q)->tail->next = n;
    }

    n->next = EMPTY_NODE;
}

// remove the first node from the queue and move the head
struct node *removeFirstFromQueue(struct queue **q) {
    if ((*q)->head == EMPTY_NODE) {
        return EMPTY_NODE;
    }

    struct node *n = (*q)->head;
    (*q)->head = (*q)->head->next;

    // set tail to EMPTY_NODE in case of empty queue
    if ((*q)->head == EMPTY_NODE) {
        (*q)->tail = EMPTY_NODE;
    }

    return n;
}

// check if queue is empty
bool isQueueEmpty(struct queue *q) {
    return q->head == EMPTY_NODE;
}

bool searchRoute(struct graph *g, int start, int end) {
    if (start == end) {
        return true;
    }

    // mark all nodes as unvisited
    for (int i = 0; i < g->vertices; i++) {
        g->nodes[i].status = unvisited;
    }

    // put the start node into the queue
    struct queue *q = createQueue();
    queueAdd(&q, &(g->nodes[start]));
    g->nodes[start].status = visiting;

    while(! isQueueEmpty(q)) {
        struct node *root = removeFirstFromQueue(&q);
        if (root != EMPTY_NODE) {
            struct adjListNode *adjacency = root->adjList;

            while (adjacency != ADJ_LIST_END) {
                struct node *child = &(g->nodes[adjacency->destNode]);
                if (child->status == unvisited) {
                    if (child->nodeId == end) {
                        return true;
                    }

                    child->status = visiting;
                    queueAdd(&q, child);
                }

                adjacency = adjacency->next;
            }
        }

        root->status = visited;
    }
<commit_msg>store all adjacency nodes inside nodes themselves as pointers to them<commit_after>//
//  main.c
//  route-between-nodes: check is there is a route between two nodes in a given directed graph
//
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define EMPTY_NODE (struct node *) 0

enum statuses {unvisited, visited, visiting};

// vertex node
struct node {
    int nodeId;
    int edgesCount;
    enum statuses status;

    struct node *next; // for supporting queue
    struct node **edgeNodes; // holding adjacency nodes
};
 
// A structure to represent a directed graph. A graph is a list (array of adjacency lists)
struct graph {
    int vertices;
    struct node *nodes;
};

// a queue for BFS
struct queue {
    struct node *head;
    struct node *tail;
};

// create a new graph with number of node = vertices and empty adjacency lists
struct graph *createGraph(int vertices) {
    struct graph *newGraph = (struct graph *) malloc(sizeof(struct graph));

    // create all vertices/nodes for the graph
    newGraph->vertices = vertices;
    newGraph->nodes = (struct node *) malloc(vertices * sizeof(struct node));

    for (int i = 0; i < vertices; i++) {
        struct node *nd = newGraph->nodes;

        newGraph->nodes[i].nodeId = i;
        newGraph->nodes[i].edgesCount = 0;
        newGraph->nodes[i].edgeNodes = (struct node **) malloc(vertices * sizeof(struct node *)); // by default no adjacencies
        newGraph->nodes[i].next = EMPTY_NODE; // for supporting queue
    }

    return newGraph;
}

// add new edge to the directed graph g
void addEdge(struct graph *g, int srcNodeId, int dstNodeId) {
    struct node *parentNode = &(g->nodes[srcNodeId]);

    parentNode->edgeNodes[parentNode->edgesCount] = &(g->nodes[dstNodeId]);
    parentNode->edgesCount++;
}

// printing the graph and all its nodes adjacencies
void printGraph(struct graph *g) {
    for (int i = 0; i < g->vertices; i++) {
        struct node *v = &(g->nodes[i]);

        printf("Adjacency list of vertex (node) %i:\n", v->nodeId);
        printf("\thead");
        for (int i = 0; i < v->edgesCount; i++) {
            printf(" -> %i", v->edgeNodes[i]->nodeId);
        }

        printf("\n");
    }
}

// create a new queue for storing graph's nodes during BFS
struct queue *createQueue(void) {
    struct queue *q = malloc(sizeof(struct queue));
    q->head = EMPTY_NODE;
    q->tail = EMPTY_NODE;

    return q;
}

// add a new node to the queue and update tail and head
void queueAdd(struct queue **q, struct node *n) {
    if ((*q)->tail == EMPTY_NODE) {
        (*q)->head = n;
        (*q)->tail = (*q)->head;
    } else {
        (*q)->tail->next = n;
    }

    n->next = EMPTY_NODE;
}

// remove the first node from the queue and move the head
struct node *removeFirstFromQueue(struct queue **q) {
    if ((*q)->head == EMPTY_NODE) {
        return EMPTY_NODE;
    }

    struct node *n = (*q)->head;
    (*q)->head = (*q)->head->next;

    // set tail to EMPTY_NODE in case of empty queue
    if ((*q)->head == EMPTY_NODE) {
        (*q)->tail = EMPTY_NODE;
    }

    return n;
}

// check if queue is empty
bool isQueueEmpty(struct queue *q) {
    return q->head == EMPTY_NODE;
}

bool searchRoute(struct graph *g, int start, int end) {
    if (start == end) {
        return true;
    }

    // mark all nodes as unvisited
    for (int i = 0; i < g->vertices; i++) {
        g->nodes[i].status = unvisited;
    }

    // put the start node into the queue
    struct queue *q = createQueue();
    queueAdd(&q, &(g->nodes[start]));
    g->nodes[start].status = visiting;

    while(! isQueueEmpty(q)) {
        struct node *root = removeFirstFromQueue(&q);
        if (root != EMPTY_NODE) {
            for (int i = 0; i < root->edgesCount; i++) {
                struct node *child = root->edgeNodes[i];
                if (child->status == unvisited) {
                    if (child->nodeId == end) {
                        return true;
                    }

                    child->status = visiting;
                    queueAdd(&q, child);
                }
            }
        }

        root->status = visited;
    }

{'fraction_non_alphanumeric': 0.13261117445838083, 'fraction_numerical': 0.0013683010262257698, 'mean_word_length': 2.343881052230271, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 103, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4043652', 'n_tokens_mistral': 2803, 'n_tokens_neox': 2705, 'n_words': 883}