CXXGraph
CXXGraph
Table of Contents
 CXXGraph
Introduction
CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".
Algorithm Explanation
Dijkstra
Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path) Dijkstra's Algorithm is used to find the shortest path from a source node to all other reachable nodes in the graph. The algorithm initially assumes all the…
Table of Contents

CXXGraph
 Table of Contents
 Introduction
 Algorithm Explanation
 Partition Algorithm Explanation
 VertexCut
 Classes Explanation
 Requirements
 How to use
 UnitTest 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
 Packaging
 Tarballs
 RPM
 DEB
 Install and Uninstall
 Install Linux Tarballs
 Install RPM
 Install DEB
 Install From Source
 How to contribute
 Site
 Contact
 Support
 References
 Credits
 We are Looking for...
Introduction
CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".
Algorithm Explanation
Dijkstra
Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path)
Dijkstra's Algorithm is used to find the shortest path from a source node to all other reachable nodes in the graph. The algorithm initially assumes all the nodes are unreachable from the given source node so we mark the distances of all nodes as infinity.
(infinity) from source node (INF / infinity denotes unable to reach).
Dial
Dial specialization of dijkstra’s algorithm.
When edge weights are small integers (bounded by a parameter C), specialized queues which take advantage of this fact can be used to speed up Dijkstra's algorithm. The first algorithm of this type was Dial's algorithm (Dial 1969) for graphs with positive integer edge weights, which uses a bucket queue to obtain a running time
O(E+VC).(source wikipedia)
Below is complete algorithm:
 Maintains some buckets, numbered 0, 1, 2,…,wV.
 Bucket k contains all temporarily labeled nodes with distance equal to k.
 Nodes in each bucket are represented by list of vertices.
 Buckets 0, 1, 2,..wV are checked sequentially until the first nonempty bucket is found. Each node contained in the first nonempty bucket has the minimum distance label by definition.
 One by one, these nodes with minimum distance label are permanently labeled and deleted from the bucket during the scanning process.
 Thus operations involving vertex include:
 Checking if a bucket is empty
 Adding a vertex to a bucket
 Deleting a vertex from a bucket.
 The position of a temporarily labeled vertex in the buckets is updated accordingly when the distance label of a vertex changes.
 Process repeated until all vertices are permanently labeled (or distances of all vertices are finalized).
At this link you can find a stepbystep illustrations.
BFS
(Breadth First Search)
Breadth First Search Algorithm(Breadth First Search)
Breadth First Search, also quoted as BFS, is a Graph Traversal Algorithm. Time Complexity O(V + E) where V are the number of vertices and E are the number of edges in the graph.
Applications of Breadth First Search are :
 Finding shortest path between two vertices say u and v, with path length measured by number of edges (an advantage over depth first search algorithm)
 FordFulkerson Method for computing the maximum flow in a flow network.
 Testing bipartiteness of a graph.
 Cheney's Algorithm, Copying garbage collection.
And there are many more...
DFS
(Depth First Search)
Depth First Search Algorithm (Depth First Search)
Depth First Search, also quoted as DFS, is a Graph Traversal Algorithm. Time Complexity O(V + E) where V is number of vertices and E is number of edges in graph.
Application of Depth First Search are:
 Finding connected components
 Finding 2(edge or vertex)connected components.
 Finding 3(edge or vertex)connected components.
 Finding the bridges of a graph.
 Generating words in order to plot the limit set of a group.
 Finding strongly connected components.
And there are many more...
Cycle Detection
The existence of a cycle in directed and undirected graphs can be determined by whether depthfirst search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an nvertex graph, since at most n − 1 edges can be tree edges.
Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.
For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing largescale graphs using a distributed graph processing system on a computer cluster (or supercomputer).
Applications of cycle detection include the use of waitfor graphs to detect deadlocks in concurrent systems.
WORK IN PROGRESS
Partition Algorithm Explanation
VertexCut
A vertexcut partitioning divides edges of a graph into equal size partitions. The vertices that hold the endpoints of an edge are also placed in the same partition as the edge itself. However, the vertices are not unique across partitions and might have to be replicated (cut), due to the distribution of their edge across different partitions.
Replication factor quantifies how many vertexes are replicated over computers compared with the the number of vertexes of the original input graph.
Greedy VertexCut
This Algorithm is a simple vertexcut in RoundRobin fashion.
It takes the original graph edges and assign them to the partitions, dividing it in equal(or similar) size. This algorithm does not take care of optimization in vertex replication ( Replication Factor) but only balance the edge in the partitions.
Classes Explanation
The Classes Explanation can be found in the Doxygen Documentation, in the Classes Section
Requirements
The minimun C++ standard required is C++17 and a G++ compiler version greater than 7.3.0.
How to use
The use of the library is very simple, just put the header file where you need!
UnitTest Execution
The UnitTest required the CMake version greater than 3.9 and the google test library.
Google Test Installation
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository.
mkdir build # Create a directory to hold the build output.
cd build
cmake .. # Generate native build scripts for GoogleTest.
make
sudo make install # Install in /usr/local/ by default
How to Compile Test
 If not exist create a directory "build" under the base directory.
 Enter the directory
 execute command
cmake ..
 if all is succesfull execute the command
make
How to Run Test
After the compilation, you can run the executable that is under the "build" directory with the name "test_exe", with the simple command ./test_exe
.
Benchmark Execution
The Benchmark required the CMake version greater than 3.9 and the google test and the google benchmark library.
Google Benchmark Installation
# Check out the library.
$ git clone https://github.com/google/benchmark.git
# Benchmark requires Google Test as a dependency. Add the source tree as a subdirectory.
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library root directory
$ cd benchmark
# Make a build directory to place the build output.
$ cmake E make_directory "build"
# Generate build system files with cmake.
$ cmake E chdir "build" cmake DCMAKE_BUILD_TYPE=Release ../
# or, starting with CMake 3.13, use a simpler form:
# cmake DCMAKE_BUILD_TYPE=Release S . B "build"
# Build the library.
$ cmake build "build" config Release
# install library
$ sudo cmake build "build" config Release target install
How to Compile Benchmark
 If not exist create a directory "build" under the base directory.
 Enter the directory
 execute command
cmake ..
 if all is succesfull execute the command
make
How to Run Benchmark
After the compilation, you can run the executable that is under the "build" directory with the name "benchmark", with the simple command ./benchmark
.
Benchmark Results
You can check benchmark result at this link
Packaging
Tarballs
To create tarballs package you need to follow the following steps:
# Enter Packaging Directory
$ cd packaging
# execute the script to generate tarballs
$ ./tarballs.sh
RPM
(Fedora/CentOS/RedHat)
To create rpm package you need to follow the following steps:
# Enter Packaging Directory
$ cd packaging/rpm
# execute the script to generate tarballs
$ ./make_rpm.sh
DEB
(Debian/Ubuntu)
To create deb package you need to follow the following steps:
# Enter Packaging Directory
$ cd packaging/deb
# execute the script to generate tarballs
$ ./make_deb.sh
Install and Uninstall
Install Linux Tarballs
On Unix/Linux system you need to execute the following command to install:
$ sudo tar xjf CXXGraph{version}.tar.bz2
to uninstall:
$ sudo rm f /usr/include/Graph.hpp /usr/include/CXXGraph*
Install RPM
On Fedora/CentOS/RedHat system you need to execute the following command to install:
$ sudo rpm ivh CXXGraph{version}.noarch.rpm
to uninstall:
$ sudo rpm e CXXGraph{version}
Install DEB
On Debian/Ubuntu system you need to execute the following command to install:
$ sudo dpkg i CXXGraph_{version}.deb
to uninstall:
$ sudo aptget remove CXXGraph
Install From Source
You can install from source the library using CMake. After the compilation phase, you can use:
$ sudo make install
to install the library.
How to contribute
If you want give your support you can create a pull request or report an issue .
If you want to change the code, or fix issue, or implement a new feature please read our CONTRIBUTING Guide
Site
Contact
EMail : zigrazor@gmail.com
Support
To support me just add Star the project or follow me
To get updated watch the project
References
We are referenced by:
Credits
Thanks to the community of TheAlgorithms for some algorithms ispiration.
Thanks to GeeksForGeeks for some algorithms inspiration.
We are Looking for...
We are looking for developers and committer, also at first experience, we will guide you step by step to the opensource world!
If you are interested, please contact us at zigrazor@gmail.com or contribute to this project. We are waiting for you!
Discussion (0)