GitHub - ZigRazor/CXXGraph: Header-Only C++ Library for Graph Representation and Algorithms (original) (raw)

CXXGraph

Introduction

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

CXXGraph Website

We are Looking for

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 at zigrazor@gmail.com or contribute to this project. We are waiting for you!

Table of Contents

• 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

Install and Uninstall

Install Linux Tarballs

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*

Install RPM

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}

Install DEB

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

Install From Source

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

$ sudo make install

Prerequisites

• The minimum C++ standard required is C++17
• A GCC compiler version 7.3.0 and later OR a MSVC compiler that supports C++17

How to use

To use the library simply include the header file CXXGraph.hpp, (make sure to add the include 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 the examples section, examples folder and website for more information

Examples

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

#include #include "CXXGraph/CXXGraph.hpp"

int main(){ CXXGraph::Node nodeA("A", 1); CXXGraph::Node nodeB("B", 2); CXXGraph::Node nodeC("C", 3);

CXXGraph::DirectedWeightedEdge edge1("1", nodeA, nodeB, 1); CXXGraph::DirectedWeightedEdge edge2("2", nodeB, nodeC, 1); CXXGraph::UndirectedWeightedEdge edge3("3", nodeA, nodeC, 6);

CXXGraph::T_EdgeSet edgeSet; edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge>(edge1)); edgeSet.insert(make_shared<CXXGraph::DirectedWeightedEdge>(edge2)); edgeSet.insert(make_shared<CXXGraph::UndirectedWeightedEdge>(edge3));

CXXGraph::Graph 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 the examples folder.

Unit-Test Execution

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

Install GoogleTest

GoogleTest

git clone https://github.com/google/googletest.git cd googletest # Main directory of the cloned repository mkdir -p build # Create a directory to hold the build output cd build cmake .. # Generate native build scripts for GoogleTest make # Compile sudo make install # Install in /usr/local/ by default

How to Compile GoogleTest

From the base directory:

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

How to Run GoogleTest

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

./test_exe

Benchmark Execution

The Benchmark requires CMake 3.9 and later, the GoogleTest library, and the Google Benchmark library.

Install Google Benchmark

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

How to Compile Google Benchmark

From the base directory:

mkdir -p build # Create a directory to hold the build output cd build # Enter the build folder cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark make # Compile

How to Run Google Benchmark

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

./benchmark

Benchmark Results

You can check the benchmark result using this link.

Packaging

Tarballs

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

RPM

(Fedora/CentOS/RedHat)

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

DEB

(Debian/Ubuntu)

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

Algorithms, Classes and Network Dynamics

Both the Doxygen documentation and the website provide implementation and explanation information on the classes and algorithms of CXXGraph.

Classes

The Classes Explanation can be found in the classes section of the Doxygen documentation.

Network Dynamics

More information can be found here.

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

Algorithms

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

Graph Traversal Algorithms

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

Shortest Path Algorithms

• 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)

Minimum Spanning Tree Algorithms

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

Network Flow Algorithms

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

Connectivity and Component Detection

• 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 & Dependency Sorting

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

Eulerian Path/Cycle Detection

• Hierholzer's Algorithm

Graph Transformation

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

Graph Coloring Algorithms

• Welsh–Powell Coloring Algorithm

Partition Algorithms

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

How to contribute

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

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

Roadmap

Stars History

Contact

E-mail : zigrazor@gmail.com

GitHub Profile

Support

To support me, add a Star to the project or follow me

To stay updated, watch the project

References

We are referenced by:

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

Credits

Thanks to the community of TheAlgorithms for some algorithm inspiration.

Thanks to GeeksForGeeks for some algorithm inspiration.

Contributors

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

Cited By

• 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

Cite Us

If you use this software please follow the CITATION instructions. Thank you!

Other Details

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

View the Estimated Value of the Project

Author

@ZigRazor