MyGraph.cpp

#include <iostream>
#include <set>
#include <queue>
#include "MyGraph.h"

std::ostream& AdjacencyList::output(std::ostream& os, size_t offset) {
    for (size_t i = 0; i < numVertices(); ++i) {
        for (std::pair<TransVertex, Weight> col : data.at(i)) {
            os << (i + offset) << " " << (col.first + offset) << " " << col.second << "\n";
        }
    }
    return (os << std::flush);
}

Weight& AdjacencyList::operator()(TransVertex start, TransVertex end) {
    if (start < end)
        return data.at(start).at(end);
    else
        return data.at(end).at(start);
}

const Weight& AdjacencyList::operator()(TransVertex start, TransVertex end) const {
    if (start < end)
        return data.at(start).at(end);
    else
        return data.at(end).at(start);
}

template <class T> T& temporary(T&& x) { return x; }

Weight& AdjacencyList::getVertex(Vertex start, Vertex end) {
    try {
        return operator()(toTransVertex(start), toTransVertex(end));
    } catch (std::out_of_range& e) {
        Weight&& infinity = INFINITY;
        return temporary(infinity);
    }
}

const Weight& AdjacencyList::getVertex(Vertex start, Vertex end) const {
    try {
        return operator()(toTransVertex(start), toTransVertex(end));
    } catch (std::out_of_range& e) {
        return INFINITY;
    }
}

bool AdjacencyList::insertTransEdge(TransVertex start, TransVertex end, Weight weight) {
    if (start < 0 || start >= numVertices() || end < 0 || end >= numVertices())
        return false;

    bool ret = false;
    if (start < end)
        ret = data.at(start).try_emplace(end, weight).second;
    else
        ret = data.at(end).try_emplace(start, weight).second;

    if (ret) ++_numEdges;
    return ret;
} 

MyGraph::MyGraph(size_t vertices) : weights {vertices} {}
MyGraph::MyGraph(const MyGraph& other) : weights {other.weights} {}
MyGraph::MyGraph(size_t vertices, const std::vector<Link>& edges) : weights {vertices} {
    for (const Link& link : edges) {
        addEdge(link.v1, link.v2, link.w);
    }
}

bool MyGraph::addEdge(Vertex a, Vertex b, Weight w)
{
    return weights.insertEdge(a, b, w);
}

void MyGraph::output(ostream& os)
{
    os << weights.numVertices() << "\n";
    weights.outputVertices(os);
}

std::pair<std::vector<Link>, std::optional<std::vector<Vertex> >> MyGraph::MSTLink()
{
    const int n = weights.numVertices();
    auto kruskal = [&]() -> std::pair<std::vector<Link>, std::optional<std::vector<Vertex> >> {
        std::vector<int> num(n + 1); // Tracks number of nodes for speed
        std::vector<Vertex> disjoint(n + 1);
        std::vector<Link> F(n - 1);

        // Fill E with all edges, sorting in process
        std::set<Link> sortedEdges;
        for (int i = 1; i <= n; ++i) {
            for (std::pair<TransVertex, Weight> col : weights[toTransVertex(i)]) {
                sortedEdges.insert(Link(i, toVertex(col.first), col.second));
            }
        }

        // Define disjoint set functions
#define num(i) num.at(i)
#define parent(i) disjoint.at(i)

        auto makeset3 = [&](int i) {
            parent(i) = i;
            num(i) = 1;
        };
        auto mergetrees3 = [&](int i, int j) {
            if (num(i) < num(j)) {
                parent(i) = j;
                num(j) += num(i);
            } else if (num(i) > num(j)) {
                parent(j) = i;
                num(i) += num(j);
            } else {
                parent(i) = j;
                num(j) += num(i);
            }
        };
        auto findset4 = [&](int i) {
            int root = i;
            while (parent(root) != root) {
                root = parent(root);
            }
            int& j = parent(i);
            while (j != root) {
                parent(i) = root;
                i = j;
                j = parent(i);
            }
            return root;
        };
#define union4(i, j) mergetrees3(findset4(i), findset4(j))

        // Start the algorithm
        for (int i = 1; i <= n; ++i)
            makeset3(i);

        int edges = 0;
        std::set<Link> E(sortedEdges);
        while (edges < n - 1) {
            F[edges] = *E.begin(); // Save the minimum weight edge
            E.erase(E.begin()); // Remove the minimum weight edge
            if (findset4(F[edges].v1) == findset4(F[edges].v2))
                continue;
            union4(F[edges].v1, F[edges].v2);
            ++edges;
        }
        return std::make_pair(F, std::optional<std::vector<Vertex>>(std::nullopt));
    };
    auto prim = [&]() -> std::pair<std::vector<Link>, std::optional<vector<Vertex> >> {
        std::vector<Link> F(n - 1);
        std::vector<Vertex> minNeighbor(n + 1, 1);
        std::vector<Weight> minWeight(n + 1);
        std::vector<bool> selected(n + 1, false);

        for (int i = 2; i <= n; ++i)
            minWeight.at(i) = weights.getVertex(1, i);
        selected.at(1) = true;

        for (int edges = 0; edges < n - 1; ++edges) {
            // Select next vertex to selected by picking smallest weight edge
            float min = INFINITY;
            int minIndex = -1;
            for (int i = 2; i <= n; ++i) {
                if (!selected.at(i) && minWeight.at(i) < min) {
                    min = minWeight.at(i);
                    minIndex = i;
                }
            }

            // Add edge to F and corresponding vertex to selected
            F.at(edges) = Link(minNeighbor.at(minIndex), minIndex, weights);
            selected.at(minIndex) = true;

            // Consider all edges from newly selected to unselected vertices and update min weight
            for (int i = 2; i <= n; ++i) {
                if (!selected.at(i) && weights.getVertex(minIndex, i) < minWeight.at(i)) {
                    minWeight.at(i) = weights.getVertex(minIndex, i);
                    minNeighbor.at(i) = minIndex;
                }
            }
        }
        return std::make_pair(F, std::optional<std::vector<Vertex>>(minNeighbor));
    };

    auto _kruskal = std::log(static_cast<long double>(weights.numEdges())) * weights.numEdges();
    auto _prim = weights.numVertices() * weights.numVertices();
    //if (_kruskal < _prim)
    //return kruskal(); 
    //else
    return prim();
}

struct IndexedWeight {
    int index;
    Weight weight;
    IndexedWeight() : index {0}, weight {0} {}
    IndexedWeight(int i, Weight w) : index {i}, weight {w} {}
    inline bool operator<(const IndexedWeight& other) { return weight < other.weight;}
    inline bool operator>(const IndexedWeight& other) { return weight > other.weight;}
    std::pair<int, Weight> pair() { return std::pair<int, Weight>(index, weight); }
};

/*
class DecreasableHeap {
    private:
        std::vector<IndexedWeight> actualHeap;
        std::vector<int> indexLocations;
#define iParent ((i - 1) / 2)
#define iLeft (2 * i + 1)
#define iRight (2 * i + 2)
    public:
        void insert(const IndexedWeight& value) {
            actualHeap.push_back(value);
            indexLocations.push_back(value.index);
            for (int i = actualHeap.size() - 1; actualHeap.at(i) < actualHeap.at(iParent);
                    i = iParent) {
                std::swap(actualHeap.at(i), actualHeap.at(iParent));
                std::swap(indexLocations.at(i), indexLocations.at(iParent));
            }
        }
        IndexedWeight deleteMin() {
            std::swap(actualHeap.at(0), actualHeap.at(actualHeap.size() - 1));
            auto ret = actualHeap.at(actualHeap.size() - 1);
            actualHeap.pop_back();
            std::swap(indexLocations.at(0), indexLocations.at(indexLocations.size() - 1));
            indexLocations.pop_back();

            int i = 0;
            while (true) {
                if (iLeft < actualHeap.size()) {
                    if (iRight < actualHeap.size() && actualHeap.at(iRight) > actualHeap.at(iLeft)) {
                        if (actualHeap.at(i) > actualHeap.at(iRight)) {
                            std::swap(actualHeap.at(i), actualHeap.at(iRight));
                            std::swap(indexLocations.at(i), indexLocations.at(iRight));
                            i = iRight;
                        } else { break; }
                    } else {
                        if (actualHeap.at(i) > actualHeap.at(iLeft)) {
                            std::swap(actualHeap.at(i), actualHeap.at(iLeft));
                            std::swap(indexLocations.at(i), indexLocations.at(iLeft));
                        } else { break; }
                    }    
                } else {
                    break;
                }
            }
            return ret;
        }
        void decrease(int index, Weight weight) {
            int i = indexLocations.at(index);
            actualHeap.at(i).weight = weight;
            for (int i = actualHeap.size() - 1; actualHeap.at(i) < actualHeap.at(iParent);
                    i = iParent) {
                std::swap(actualHeap.at(i), actualHeap.at(iParent));
                std::swap(indexLocations.at(i), indexLocations.at(iParent));
            }
        }
};


std::vector<Vertex> dijkstraMod(size_t n, const std::vector<Link>& mst) {
    // Kruskal doesn't give us a path for free
    // However, with the MST, just get the shortest path in O(n log n) with modified Dijkstra
    std::vector<Link> F(n - 1);
    std::vector<Vertex> minNeighbor(n + 1, 1);
    std::vector<Weight> minWeight(n + 1);
    DecreasableHeap notInY;
    MyGraph pathWorker = MyGraph(n, mst);
    auto& weights = pathWorker.weights;

    for (int i = 2; i <= n; ++i) {
        minWeight.at(i) = weights.getVertex(1, i);
        notInY.insert(IndexedWeight(i, weights.getVertex(1, i)));
    }

    for (int edges = 0; edges < n - 1; ++edges) {
        // Select next vertex to selected by picking smallest weight edge
        auto [minIndex, min] = notInY.deleteMin().pair();

        // Add edge to F
        F.at(edges) = Link(minNeighbor.at(minIndex), minIndex, weights);

        // Consider all edges from newly selected to unselected vertices and update min weight
        for (const std::pair<TransVertex, Weight>& edge : weights[toTransVertex(minIndex)]) {
            const auto& [i, w] = edge;
            if (w + minWeight.at(minIndex) < minWeight.at(i)) {
                minWeight.at(i) = w + minWeight.at(minIndex);
                notInY.decrease(i, minWeight.at(i));
                minNeighbor.at(i) = minIndex;
            }
        }
    }
    return minNeighbor;
}
*/

std::pair<std::vector<Link>, std::vector<Vertex> > Prog2(std::vector<Weight> satcost,
        std::vector<Link> linkcost, Vertex& sat_conn)
{
    sat_conn = std::distance(satcost.begin(), std::min_element(satcost.begin() + 1, satcost.end()));
    const size_t n = satcost.size() - 1;
    MyGraph MSTworker = MyGraph(n, linkcost);
    auto [mst, info] = MSTworker.MSTLink();
    std::vector<Vertex> path = {0, sat_conn};
    std::vector<Vertex> minNeighbor;
    //if (info.has_value()) {
        minNeighbor = info.value();
    //} else {
    //    minNeighbor = dijkstraMod(n, mst);
    //}
    // Convert minNeighbor into a path and return
#define LAST path.at(path.size() - 1)
    while (LAST != 1) {
        path.push_back(minNeighbor.at(LAST));
    }
    return std::make_pair(mst, path);
}