graph.cpp

#include "graph.h"
#include <iostream>
#include <cstdlib>

// Doubles capacity when full
void free_int_list(IntList& list) {
    if (list.data != nullptr) {
        delete[] list.data;
        list.data = nullptr;
    }
    list.size = 0;
    list.capacity = 0;
}

void add_to_int_list(IntList& list, int value) {
    if (list.size >= list.capacity) {
        int new_capacity = (list.capacity == 0) ? 4 : list.capacity * 2;
        int* new_data = new int[new_capacity];
        for (int i = 0; i < list.size; i++) {
            new_data[i] = list.data[i];
        }
        delete[] list.data;
        list.data = new_data;
        list.capacity = new_capacity;
    }
    list.data[list.size++] = value;
}

Graph::Graph(int n, bool directed) : num_vertices(n), is_directed(directed) {
    adj_list = new IntList[n];
    for (int i = 0; i < n; i++) {
        adj_list[i].data = nullptr;
        adj_list[i].size = 0;
        adj_list[i].capacity = 0;
    }
}

void Graph::add_edge(int u, int v) {
    if (u < 0 || u >= num_vertices || v < 0 || v >= num_vertices) {
        std::cerr << "Error: vertex out of bounds\n";
        return;
    }
    add_to_int_list(adj_list[u], v);
    if (!is_directed) {
        add_to_int_list(adj_list[v], u);
    }
}

void Graph::print() const {
    for (int i = 0; i < num_vertices; i++) {
        std::cout << i << ": [";
        for (int j = 0; j < adj_list[i].size; j++) {
            std::cout << adj_list[i].data[j];
            if (j < adj_list[i].size - 1) std::cout << ", ";
        }
        std::cout << "]\n";
    }
}

struct IntQueue {
    int* data;
    int front;
    int rear;
    int capacity;
    int size;
};

void init_queue(IntQueue& q, int cap) {
    q.capacity = cap;
    q.data = new int[cap];
    q.front = 0;
    q.rear = 0;
    q.size = 0;
}

void push_queue(IntQueue& q, int value) {
    if (q.size >= q.capacity) {
        int new_cap = q.capacity * 2;
        int* new_data = new int[new_cap];
        for (int i = 0; i < q.size; i++) {
            new_data[i] = q.data[(q.front + i) % q.capacity];
        }
        delete[] q.data;
        q.data = new_data;
        q.front = 0;
        q.rear = q.size;
        q.capacity = new_cap;
    }
    q.data[q.rear] = value;
    q.rear = (q.rear + 1) % q.capacity;
    q.size++;
}

int pop_queue(IntQueue& q) {
    if (q.size == 0) return -1;
    int value = q.data[q.front];
    q.front = (q.front + 1) % q.capacity;
    q.size--;
    return value;
}

bool is_queue_empty(IntQueue& q) {
    return q.size == 0;
}

void free_queue(IntQueue& q) {
    if (q.data != nullptr) {
        delete[] q.data;
        q.data = nullptr;
    }
    q.size = 0;
    q.capacity = 0;
}

// Queue-based level-order traversal
IntList bfs(const Graph& G, int start) {
    IntList result;
    result.data = nullptr;
    result.size = 0;
    result.capacity = 0;
    
    if (start < 0 || start >= G.num_vertices) {
        std::cerr << "Error: start vertex out of bounds\n";
        return result;
    }
    
    bool* visited = new bool[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
    }
    
    IntQueue q;
    init_queue(q, 16);
    
    push_queue(q, start);
    visited[start] = true;
    
    while (!is_queue_empty(q)) {
        int v = pop_queue(q);
        add_to_int_list(result, v);
        
        for (int i = 0; i < G.adj_list[v].size; i++) {
            int neighbor = G.adj_list[v].data[i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                push_queue(q, neighbor);
            }
        }
    }
    
    delete[] visited;
    free_queue(q);
    return result;
}

void dfs_helper(const Graph& G, int v, bool* visited, IntList& result) {
    visited[v] = true;
    add_to_int_list(result, v);
    
    for (int i = 0; i < G.adj_list[v].size; i++) {
        int neighbor = G.adj_list[v].data[i];
        if (!visited[neighbor]) {
            dfs_helper(G, neighbor, visited, result);
        }
    }
}

// Recursive depth-first traversal
IntList dfs(const Graph& G, int start) {
    IntList result;
    result.data = nullptr;
    result.size = 0;
    result.capacity = 0;
    
    if (start < 0 || start >= G.num_vertices) {
        std::cerr << "Error: start vertex out of bounds\n";
        return result;
    }
    
    bool* visited = new bool[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
    }
    
    dfs_helper(G, start, visited, result);
    
    delete[] visited;
    return result;
}

int degree(const Graph& G, int v) {
    if (v < 0 || v >= G.num_vertices) {
        std::cerr << "Error: vertex out of bounds\n";
        return -1;
    }
    return G.adj_list[v].size;
}

IntList degree_sequence(const Graph& G) {
    IntList result;
    result.data = nullptr;
    result.size = 0;
    result.capacity = 0;
    
    for (int i = 0; i < G.num_vertices; i++) {
        add_to_int_list(result, degree(G, i));
    }
    return result;
}

void dfs_connected(const Graph& G, int v, bool* visited) {
    visited[v] = true;
    for (int i = 0; i < G.adj_list[v].size; i++) {
        int neighbor = G.adj_list[v].data[i];
        if (!visited[neighbor]) {
            dfs_connected(G, neighbor, visited);
        }
    }
}

bool is_connected(const Graph& G) {
    if (G.num_vertices == 0) return true;
    
    bool* visited = new bool[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
    }
    
    dfs_connected(G, 0, visited);
    
    for (int i = 0; i < G.num_vertices; i++) {
        if (!visited[i]) {
            delete[] visited;
            return false;
        }
    }
    delete[] visited;
    return true;
}

bool is_bipartite(const Graph& G) {
    if (G.num_vertices == 0) return true;
    
    int* color = new int[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        color[i] = -1;
    }
    
    for (int start = 0; start < G.num_vertices; start++) {
        if (color[start] != -1) continue;
        
        color[start] = 0;
        IntQueue q;
        init_queue(q, 16);
        push_queue(q, start);
        
        while (!is_queue_empty(q)) {
            int v = pop_queue(q);
            
            for (int i = 0; i < G.adj_list[v].size; i++) {
                int neighbor = G.adj_list[v].data[i];
                if (color[neighbor] == -1) {
                    color[neighbor] = 1 - color[v];
                    push_queue(q, neighbor);
                } else if (color[neighbor] == color[v]) {
                    delete[] color;
                    free_queue(q);
                    return false;
                }
            }
        }
        free_queue(q);
    }
    
    delete[] color;
    return true;
}

int count_components(const Graph& G) {
    if (G.num_vertices == 0) return 0;
    
    bool* visited = new bool[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
    }
    int count = 0;
    
    for (int i = 0; i < G.num_vertices; i++) {
        if (!visited[i]) {
            dfs_connected(G, i, visited);
            count++;
        }
    }
    
    delete[] visited;
    return count;
}

bool has_cycle_helper(const Graph& G, int v, int parent, bool* visited) {
    visited[v] = true;
    
    for (int i = 0; i < G.adj_list[v].size; i++) {
        int neighbor = G.adj_list[v].data[i];
        if (!visited[neighbor]) {
            if (has_cycle_helper(G, neighbor, v, visited)) {
                return true;
            }
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool has_cycle(const Graph& G) {
    if (G.num_vertices == 0) return false;
    
    bool* visited = new bool[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
    }
    
    for (int i = 0; i < G.num_vertices; i++) {
        if (!visited[i]) {
            if (has_cycle_helper(G, i, -1, visited)) {
                delete[] visited;
                return true;
            }
        }
    }
    delete[] visited;
    return false;
}

// BFS from source, stop when destination reached
int shortest_path(const Graph& G, int src, int dst) {
    if (src < 0 || src >= G.num_vertices || dst < 0 || dst >= G.num_vertices) {
        return -1;
    }
    
    bool* visited = new bool[G.num_vertices];
    int* dist = new int[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
        dist[i] = -1;
    }
    
    IntQueue q;
    init_queue(q, 16);
    
    push_queue(q, src);
    visited[src] = true;
    dist[src] = 0;
    
    while (!is_queue_empty(q)) {
        int v = pop_queue(q);
        
        if (v == dst) {
            int result = dist[v];
            delete[] visited;
            delete[] dist;
            free_queue(q);
            return result;
        }
        
        for (int i = 0; i < G.adj_list[v].size; i++) {
            int neighbor = G.adj_list[v].data[i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                dist[neighbor] = dist[v] + 1;
                push_queue(q, neighbor);
            }
        }
    }
    
    delete[] visited;
    delete[] dist;
    free_queue(q);
    return -1;
}

IntList get_path(const Graph& G, int src, int dst) {
    IntList result;
    result.data = nullptr;
    result.size = 0;
    result.capacity = 0;
    
    if (src < 0 || src >= G.num_vertices || dst < 0 || dst >= G.num_vertices) {
        return result;
    }
    
    bool* visited = new bool[G.num_vertices];
    int* parent = new int[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        visited[i] = false;
        parent[i] = -1;
    }
    
    IntQueue q;
    init_queue(q, 16);
    
    push_queue(q, src);
    visited[src] = true;
    
    while (!is_queue_empty(q)) {
        int v = pop_queue(q);
        
        if (v == dst) {
            int current = dst;
            while (current != -1) {
                add_to_int_list(result, current);
                current = parent[current];
            }
            for (int i = 0; i < result.size / 2; i++) {
                int temp = result.data[i];
                result.data[i] = result.data[result.size - 1 - i];
                result.data[result.size - 1 - i] = temp;
            }
            delete[] visited;
            delete[] parent;
            free_queue(q);
            return result;
        }
        
        for (int i = 0; i < G.adj_list[v].size; i++) {
            int neighbor = G.adj_list[v].data[i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                parent[neighbor] = v;
                push_queue(q, neighbor);
            }
        }
    }
    
    delete[] visited;
    delete[] parent;
    free_queue(q);
    return result;
}

bool has_eulerian_path(const Graph& G) {
    if (G.num_vertices == 0) return false;
    if (!is_connected(G)) return false;
    
    int odd_degree_count = 0;
    for (int i = 0; i < G.num_vertices; i++) {
        if (degree(G, i) % 2 != 0) {
            odd_degree_count++;
        }
    }
    
    return odd_degree_count == 0 || odd_degree_count == 2;
}

bool has_eulerian_circuit(const Graph& G) {
    if (G.num_vertices == 0) return false;
    
    for (int i = 0; i < G.num_vertices; i++) {
        if (degree(G, i) % 2 != 0) {
            return false;
        }
    }
    return is_connected(G);
}

// Kahn's algorithm: remove vertices with zero in-degree iteratively
IntList topological_sort(const Graph& G) {
    IntList result;
    result.data = nullptr;
    result.size = 0;
    result.capacity = 0;
    
    if (!G.is_directed) {
        std::cerr << "Error: topological sort only works on directed graphs\n";
        return result;
    }
    
    int* in_degree = new int[G.num_vertices];
    for (int i = 0; i < G.num_vertices; i++) {
        in_degree[i] = 0;
    }
    
    for (int i = 0; i < G.num_vertices; i++) {
        for (int j = 0; j < G.adj_list[i].size; j++) {
            in_degree[G.adj_list[i].data[j]]++;
        }
    }
    
    IntQueue q;
    init_queue(q, 16);
    for (int i = 0; i < G.num_vertices; i++) {
        if (in_degree[i] == 0) {
            push_queue(q, i);
        }
    }
    
    while (!is_queue_empty(q)) {
        int v = pop_queue(q);
        add_to_int_list(result, v);
        
        for (int i = 0; i < G.adj_list[v].size; i++) {
            int neighbor = G.adj_list[v].data[i];
            in_degree[neighbor]--;
            if (in_degree[neighbor] == 0) {
                push_queue(q, neighbor);
            }
        }
    }
    
    if (result.size != G.num_vertices) {
        std::cerr << "Error: graph has a cycle, topological sort not possible\n";
        free_int_list(result);
    }
    
    delete[] in_degree;
    free_queue(q);
    return result;
}

void free_graph(Graph& G) {
    if (G.adj_list != nullptr) {
        for (int i = 0; i < G.num_vertices; i++) {
            free_int_list(G.adj_list[i]);
        }
        delete[] G.adj_list;
        G.adj_list = nullptr;
    }
    G.num_vertices = 0;
}