Graph Algorithms Overview

template <typename T>
struct edge {
    int from;
    int to;
    T cost;
};

template <typename T>
struct link {
    int to;
    T cost;
    bool operator>(const link& other) const {return cost > other.cost;}
    bool operator<(const link& other) const {return cost < other.cost;}
};

template <typename T>
class graph {
public:
    vector<edge<T>> edges;
    vector<vector<link<T>>> adj;
    int n;
    graph(int sz) : n(sz) {
        adj.resize(n);
    }
    virtual void add(int from, int to, T cost) = 0;
};

template <typename T>
class undigraph : public graph<T> {
public:
    using graph<T>::edges;
    using graph<T>::adj;
    using graph<T>::n;

    undigraph(int sz) : graph<T>(sz) {}

    void add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        edges.push_back({from, to, cost});
        adj[from].push_back({to, cost});
        adj[to].push_back({from, cost});
    }
};

template <typename T>
class digraph : public graph<T> {
public:
    using graph<T>::edges;
    using graph<T>::adj;
    using graph<T>::n;

    digraph(int sz) : graph<T>(sz) {}

    void add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        edges.push_back({from, to, cost});
        adj[from].push_back({to, cost});
    }
    
    digraph<T> reverse() const {
        digraph<T> rev(n);
        for (auto &e : edges) {
            rev.add(e.to, e.from, e.cost);
        }
        return rev;
    }
};

// Create an undirected graph with 5 nodes
undigraph<int> g(5);
g.add(0, 1, 2);  // Edge from 0 to 1 with cost 2
g.add(1, 2, 3);
g.add(2, 3, 1);
g.add(3, 4, 4);

// Create a directed graph
digraph<int> dg(5);
dg.add(0, 1, 2);  // Directed edge from 0 to 1
dg.add(1, 2, 3);