Welcome, to the home page of Marko Štajgár

The node structure represents one node of a singly linked list.

Elements:

1. int key - integer value that serves as a identifier key in operations like insert, delete and search
   • It is assumed by the module that key of the given node is unique to the linked-list in which it resides in
2. void* data - void pointer to data that you want to reference and “link” to the given node
3. struct Node* next - pointer to the next node in the linked list chain

Source: linkedList.h

typedef struct Node {
    int key;
    void* data;
    struct Node* next;
} Node;

Example raw usage:

int key = 1;
int data = 42;

Node* node = (Node*) malloc(sizeof(Node));

node->key = key;
node->data = &data;
node->next = NULL;

// Rest of the code

free(node);

<2024-08-23 Pá>

Important: must be called before any other function

When called, a new linked list node is created and allocated and filled with given key and data

Arguments:

1. int key - integer value that serves as an identifier key in operations like insert, delete and search.
2. void* data - void pointer to data that you want to reference and “link” to the given node

Return type:

• Function returns a pointer Node* that points to newly created linked list

Source: linkedList.h

Node* create_linked_list(int key, void* data);

Example usage:

int key = 1;
int data = 42;

Node* list_head = create_linked_list(key, &data);

// Rest of the code

delete_linked_list(&list_head);

<2024-08-23 Pá>

Important: use when no longer needed to avoid memory leaks

When called, given an address of the desired linked list, the function deallocates and frees all nodes from memory and returns an integer exit code.

Arguments:

1. Node** list_head - Pointer to pointer to linked list head that is to be deleted.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, check stderr for more info

Source: linkedList.h

int delete_linked_list(Node** list_head);

Example usage:

int key = 1;
int data = 42;

Node* list_head = create_linked_list(key, &data);

// Rest of the code

delete_linked_list(&list_head);

<2024-08-23 Pá>

Insert’s a node with given key and data pointer at the beginning of the linked list

Arguments:

1. int key - integer value that serves as an identifier key in operations like insert, delete and search.
2. void* data - void pointer to data that you want to reference and “link” to the given node
3. Node** list_head - Pointer to pointer to linked list head of the linked lits that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int insert_at_beginning(int key, void* data, Node** list_head);

Example usage:

int key1 = 1;
int key2 = 2;

int data1 = 42
int data2 = 84;

Node* list_head = create_linked_list(key1, &data1);

insert_at_beginning(key2, &data2, &list_head);

// Rest of the code

delete_linked_list(&list_head);

<2024-08-23 Pá>

Insert’s a node with given key and data pointer at the end of the linked list

Arguments:

1. int key - integer value that serves as an identifier key in operations like insert, delete and search.
2. void* data - void pointer to data that you want to reference and “link” to the given node
3. Node** list_head - Pointer to pointer to linked list head of the linked list that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int insert_at_end(int key, void* data, Node** list_head);

Example usage:

int key1 = 1;
int key2 = 2;

int data1 = 42
int data2 = 84;

Node* list_head = create_linked_list(key1, &data1);

insert_at_end(key2, &data2, &list_head);

// Rest of the code

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and delete a node with given key value

Arguments:

1. int key - integer value that serves as an identifier key in operations like insert, delete and search. Key numbering 0 -> n - 1
2. Node** list_head - Pointer to pointer to linked list head of the linked list that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int delete_node_with_key(int key, void* data, Node** list_head);

Example usage:

int data1 = 42
int data2 = 84;
Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);

delete_node_with_key(1, &list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and add given value to all nodes until the end.

Arguments:

1. int value - integer value that is to be added up to every node key in the linked list.
2. Node* list_head - Pointer to the linked list head of the linked list that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int add_to_all_node_keys(int value, Node* list_head);

Example usage:

int data1 = 42;
int data2 = 84;

Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);

add_to_all_node_keys(5, list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and apply the given transformer function to all node keys until the end.

Arguments:

1. int (*transformer)(int) - function pointer of a transformer function that takes the node key as argument and returns new key value. This function is to be applied to every node key in the linked list.
2. Node* list_head - Pointer to the linked list head of the linked list that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int transform_all_node_keys(int (*transformer)(int), Node* list_head);

Example usage:

int some_transformer(int key);

int data1 = 42;
int data2 = 84;
int data3 = 126;

Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);
insert_at_end(3, &data3, &list_head);

transform_all_node_keys(&some_transformer, list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and return a pointer to a node with given key.

Arguments:

1. int key - integer value that serves as an identifier key of the node that is ot be returned. Key numbering 0 -> n - 1
2. Node* list_head - Pointer to the linked list head of the linked list that is to be modified.

Return type:

• Function returns a Node*, that is a pointer to a Node.

Source: linkedList.h

Node* list_search(int key, Node* list_head);

Example usage:

int data1 = 42;
int data2 = 84;
int data3 = 126;

Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);
insert_at_end(3, &data3, &list_head);

Node* desired_node = list_search(2, list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and return true if a node with given key is found.

Arguments:

1. int key - integer value that serves as an identifier key of the node that is ot be returned. Key numbering 0 -> n - 1
2. Node* list_head - Pointer to the linked list head of the linked list that is to be modified.

Return type:

• Function returns bool value.

Source: linkedList.h

bool list_contains(int key, Node* list_head);

Example usage:

int data1 = 42;
int data2 = 84;
int data3 = 126;

Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);
insert_at_end(3, &data3, &list_head);

bool result = list_contains(2, list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and print content of every node to file with given file descriptor.

Arguments:

1. int file_descriptor - file descriptor of a file that is to be printed into.
2. Node* list_head - Pointer to the linked list head of the linked list that is to be printed.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int list_print_content(int file_descriptor, Node* list_head);

Example usage:

int data1 = 42;
int data2 = 84;
int data3 = 126;

Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);
insert_at_end(3, &data3, &list_head);

// stdout has a file descriptor of 1 by default in every proccess (atleast on nixos)
list_print_content(1, list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Search through the given linked list and print content of every node to stdout.

Arguments:

1. Node* list_head - Pointer to the linked list head of the linked list that is to be printed.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: linkedList.h

int list_print_to_stdout(Node* list_head);

Example usage:

int data1 = 42;
int data2 = 84;
int data3 = 126;

Node* list_head = create_linked_list(1, &data1);

insert_at_end(2, &data2, &list_head);
insert_at_end(3, &data3, &list_head);

list_print_to_stdout(list_head);

delete_linked_list(&list_head);

<2024-08-23 Pá>

Serves as an element that the queue accepts for equeue / dequeue operations

Elements:

1. int key - integer value that serves as a identifier key
2. void* data - void pointer to data that you want to reference and “link” to given QueueElement

Source: queue.h

typedef struct QueueElement {
    int key;
    void* data;
} QueueElement;

Example raw usage:

int new_key = 1;
int new_data = 42;

QueueElement new_element = {
        .key = new_key,
        .data = &new_data
};

// Rest of the code

<2024-08-24 So>

FIFO Queue structure that is implemented using the linked list module

Elements:

1. Node* back - Pointer to Node that is at the back of the queue
2. Node* front - Pointer to Node that is at the front of the queue

Source: queue.h

typedef struct Queue {
    Node* back;
    Node* front;
} Queue;

Example raw usage:

#include "linkedList.h"

int key = 1;
int data = 42;

Node* new_front = create_linked_list(key, &data);
Node* new_back = front;

Queue* queue = (Queue*) malloc(sizeof(Queue));

queue->front = new_front;
queue->back = new_back;

// Rest of the code

delete_linked_list(&front);
free(queue);

<2024-08-24 So>

Important: must be called before any other function

When called, a new Queue is created and allocated.

Arguments: none

Return type:

• returns a pointer Queue* that points to newly created Queue

Source: heap.h

Queue* create_queue();

Example usage:

Queue* new_queue = create_queue();

// Rest of the code

delete_queue(&new_queue);

<2024-08-24 So>

Important: use when no longer needed to avoid memory leaks

When called, Queue on given address will be deallocated and deleted.

Arguments:

1. Queue** queue - Pointer to pointer to the queue that is to be deleted.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, check stderr for more info

Source: queue.h

int delete_queue(Queue** queue);

Example usage:

Queue* new_queue = create_queue();

// Rest of the code

delete_queue(&new_queue);

<2024-08-24 So>

Checks if given Queue is empty.

Arguments:

1. Queue* queue - Pointer to the Queue that is to be checked.

Return type:

• Function returns bool value.

Source: queue.h

bool is_empty(Queue* queue);

Example usage:

Queue* queue = create_queue();

bool result = is_empty(queue);

delete_queue(&queue);

<2024-08-24 So>

Adds given QueueElement to the back of the Queue.

Arguments:

1. QueueElement new_element - QueueElement type value that holds the key and pointer to data that is to be enqueued.
2. Queue** queue - Pointer to pointer to the queue that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: queue.h

int enqueue(QueueElement new_element, Queue** queue);

Example usage:

Queue* queue = create_queue();

int new_key = 1;
int new_data = 2;

QueueElement new_element = {
        .key = new_key,
        .data = &new_data
};

enqueue(new_element, &queue)

// Rest of the code

delete_queue(&queue);

<2024-08-24 So>

Removes given QueueElement from the front of the Queue and returns its value.

Arguments:

1. Queue** queue - Pointer to pointer to the queue that is modified.

Return type:

• Function returns the value of the QueueElement that was in the front of the Queue

Source: queue.h

QueueElement dequeue(Queue** queue);

Example usage:

Queue* queue = create_queue();

int new_key1 = 1;
int new_data1 = 2;

QueueElement new_element1 = {
        .key = new_key1,
        .data = &new_data1
};

QueueElement new_element2 = {
        .key = new_key2,
        .data = &new_data2
};

enqueue(new_element1, &queue);
enqueue(new_element2, &queue);

QueueElement dequeued_element = dequeue(&queue);

// Rest of the code

delete_queue(&queue);

<2024-08-24 So>

Returns the value of the QueueElement at the front of the Queue.

Arguments:

1. Queue* queue - Pointer to the queue that is to be peeked.

Return type:

• Function returns the value of the QueueElement that was in the front of the Queue

Source: queue.h

QueueElement peek(Queue* queue);

Example usage:

Queue* queue = create_queue();

int new_key1 = 1;
int new_data1 = 2;

QueueElement new_element1 = {
        .key = new_key1,
        .data = &new_data1
};

QueueElement new_element2 = {
        .key = new_key2,
        .data = &new_data2
};

enqueue(new_element1, &queue);
enqueue(new_element2, &queue);

QueueElement peeked_element = peek(&queue);

// Rest of the code

delete_queue(&queue);

<2024-08-24 So>

Serves as an element that the heap accepts for insert / extract operations

Elements:

1. int weight - integer value that serves as a weight
2. int edge[2] - array that contains two keys corresponding to the given edge of some graph

Source: heap.h

typedef struct HeapNode {
     int weight;
     int edge[2];
}HeapNode;

Example raw usage:

int new_weight = 42;
int new_edge[2] = { 0, 1 };

HeapNode new_heap_node = {
        .weight = new_weight,
        .data = new_edge
};

// Rest of the code

<2024-08-24 So>

Heap structure that is implemented as array binary tree representation.

Elements:

1. int size - integer value that is equal to the number of elements currently stored within the Heap
2. int capacity - integer value that is equal to the current capacity that the heap can hold without the heap_resize operation
3. HeapNode* content - pointer to array of HeapNode elements that holds the content of the Heap

Source: heap.h

typedef struct Heap {
     int size;
     int capacity;
     HeapNode* content;
} Heap;

Example raw usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

Heap* heap = (Heap*) malloc(sizeof(Heap));
heap->content = (HeapNode*) malloc(sizeof(HeapNode) * 2);
heap->capacity = 2;

heap->content[0] = new_heap_node1;
heap->content[1] = new_heap_node2;

heap->size = 2;

// Rest of the code

free(heap->content);
free(heap);

<2024-08-24 So>

Important: must be called before any other function

When called, a new Heap is created and allocated.

Arguments:

1. int capacity - integer value capacity that the Heap will be initialy allocated to

Return type:

• returns a pointer Heap* structure that points to newly created Heap

Source: heap.h

Heap* create_heap(int capacity);

Example usage:

Heap* new_heap = create_heap(5);

// Rest of the code

delete_heap(&new_heap);

<2024-08-24 So>

Important: use when no longer needed to avoid memory leaks

When called, Heap on given address will be deallocated and deleted.

Arguments:

1. Heap** heap - Pointer to pointer to the heap that is to be deleted.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, check stderr for more info

Source: heap.h

int delete_heap(Heap** heap);

Example usage:

Heap* new_heap = create_heap();

// Rest of the code

delete_heap(&new_heap);

<2024-08-24 So>

Resize the capacity of the given Heap.

Arguments:

1. int new_capacity - integer value of the new capacity that the Heap should be resized to.
2. Heap** heap - Pointer to pointer to the Heap that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  • exit_code = 0 - function finished succesfully
  • exit_code = 1 - function failed to execute, please see stderr for more info

Source: heap.h

int heap_resize(int new_capacity, Heap** heap);

Example usage:

Heap* heap = create_heap(2);

heap_resize(4, &heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Given a Heap and a node index in the content array, heapify the given node on that index.

Arguments:

1. int index - index of the HeapNode in the contents array that is to be heapified
2. Heap* heap - Pointer to the Heap that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: heap.h

int heapify(int index, Heap* heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

int new_weight3 = 126;
int new_edge3[2] = { 0, 3 };

HeapNode new_heap_node3 = {
        .weight = new_weight3,
        .data = new_edge3
};

Heap* heap = create_heap(3)

heap->content[0] = new_heap_node3;
heap->content[1] = new_heap_node2;
heap->content[2] = new_heap_node1;

heapify(0,heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Given a Heap with existing non valid HeapNode* content* array, make it into valid Heap.

Arguments:

1. Heap* heap - Pointer to the Heap that is to be made valid.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: heap.h

int make_heap(Heap* heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

int new_weight3 = 126;
int new_edge3[2] = { 0, 3 };

HeapNode new_heap_node3 = {
        .weight = new_weight3,
        .data = new_edge3
};

Heap* heap = create_heap(3)

heap->content[0] = new_heap_node3;
heap->content[1] = new_heap_node2;
heap->content[2] = new_heap_node1;

heap->size = 3;

make_heap(heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Info: when heap capacity is reached, the function resizes the heap to double the current capacity

Correctly insert a HeapNode into given Heap.

Arguments:

1. HeapNode node - HeapNode that is to be inserted and heapified into the Heap
2. Heap** heap - Pointer to pointer to the Heap that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: heap.h

int heap_insert_node(HeapNode node, Heap** heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

int new_weight3 = 126;
int new_edge3[2] = { 0, 3 };

HeapNode new_heap_node3 = {
        .weight = new_weight3,
        .data = new_edge3
};

Heap* heap = create_heap(3)

heap_insert_node(new_heap_node1, &heap);
heap_insert_node(new_heap_node2, &heap);
heap_insert_node(new_heap_node3, &heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Correctly delete a HeapNode from given Heap on given index.

Arguments:

1. int index - integer index of the node to be deleted. Index numbering 0 -> n - 1
2. Heap** heap - Pointer to pointer to the Heap that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: heap.h

int heap_delete_node(int index, Heap* heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

int new_weight3 = 126;
int new_edge3[2] = { 0, 3 };

HeapNode new_heap_node3 = {
        .weight = new_weight3,
        .data = new_edge3
};

Heap* heap = create_heap(3)

heap_insert_node(new_heap_node1, &heap);
heap_insert_node(new_heap_node2, &heap);
heap_insert_node(new_heap_node3, &heap);

heap_delete_node(1, &heap);

// Rest of the code

delete_heap(heap);

<2024-08-24 So>

Change node weight on a HeapNode from given Heap on given index.

Arguments:

1. int index - integer index of the HeapNode in the content array that is to be modified. Index numbering 0 -> n - 1
2. int new_value - new value that is to be set to the modified HeapNode weight
3. Heap* heap - Pointer to the Heap that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: heap.h

int heap_change_node_weight(int index, int new_value, Heap* heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

Heap* heap = create_heap(2)

heap_insert_node(new_heap_node1, &heap);
heap_insert_node(new_heap_node2, &heap);

heap_change_node_weight(2, 126, heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Deletes the minimal node of the Heap and returns its value.

Arguments:

1. Heap* heap - Pointer to the Heap that is to be modified.

Return type:

• HeapNode that contains the value of the extracted minimal node

Source: heap.h

HeapNode heap_extract_min(Heap* heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

Heap* heap = create_heap(2)

heap_insert_node(new_heap_node1, &heap);
heap_insert_node(new_heap_node2, &heap);

HeapNode extracted_min = heap_extract_min(heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Returns the value of the minimal node of the Heap.

Arguments:

1. Heap* heap - Pointer to the Heap that is to be peeked.

Return type:

• HeapNode that contains the value of the peeked minimal node

Source: heap.h

HeapNode heap_peek_min(Heap* heap);

Example usage:

int new_weight1 = 42;
int new_edge1[2] = { 0, 1 };

HeapNode new_heap_node1 = {
        .weight = new_weight1,
        .data = new_edge1
};

int new_weight2 = 84;
int new_edge2[2] = { 0, 2 };

HeapNode new_heap_node2 = {
        .weight = new_weight2,
        .data = new_edge2
};

Heap* heap = create_heap(2)

heap_insert_node(new_heap_node1, &heap);
heap_insert_node(new_heap_node2, &heap);

HeapNode extracted_min = heap_peek_min(heap);

// Rest of the code

delete_heap(&heap);

<2024-08-24 So>

Implementation of the graph data structure through adjacency list.

Elements:

1. int vertex_count - integer value holds the number of vertices in the given graph
2. int edge_count - integer value holds the number of edges in the given graph
3. Node** adjacency_list - Array of linked lists that represent the adjacency list of the given graph
4. bool directed - bool value that signals if the graph is directed or not

Source: graph.h

typedef struct Graph {
    int vertex_count;
    int edge_count;

    Node** adjacency_list;

    bool directed;
} Graph;

Example raw usage:

#include "linkedList.h"

Grap* graph = (Graph*) malloc(sizeof(Graph));

grph->vertex_count = 2;
graph->adjacency_list = (Node**) malloc(sizeof(Node*) * 2);

int weights[2] = { 1, 2 };

grph->edge_count = 2;
graph->adjacency_list[0] = create_linked_list(1, &weights[0]);
graph->adjacency_list[1] = create_linked_list(0, &weights[1]);

// Rest of the code

delete_linked_list(&graph->adjacency_list[0])
delete_linked_list(&graph->adjacency_list[1])

free(graph->adjacency_list);
free(graph);

<2024-08-24 So>

This strucutre represents a different way to store graph edge information that is used in some algorithms as return value.

Elements:

1. int left_vertex - integer value that signals the source vertex of the given edge
2. int right_vertex - integer value that signals the destination vertex of the given edge
3. bool directed - bool value that signals if the edge is directed or not

Source: graph.h

typedef struct {
    int left_vertex;
    int right_vertex;
    bool directed;
} EdgePair;

Example raw usage:

EdgePair edge1 = {
        .left_vertex = 0,
        .right_vertex = 1,
        .directed = true
};

// Rest of the code

<2024-08-24 So>

Important: must be called before any other function

When called, a new graph is created and allocated.

Arguments:

1. int vertex_count - integer value that signals the number of vertices that the Graph will be initialy allocated to
2. bool directed - bool value that signals if the Graph is directed or not

Return type:

• returns a pointer Graph* structure that points to newly created Graph

Source: graph.h

Graph* create_graph(int vertex_count, bool directed);

Example usage:

Heap* new_heap = create_heap(5);

// Rest of the code

delete_heap(&new_heap);

<2024-08-24 So>

Important: use when no longer needed to avoid memory leaks

When called, Graph on given address will be deallocated and deleted.

Arguments:

1. Graph** graph - Pointer to pointer to the Graph that is to be deleted.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, check stderr for more info

Source: graph.h

int delete_graph(Graph** graph);

Example usage:

Graph* new_graph = create_graph(5, false);

// Rest of the code

delete_graph(&new_graph);

<2024-08-24 So>

Adds a new vertex into the given Graph.

Arguments:

1. Graph* graph - Pointer to Graph that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: graph.h

int graph_add_vertex(Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

Removes a target vertex and all edges adjacent with it from the given Graph.

Arguments:

1. int target_vertex - integer value that is the number of the vertex that is to be removed. The vertex numbering goes from 0 -> n-1
2. Graph* graph - Pointer to Graph that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: graph.h

int graph_remove_vertex(int target_vertex, Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_remove_vertex(2, graph);

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

Connects the given source vertex to the destination vertex with an edge in the given Graph.

Arguments:

1. int src - integer value that is the number of the srouce vertex. The vertex numbering goes from 0 -> n-1
2. int dest - integer value that is the number of the destination vertex. The vertex numbering goes from 0 -> n-1
3. void* data - void pointer to data that is to be linked to given edge
4. Graph* graph - Pointer to Graph that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: graph.h

int graph_connect_edge(int src, int dest, void* data, Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

unsigned int data[3] = { 1234321, 2345, 2435 };

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_connect_edge(0, 1, &data[0], graph);
graph_connect_edge(1, 2, &data[1], graph);
graph_connect_edge(3, 0, &data[2], graph);

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

Disconnects the given edge from source vertex to the destination vertex in the given Graph.

Arguments:

1. int src - integer value that is the number of the srouce vertex. The vertex numbering goes from 0 -> n-1
2. int dest - integer value that is the number of the destination vertex. The vertex numbering goes from 0 -> n-1
3. Graph* graph - Pointer to Graph that is to be modified.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: graph.h

int graph_remove_edge(int src, int dest, Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

unsigned int data[3] = { 1234321, 2345, 2435 };

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_connect_edge(0, 1, &data[0], graph);
graph_connect_edge(1, 2, &data[1], graph);
graph_connect_edge(3, 0, &data[2], graph);

graph_remove_edge(1, 2, graph);

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

Returns true if the given edge from source vertex to the destination vertex exists in the given Graph.

Arguments:

1. int src - integer value that is the number of the srouce vertex. The vertex numbering goes from 0 -> n-1
2. int dest - integer value that is the number of the destination vertex. The vertex numbering goes from 0 -> n-1
3. Graph* graph - Pointer to Graph that is to be modified.

Return type:

• Function returns an bool value

Source: graph.h

bool graph_contains_edge(int src, int dest, Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

unsigned int data[3] = { 1234321, 2345, 2435 };

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_connect_edge(0, 1, &data[0], graph);
graph_connect_edge(1, 2, &data[1], graph);
graph_connect_edge(3, 0, &data[2], graph);

bool result = graph_contains_edge(1, 2, graph);

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

Returns pointer to data from edge identified as source vertex to the destination vertex in the given Graph.

Arguments:

1. int src - integer value that is the number of the srouce vertex. The vertex numbering goes from 0 -> n-1
2. int dest - integer value that is the number of the destination vertex. The vertex numbering goes from 0 -> n-1
3. Graph* graph - Pointer to Graph that is to be modified.

Return type:

• Function returns a void pointer

Source: graph.h

void* graph_get_edge_data(int src, int dest, Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

unsigned int data[3] = { 1234321, 2345, 2435 };

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_connect_edge(0, 1, &data[0], graph);
graph_connect_edge(1, 2, &data[1], graph);
graph_connect_edge(3, 0, &data[2], graph);

int result = *(int*)graph_get_edge_data(1, 2, graph);

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

Search through the given Graph and output the contents of the adjacency list and other information to given file descriptor

Arguments:

1. int file_descriptor - file descriptor of a file that is to be outputed into.
2. Graph* graph - Pointer to the Graph that its data is to be outputed.

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: graph.h

int print_graph_data(int file_descriptor, Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

unsigned int data[3] = { 1234321, 2345, 2435 };

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_connect_edge(0, 1, &data[0], graph);
graph_connect_edge(1, 2, &data[1], graph);
graph_connect_edge(3, 0, &data[2], graph);

// stdout has a file descriptor of 1 by default in every proccess (atleast on nixos)
print_graph_data(1, graph);

delete_graph(&graph);

<2024-08-24 So>

Search through the given Graph and output the contents of the adjacency list and other information to stdout

Arguments:

1. Graph* graph - Pointer to the Graph that its data is to be printed

Return type:

• Function returns an exit code in the form of integer value
  1. exit_code = 0 - function finished succesfully
  2. exit_code = 1 - function failed to execute, please see stderr for more info

Source: graph.h

int print_graph_data_to_stdout(Graph* graph);

Example usage:

Graph* graph = create_graph(1, false);

unsigned int data[3] = { 1234321, 2345, 2435 };

graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);
graph_add_vertex(Graph* graph);

graph_connect_edge(0, 1, &data[0], graph);
graph_connect_edge(1, 2, &data[1], graph);
graph_connect_edge(3, 0, &data[2], graph);

print_graph_data_to_stdout(graph);

delete_graph(&graph);

<2024-08-24 So>

External dependencies: grap.h

Performs a depth first search on the given graph and returns the corresponding search tree as another graph.

Arguments:

1. int start - integer value that is the number of the start vertex from which will the algorithm start its search. Vertex numbering is 0 -> n - 1
2. Graph* graph - pointer to the given graph that is to be search through

Return type:

• returns a pointer Graph* to the corresponding search tree of the depth first search

Source: graphAlgorithms.h

Graph* dfs_search_tree(int start, Graph* graph);

Example usage:

    Graph* graph = create_graph(5, false);
    graph_connect_edge(0, 1, NULL, graph);
    graph_connect_edge(0, 2, NULL, graph);
    graph_connect_edge(1, 3, NULL, graph);
    graph_connect_edge(1, 4, NULL, graph);
    graph_connect_edge(3, 4, NULL, graph);

    /*
            0
           / \
          1   2
         / \
        3 _ 4
    */

    Graph* dfs_tree = dfs_search_tree(0, graph);

    // Rest of the code

    delete_graph(&graph);
    delete_graph(&dfs_tree);

<2024-08-24 So>

External dependencies: grap.h, queue.h

Performs a breadth first search on the given graph and returns the shortest path between the start vertex and the destination vertex.

Arguments:

1. int start - integer value that is the number of the start vertex from which will the algorithm start its search. Vertex numbering is 0 -> n - 1
2. int destination - integer value that is the number of the destination vertex from which will the algorithm ends its search. Vertex numbering is 0 -> n - 1
3. Graph* graph - pointer to the given graph that is to be search through

Return type:

• returns a pointer int* to the corresponding shortest path of the breath first search

Source: graphAlgorithms.h

int* bfs_shortest_path(int start, int destination, Graph* graph);

Example usage:

Graph* graph = create_graph(6, false);

graph_connect_edge(0, 1, NULL, graph);
graph_connect_edge(0, 2, NULL, graph);
graph_connect_edge(1, 3, NULL, graph);
graph_connect_edge(1, 4, NULL, graph);
graph_connect_edge(2, 4, NULL, graph);
graph_connect_edge(3, 5, NULL, graph);
graph_connect_edge(4, 5, NULL, graph);

/*
            0
           / \
          1   2
         / \ /
        3   4
         \ /
          5


*/

int* path = bfs_shortest_path(0, 3, graph);

free(path);
delete_graph(&graph);

Important: it is assumed by the algorithm that the given graph is a DAG

External dependencies: grap.h, queue.h

Performs a Kahns algorithm on the given graph and returns the topological order of vertices.

Arguments:

1. Graph* graph - pointer to the given graph that is to be sorted

Return type:

• returns a pointer int* to the corresponding topological order of vertices in the given Graph

Source: graphAlgorithms.h

int* kahn_topological_sort(Graph* graph);

Example usage:

Graph* graph = create_graph(6, true);

graph_connect_edge(5, 2, NULL, graph);
graph_connect_edge(5, 0, NULL, graph);
graph_connect_edge(0, 4, NULL, graph);
graph_connect_edge(4, 2, NULL, graph);
graph_connect_edge(2, 3, NULL, graph);
graph_connect_edge(3, 1, NULL, graph);
graph_connect_edge(2, 1, NULL, graph);

/*

      5 → 2 → 3 → 1
      ↓   |_______^
      0   ^
      ↓   |
      4___|

*/

int* topological_order = kahn_topological_sort(graph);

// Rest of the code

free(topological_order);
delete_graph(&graph);

External dependencies: grap.h

Finds and numbers the vertices of given graph into connected components. Two vertices share a component number if and only if the are in the same component.

Arguments:

1. Graph* graph - pointer to the given graph that is to be numbered

Return type:

• returns a pointer int* to the list of component numbers that are linked to given vertex on that index. The numbering of components is 0 -> n-1

Source: graphAlgorithms.h

int* find_weakly_connected_components(Graph* graph);

Example usage:

Graph* graph = create_graph(6, false);

graph_connect_edge(0, 1, NULL, graph);
graph_connect_edge(1, 2, NULL, graph);
graph_connect_edge(3, 4, NULL, graph);

/*
            0 - 1 - 2

            3 - 4

            5
*/

int* components = find_weakly_connected_components(graph);

int component_number_of_vertex_4 = components[4];

// Rest of the code

free(components);
delete_graph(&graph);

External dependencies: grap.h, kahn_{topologicalsort} from graphAlgorithms.h

Checks if the given Graph does or does not contain a cycle.

Arguments:

1. Graph* graph - pointer to the given graph that is to be checked

Return type:

• Returns a bool that signals if the given graph is acyclic or not

Source: graphAlgorithms.h

bool is_acyclic(Graph* graph);

Example usage:

Graph* graph = create_graph(3, true);

// 0 → 1 → 2 → 0
graph_connect_edge(0, 1, NULL, graph);
graph_connect_edge(1, 2, NULL, graph);
graph_connect_edge(2, 0, NULL, graph);

bool is_dag = graph->directed && is_acyclic(graph);

// Rest of the code

delete_graph(&graph);

External dependencies: grap.h

Checks if the given Graph is or is not a tree.

Arguments:

1. Graph* graph - pointer to the given graph that is to be checked

Return type:

• Returns a bool that signals if the given graph is or isnt a tree

Source: graphAlgorithms.h

bool is_tree(Graph* graph)

Example usage:

Graph* graph = create_graph(5, false);

graph_connect_edge(0, 1, NULL, graph);
graph_connect_edge(0, 2, NULL, graph);
graph_connect_edge(1, 3, NULL, graph);
graph_connect_edge(1, 4, NULL, graph);

/*
            0
           / \
          1   2
         / \
        3   4
*/

bool is_a_tree = is_tree(graph);

// Rest of the code

delete_graph(&graph);

External dependencies: grap.h, queue.h,

Checks if the given Graph is or is not bipartite.

Arguments:

1. Graph* graph - pointer to the given graph that is to be checked

Return type:

• Returns a bool that signals if the given graph is or is not a bipartite

Source: graphAlgorithms.h

bool is_bipartite(Graph* graph)

Example usage:

Graph* graph = create_graph(6, false);

graph_connect_edge(0, 1, NULL, graph);
graph_connect_edge(1, 2, NULL, graph);
graph_connect_edge(2, 3, NULL, graph);
graph_connect_edge(3, 4, NULL, graph);
graph_connect_edge(4, 5, NULL, graph);
graph_connect_edge(5, 0, NULL, graph);

bool is_bipartite = is_bipartite(graph);

// Rest of the code

delete_graph(&graph);

External dependencies: grap.h, heap.h

Important: the algorithm assumes that the graph is directed and connected, and the edge data is going to be typecasted and dereferenced by the algorithm as (int) corresponding to the weight of the edge

Performs Dijkstras shortest path algorithm on the given graph and returns the corresponding shortest path tree as another graph.

Arguments:

1. int start - integer value that is the number of the start vertex from which will the algorithm start its search. Vertex numbering is 0 -> n - 1
2. Graph* graph - pointer to the given graph that is to be search through

Return type:

• returns a pointer Graph* to the corresponding shortest path tree of the shortest path algorithm

Source: graphAlgorithms.h

Graph* dijkstra_shortest_paths(int start, Graph* graph)

Example usage:

Graph* graph = create_graph(5, true);

int weights[5] = {10, 10, 5, 1, 50};

graph_connect_edge(0, 1, &weights[0], graph);
graph_connect_edge(0, 2, &weights[1], graph);
graph_connect_edge(1, 3, &weights[2], graph);
graph_connect_edge(2, 3, &weights[3], graph);
graph_connect_edge(3, 4, &weights[4], graph);

Graph* shortest_paths = dijkstra_shortest_paths(0, graph);

// Rest of the code

delete_graph(&graph);
delete_graph(&shortest_paths)

<2024-08-24 So>

External dependencies: grap.h, heap.h

Important: the algorithm assumes that the graph is undirected and connected, and the edge data is going to be typecasted and dereferenced by the algorithm as (int) corresponding to the weight of the edge

Performs Jarniks (Also known as Prims) algorithm on the given graph and returns the corresponding minimum spanning tree as another graph.

Arguments:

1. Graph* graph - pointer to the given graph that is to be searched through

Return type:

• returns a pointer Graph* to the corresponding minimum spanning tree

Source: graphAlgorithms.h

Graph* jarnik_minimum_spanning_tree(Graph* graph);

Example usage:

Graph* graph = create_graph(4, false);

int weights[5] = {11, 20, 12, 40, 30};

graph_connect_edge(0, 1, &weights[0], graph);

graph_connect_edge(1, 2, &weights[1], graph);
graph_connect_edge(2, 3, &weights[2], graph);
graph_connect_edge(0, 3, &weights[3], graph);
graph_connect_edge(0, 2, &weights[4], graph);

Graph* mst = jarnik_minimum_spanning_tree(graph);

print_graph_data_to_stdout(mst);

// Rest of the code

delete_graph(&graph);
delete_graph(&mst);

<2024-08-24 So>

External dependencies: grap.h, queue.h

Important: the algorithm assumes that the graph is directed and connected, and the edge data is going to be typecasted and dereferenced by the algorithm as (int) corresponding to the capacity of the edge

Performs Edmonds-Karp algorithm on the given graph and returns the value of the maximal flow as an integer.

Arguments:

1. int source - integer that is the vertex number of the source in the graph network
2. int source - integer that is the vertex number of the sink in the graph network
3. Graph* graph - pointer to the given graph that is to be searched through

Return type:

• returns a integer value of the maximalflow

Source: graphAlgorithms.h

int edmonds_karp_max_flow(int source, int sink, Graph* graph)

Example usage:

Graph* graph = create_graph(5, true);

int edge_capacity[8] = {10, 10, 15, 10, 10, 10, 10, 10};

graph_connect_edge(0, 1, &edge_capacity[0], graph);
graph_connect_edge(0, 2, &edge_capacity[1], graph);
graph_connect_edge(1, 3, &edge_capacity[2], graph);
graph_connect_edge(2, 3, &edge_capacity[3], graph);
graph_connect_edge(1, 4, &edge_capacity[4], graph);
graph_connect_edge(2, 4, &edge_capacity[5], graph);
graph_connect_edge(4, 3, &edge_capacity[6], graph);

int source = 0;
int sink = 3;

int max_flow = edmonds_karp_max_flow(source, sink, graph);
// Rest of the code

delete_graph(&graph);

<2024-08-24 So>

External dependencies: grap.h, edmonds_karpmaxflow from graphAlgorithm.h

Important: the algorithm assumes that the graph is bipartite and the left_set - right_set is truly the corresponding division of the bipartite graph into two sets

The algorithm finds out the maximum size of matching in the given bipartite graph.

Arguments:

1. int* left_set - an array that corresponds to the left set of the bipartite graph division
2. int* left_set_size - size of the left_set array
3. int* right_set - an array that corresponds to the right set of the bipartite graph division
4. int* right_set_size - size of the right_set array
5. Graph* graph - pointer to the given graph that is to be matched through

Return type:

• returns a integer value of the size of the maximal bipartite matching

Source: graphAlgorithms.h

int max_bipartite_matching(int* left_set, int left_set_size, int* right_set, int right_set_size, Graph* bipartite_graph)

Example usage:

Graph* graph = create_graph(8, true);

int left_set[4] = { 0, 1, 2, 3};
int right_set[4] = { 4, 5, 6, 7};

graph_connect_edge(0, 4, NULL, graph);
graph_connect_edge(1, 5, NULL, graph);
graph_connect_edge(2, 6, NULL, graph);
graph_connect_edge(3, 7, NULL, graph);
graph_connect_edge(1, 7, NULL, graph);
graph_connect_edge(2, 5, NULL, graph);
graph_connect_edge(0, 5, NULL, graph);

int max_matching

if (is_bipartite(graph))
{
    max_matching = max_bipartite_matching(left_set, 4, right_set, 4, graph);
}

// Rest of the code

delete_graph(&graph);

<2024-08-24 So>