Graphs are ubiquitous sctructures in computer science, and are neccesary tools for solving problems in fields ranging from network flow to GPS systems. However, in C++, a language of choice for many developers, a definitive data type for the graph does not exist. For this reason, this library provides various necessary prebuilt tools for graphs and graph algorithms.
Graphify is a header only library, meaning compiling with SOs or compilation units is not necessary. To create code using the library, simply include a submodule of your choice while using the proper namespace. Finally, please note before proceeding that Graphify's Graph datatypes are wrappers of C++'s existing map datatype.
#include "Graph/Graph.hpp"
#include "Node/Node.hpp"
int main(){
Node<char>* a = new Node<char>();
a->data = 'a';
Node<char>* b = new Node<char>();
b->data = 'b';
Graph<int> graph;
graph.addNode(a, {b}); // connect a to specified list of nodes
return 0;
}
To run your program, compile the file as normal while specifying the directory of the Graphify library. Be sure to set the C++ version to 17.
g++ main.cpp -O2 -Wall -o main.o -I Graphify -std=c++17
- Graph (unweighted)
- Out-degree/In-degree
- Initialize graph as complete
- Transpose
- Convert to edge list
- Check if directed
- Check if bi-partite (2-colorable)
- Check if Eulerian circut exists
- Check if Eulerian path exists
- Weighted Graph
- Out-degree/In-degree
- Initialize graph as complete
- Transpose
- Convert to Graph (unweighted), weighted adjacency matrix, weighted edge list
- Flow Graph
- In-degree/Out-degree
- Transpose
- Is full
- Edge List (unweighted) a. Combine with another edge list
- Weighted Edge List
- Combine with another edge list
- Minimum edge weight
- Weighted Adjacency Matrix
- Traversals (Unweighted)
- Valid traversal methods
- Number of connected components
- Shortest path between a start & end node
- Maximum component
- Minimum component
- Number of bridges
- Number of articulation points
- Top sort (traversal pts as input)
- Kahn top sort
- Tarjan's strongly connected components
- Kosaraju's strongly connected components
- Is DAG
- Weighted Traversals
- Valid traversal methods
- DAG shortest path
- DAG longest path
- Djikstra's shortest path
- Alpha start shortest path
- Bellman-Ford shortest path
- Floyd-Warshall shortest path
- Johnson shortest path
- Travelling salesman problem
- Kruskal minimum spanning tree
- Prim minimum spanning tree
- Flow Traversals
- Valid traversal methods
- Ford-Fulkerson maximum flow
- Edmonds-Karp flag
- Dinic maximum flow