Repository files navigation

CXXGraph is a comprehensive C++ library that manages graph algorithms. This header-only library serves as an alternative to theBoost Graph Library (BGL).

CXXGraph Website

We are looking for:

• A Web Developer for the development of the CXXGraph website. All documentation is currently hosted on this GitHub page.
• Developers and Contributors to provide input. If you are new to the open-source world, we will guide you step by step!

If you are interested, please contact us atzigrazor@gmail.com or contribute to this project. We are waiting for you!

• CXXGraph
  • Introduction
  • We are Looking for...
  • Table of Contents
  • Install and Uninstall
    • Install Linux Tarballs
    • Install RPM
    • Install DEB
    • Install From Source
  • Requirements
  • How to use
  • Examples
  • Unit-Test Execution
    • Google Test Installation
    • How to Compile Test
    • How to Run Test
  • Benchmark Execution
    • Google Benchmark Installation
    • How to Compile Benchmark
    • How to Run Benchmark
    • Benchmark Results
  • Packaging
    • Tarballs
    • RPM
      • (Fedora/CentOS/RedHat)
    • DEB
      • (Debian/Ubuntu)
  • Algorithms, Classes and Network Dynamics
  • How to contribute
  • Roadmap
  • Contact
  • Support
  • References
  • Credits
  • Contributors
  • Cite Us
  • Other Details
  • Author

To install on Unix/Linux systems, execute the following from the command line:

$ sudo tar xjf CXXGraph-{version}.tar.bz2

To uninstall:

$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*

To install on Fedora/CentOS/RedHat systems, execute the following from the command line:

$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm

To uninstall:

$ sudo rpm -e CXXGraph-{version}

To install on Debian/Ubuntu systems, execute the following from the command line:

$ sudo dpkg -i CXXGraph_{version}.deb

To uninstall:

$ sudo apt-get remove CXXGraph

For self-compiled installations using CMake, execute the following from the command line once compilation is complete:

$ sudo make install

• The minimum C++ standard required isC++17
• A GCC compiler version 7.3.0 and laterOR a MSVC compiler that supports C++17

To use the librarysimply include the header fileCXXGraph.hpp, (make sure to add theinclude folder to your compiler's inlcude path).

CXXGraph revolves around the graph object which contains nodes and edges. This object can then be manipulated with a wide variety of algorithms. Please see theexamples section,examples folder andwebsite for more information

In this example, the shortest path between nodeA and nodeC is obtained using Dijkstra's algorithm.

#include<iostream>#include"CXXGraph/CXXGraph.hpp"intmain(){  CXXGraph::Node<int>nodeA("A",1);  CXXGraph::Node<int>nodeB("B",2);  CXXGraph::Node<int>nodeC("C",3);  CXXGraph::DirectedWeightedEdge<int>edge1("1", nodeA, nodeB,1);  CXXGraph::DirectedWeightedEdge<int>edge2("2", nodeB, nodeC,1);  CXXGraph::UndirectedWeightedEdge<int>edge3("3", nodeA, nodeC,6);  CXXGraph::T_EdgeSet<int> edgeSet;  edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge1));  edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge<int>>(edge2));  edgeSet.insert(make_shared<CXXGraph::UndirectedWeightedEdge<int>>(edge3));  CXXGraph::Graph<int>graph(edgeSet);  CXXGraph::DijkstraResult res = graph.dijkstra(nodeA, nodeC);for(auto node_user_id : res.path){    std::cout << node_user_id <<'\n';  }}

See more examples in theexamples folder.

The Unit-Test requires CMake 3.9 and later, and theGoogleTest library.

GoogleTest

git clone https://github.com/google/googletest.gitcd googletest# Main directory of the cloned repositorymkdir -p build# Create a directory to hold the build outputcd buildcmake ..# Generate native build scripts for GoogleTestmake# Compilesudo make install# Install in /usr/local/ by default

From the base directory:

mkdir -p build# Create a directory to hold the build outputcd build# Enter the build foldercmake -DTEST=ON ..# Generate native build scripts for GoogleTest,make# Compile

After the build has compiled, run the "test_exe" executable in the "build" directory with the following command:

./test_exe

The Benchmark requires CMake 3.9 and later, theGoogleTest library, and theGoogle Benchmark library.

Google Benchmark

# Check out the library$ git clone https://github.com/google/benchmark.git# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory$ git clone https://github.com/google/googletest.git benchmark/googletest# Go to the library's root directory$cd benchmark# Make a build directory to place the build output$ cmake -E make_directory"build"# Generate the build system files with CMake$ cmake -E chdir"build" cmake -DCMAKE_BUILD_TYPE=Release ../# If starting with CMake 3.13, you can use the following:# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"# Build the library$ cmake --build"build" --config Release# Install the library$ sudo cmake --build"build" --config Release --target install

From the base directory:

mkdir -p build# Create a directory to hold the build outputcd build# Enter the build foldercmake -DBENCHMARK=ON ..# Generate native build scripts for Google Benchmarkmake# Compile

After the build has compiled, run the "benchmark" executable in the "build" directory with the following command:

./benchmark

You can check the benchmark result using thislink.

To create a tarball package, execute the following from the command line:

# Enter Packaging Directory$cd packaging# Execute the script to generate tarballs$ ./tarballs.sh

To create an RPM package, execute the following from the command line:

# Enter Packaging Directory$cd packaging/rpm# Execute the script to generate tarballs$ ./make_rpm.sh

To create a deb package, execute the following from the command line:

# Enter Packaging Directory$cd packaging/deb# Execute the script to generate tarballs$ ./make_deb.sh

Both theDoxygen documentation and thewebsite provide implementation and explanation information on theclasses andalgorithms of CXXGraph.

The Classes Explanation can be found in theclasses section of theDoxygen documentation.

More information can be foundhere.

• Adjacency Matrix
• Degree Matrix
• Laplacian Matrix
• Transition Matrix

The following is a list of all the implemented algorithms, more information on the algorithms can be foundhere.

• Breadth First Search (BFS)
• Depth First Search (DFS)
• Best First Search (a heuristic-based traversal)
• Bron–Kerbosch Algorithm (for finding maximal cliques; DFS-based)

• Dijkstra's Algorithm (single-source shortest path, non-negative weights)
• Bellman-Ford Algorithm (handles negative weights)
• Floyd–Warshall Algorithm (all-pairs shortest path)
• Dial's Algorithm (optimized Dijkstra for small integer weights)

• Prim's Algorithm
• Kruskal's Algorithm
• Borůvka's Algorithm

• Ford–Fulkerson Algorithm (maximum flow)
• Hopcroft–Karp Algorithm (maximum bipartite matching)

• Kosaraju's Algorithm (strongly connected components in directed graphs)
• Tarjan's Algorithm (strongly connected components or articulation points)
• Connectivity (general graph connectivity checking)
• Cycle Detection

• Topological Sort
• Kahn’s Algorithm (BFS-based topological sorting)
• Tarjan’s Algorithm (DFS-based topological sorting)

• Hierholzer's Algorithm

• Transitive Reduction (reduce graph to essential edges while preserving reachability)

• Welsh–Powell Coloring Algorithm

• Vertex-Cut
• Edge Balanced Vertex-Cut
• Edge Balanced Vertex-Cut based on thispaper
• Greedy Vertex-Cut
• High Degree Replicated First

If you want to give your support you can create apull request or report anissue.If you want to change the code, fix an issue, or implement a new feature please read ourCONTRIBUTING Guide.

If you want to discuss new features or you have any questions or suggestions about the library, please open aDiscussion or simply chat on

E-mail :zigrazor@gmail.com

GitHub Profile

To support me, add aStar to the project orfollow me

To stay updated,watch the project

We are referenced by:

• awesome-hpp
• cppreference.com
• awesome-cpp

Thanks to the community ofTheAlgorithms for some algorithm inspiration.

Thanks toGeeksForGeeks for some algorithm inspiration.

Thank you to all the people who have already contributed to CXXGraph!

• Ruizhe Wang, Meng Xu, and N. Asokan. 2024. SeMalloc: Semantics-Informed Memory Allocator. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security (CCS '24). Association for Computing Machinery, New York, NY, USA, 1375–1389.https://doi.org/10.1145/3658644.3670363

If you use this software please follow theCITATION instructions.Thank you!

We participated in Hacktoberfest 2021, 2022 and 2023. Thank you to all the contributors!

View theEstimated Value of the Project

@ZigRazor