Skip to content

wangtz0607/graph

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
cmake
cmake
 
 
include/graph
include/graph
 
 
.gitignore
.gitignore
 
 
CMakeLists.txt
CMakeLists.txt
 
 
LICENSE
LICENSE
 
 
README.md
README.md
 
 

Repository files navigation

Graph

Supported Algorithms

  • DepthFirstSearch
  • BreadthFirstSearch
  • KahnTopologicalSort
  • KruskalMinimumSpanningTree
  • PrimMinimumSpanningTree
  • BFSShortestPaths
  • DAGShortestPaths
  • DijkstraShortestPaths
  • BellmanFordShortestPaths
  • DFSConnectedComponents
  • BFSConnectedComponents
  • DisjointSetsConnectedComponents
  • TarjanCutVertices
  • TarjanBridges
  • TarjanStronglyConnectedComponents
  • DFSBipartitenessCheck
  • BFSBipartitenessCheck

Examples

DepthFirstSearch

#include <cstddef>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/DepthFirstSearch.h"
#include "graph/DefaultVisitor.h"
#include "graph/Color.h"

class CustomVisitor : public graph::DefaultVisitor {
public:
    template <typename Graph>
    void onDiscoverVertex(Graph &g, typename Graph::Vertex v) {
        // ...
    }
};

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(0, 2);

    std::unordered_map<Vertex, graph::Color> colors;
    CustomVisitor visitor;

    graph::DepthFirstSearch(g, &colors)(visitor);

    return 0;
}

BreadthFirstSearch

#include <cstddef>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/BreadthFirstSearch.h"
#include "graph/DefaultVisitor.h"
#include "graph/Color.h"

class CustomVisitor : public graph::DefaultVisitor {
public:
    template <typename Graph>
    void onDiscoverVertex(Graph &g, typename Graph::Vertex v) {
        // ...
    }
};

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(0, 2);

    std::unordered_map<Vertex, graph::Color> colors;
    CustomVisitor visitor;

    graph::BreadthFirstSearch(g, &colors)(visitor);

    return 0;
}

KahnTopologicalSort

#include <cassert>
#include <cstddef>
#include <vector>

#include "graph/DefaultDigraph.h"
#include "graph/KahnTopologicalSort.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(0, 2);

    std::vector<Vertex> sorted = graph::KahnTopologicalSort(g)();

    assert(sorted == std::vector<Vertex>{0, 1, 2});

    return 0;
}

KruskalMinimumSpanningTree

#include <cassert>
#include <cstddef>
#include <unordered_set>

#include "graph/DefaultDigraph.h"
#include "graph/Empty.h"
#include "graph/KruskalMinimumSpanningTree.h"

int main() {
    using Vertex = size_t;
    
    struct EdgeProps {
        int weight;
    };

    graph::DefaultDigraph<Vertex, graph::Empty, EdgeProps> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1, {1}); g.addEdge(1, 0, {1});
    g.addEdge(1, 2, {2}); g.addEdge(2, 1, {2});
    g.addEdge(0, 2, {4}); g.addEdge(2, 0, {4});

    std::unordered_set<Graph::Edge> mstEdges;

    graph::KruskalMinimumSpanningTree(g, g[&EdgeProps::weight], &mstEdges)();

    int weight = 0;
    for (auto e : mstEdges) {
        weight += g[e].weight;
    }
    assert(weight == 3);

    return 0;
}

PrimMinimumSpanningTree

#include <cassert>
#include <cstddef>
#include <optional>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/Empty.h"
#include "graph/PrimMinimumSpanningTree.h"

int main() {
    using Vertex = size_t;
    
    struct EdgeProps {
        int weight;
    };

    graph::DefaultDigraph<Vertex, graph::Empty, EdgeProps> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1, {1}); g.addEdge(1, 0, {1});
    g.addEdge(1, 2, {2}); g.addEdge(2, 1, {2});
    g.addEdge(0, 2, {4}); g.addEdge(2, 0, {4});

    Vertex s = 0;

    std::unordered_map<Vertex, int> dists;
    std::unordered_map<Vertex, std::optional<Vertex>> preds;

    graph::PrimMinimumSpanningTree(g, s, g[&EdgeProps::weight], &dists, &preds)();

    int weight = 0;
    for (Vertex v : g.vertices()) {
        weight += dists[v];
    }
    assert(weight == 3);

    return 0;
}

BFSShortestPaths

#include <cassert>
#include <cstddef>
#include <optional>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/BFSShortestPaths.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(0, 2);

    Vertex s = 0;

    std::unordered_map<Vertex, size_t> dists;
    std::unordered_map<Vertex, std::optional<Vertex>> preds;

    graph::BFSShortestPaths(g, s, &dists, &preds)();

    assert(dists[0] == 0);
    assert(dists[1] == 1);
    assert(dists[2] == 1);

    assert(preds[0] == std::nullopt);
    assert(preds[1] == 0);
    assert(preds[2] == 0);

    return 0;
}

DAGShortestPaths

#include <cassert>
#include <cstddef>
#include <optional>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/Empty.h"
#include "graph/DAGShortestPaths.h"

int main() {
    using Vertex = size_t;

    struct EdgeProps {
        int weight;
    };

    graph::DefaultDigraph<Vertex, graph::Empty, EdgeProps> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1, {10});
    g.addEdge(1, 2, {100});
    g.addEdge(0, 2, {1000});

    Vertex s = 0;

    std::unordered_map<Vertex, int> dists;
    std::unordered_map<Vertex, std::optional<Vertex>> preds;

    graph::DAGShortestPaths(g, s, g[&EdgeProps::weight], &dists, &preds)();

    assert(dists[0] == 0);
    assert(dists[1] == 10);
    assert(dists[2] == 110);

    assert(preds[0] == std::nullopt);
    assert(preds[1] == 0);
    assert(preds[2] == 1);

    return 0;
}

DijkstraShortestPaths

#include <cassert>
#include <cstddef>
#include <optional>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/Empty.h"
#include "graph/DijkstraShortestPaths.h"

int main() {
    using Vertex = size_t;

    struct EdgeProps {
        int weight;
    };

    graph::DefaultDigraph<Vertex, graph::Empty, EdgeProps> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1, {10});
    g.addEdge(1, 2, {100});
    g.addEdge(0, 2, {1000});

    Vertex s = 0;

    std::unordered_map<Vertex, int> dists;
    std::unordered_map<Vertex, std::optional<Vertex>> preds;

    graph::DijkstraShortestPaths(g, s, g[&EdgeProps::weight], &dists, &preds)();

    assert(dists[0] == 0);
    assert(dists[1] == 10);
    assert(dists[2] == 110);

    assert(preds[0] == std::nullopt);
    assert(preds[1] == 0);
    assert(preds[2] == 1);

    return 0;
}

BellmanFordShortestPaths

#include <cassert>
#include <cstddef>
#include <optional>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/Empty.h"
#include "graph/BellmanFordShortestPaths.h"

int main() {
    using Vertex = size_t;

    struct EdgeProps {
        int weight;
    };

    graph::DefaultDigraph<Vertex, graph::Empty, EdgeProps> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1, {-10});
    g.addEdge(1, 2, {-100});
    g.addEdge(0, 2, {-1000});

    Vertex s = 0;

    std::unordered_map<Vertex, int> dists;
    std::unordered_map<Vertex, std::optional<Vertex>> preds;

    graph::BellmanFordShortestPaths(g, s, g[&EdgeProps::weight], &dists, &preds)();

    assert(dists[0] == 0);
    assert(dists[1] == -10);
    assert(dists[2] == -1000);

    assert(preds[0] == std::nullopt);
    assert(preds[1] == 0);
    assert(preds[2] == 0);

    return 0;
}

DFSConnectedComponents

#include <cassert>
#include <cstddef>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/DFSConnectedComponents.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1); g.addEdge(1, 0);

    std::unordered_map<Vertex, size_t> componentNumbers;

    size_t componentCount = graph::DFSConnectedComponents(g, &componentNumbers)();

    assert(componentCount == 2);

    assert(componentNumbers[0] == componentNumbers[1]);
    assert(componentNumbers[2] != componentNumbers[0]);
    assert(componentNumbers[2] != componentNumbers[1]);

    return 0;
}

BFSConnectedComponents

#include <cassert>
#include <cstddef>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/BFSConnectedComponents.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1); g.addEdge(1, 0);

    std::unordered_map<Vertex, size_t> componentNumbers;

    size_t componentCount = graph::BFSConnectedComponents(g, &componentNumbers)();

    assert(componentCount == 2);

    assert(componentNumbers[0] == componentNumbers[1]);
    assert(componentNumbers[2] != componentNumbers[0]);
    assert(componentNumbers[2] != componentNumbers[1]);

    return 0;
}

DisjointSetsConnectedComponents

#include <cassert>
#include <cstddef>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/DisjointSetsConnectedComponents.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1); g.addEdge(1, 0);

    std::unordered_map<Vertex, Vertex> representativeVertices;

    size_t componentCount =
        graph::DisjointSetsConnectedComponents(g, &representativeVertices)();

    assert(componentCount == 2);

    assert(representativeVertices[0] == representativeVertices[1]);
    assert(representativeVertices[2] != representativeVertices[0]);
    assert(representativeVertices[2] != representativeVertices[1]);

    return 0;
}

TarjanCutVertices

#include <cassert>
#include <cstddef>
#include <unordered_set>

#include "graph/DefaultDigraph.h"
#include "graph/TarjanCutVertices.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1); g.addEdge(1, 0);
    g.addEdge(1, 2); g.addEdge(2, 1);

    std::unordered_set<Vertex> cutVertices;
    
    graph::TarjanCutVertices(g, &cutVertices)();
    
    assert(cutVertices == std::unordered_set<Vertex>{1});

    return 0;
}

TarjanBridges

#include <cassert>
#include <cstddef>

#include "graph/DefaultDigraph.h"
#include "graph/TarjanBridges.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);
    g.addVertex(3);

    g.addEdge(0, 1); g.addEdge(1, 0);
    g.addEdge(0, 2); g.addEdge(2, 0);
    g.addEdge(1, 2); g.addEdge(2, 1);
    g.addEdge(2, 3); g.addEdge(3, 2);

    auto isBridge = graph::TarjanBridges(g)();

    assert(isBridge(0, 1) == false);
    assert(isBridge(0, 2) == false);
    assert(isBridge(1, 2) == false);
    assert(isBridge(2, 3) == true);

    return 0;
}

TarjanStronglyConnectedComponents

#include <cassert>
#include <cstddef>
#include <unordered_map>

#include "graph/DefaultDigraph.h"
#include "graph/TarjanStronglyConnectedComponents.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);

    g.addEdge(0, 1);
    g.addEdge(1, 0);
    g.addEdge(0, 2);

    std::unordered_map<Vertex, size_t> sccNumbers;

    size_t sccCount = graph::TarjanStronglyConnectedComponents(g, &sccNumbers)();

    assert(sccCount == 2);
    
    assert(sccNumbers[0] == sccNumbers[1]);
    assert(sccNumbers[2] != sccNumbers[0]);
    assert(sccNumbers[2] != sccNumbers[1]);

    return 0;
}

DFSBipartitenessCheck

#include <cassert>
#include <cstddef>

#include "graph/DefaultDigraph.h"
#include "graph/DFSBipartitenessCheck.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);

    g.addEdge(0, 1); g.addEdge(1, 0);

    assert(graph::DFSBipartitenessCheck(g)() == true);

    return 0;
}

BFSBipartitenessCheck

#include <cassert>
#include <cstddef>

#include "graph/DefaultDigraph.h"
#include "graph/BFSBipartitenessCheck.h"

int main() {
    using Vertex = size_t;

    graph::DefaultDigraph<Vertex> g;

    g.addVertex(0);
    g.addVertex(1);

    g.addEdge(0, 1); g.addEdge(1, 0);

    assert(graph::BFSBipartitenessCheck(g)() == true);

    return 0;
}

License

Graph is licensed under the MIT license.

About

No description, website, or topics provided.

Resources

Readme

License

MIT license
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages