- This project implements various graph algorithms in C++. The algorithms are implemented in the
Algorithms
class and are used to perform operations on instances of theGraph
class. - The graph is undirected by default in the constructor, if we want to state that the graph is directed we will type
Graph g(true);
or use thesetIsDirected
method in Graph.cpp
isConnected(Graph graph)
: Checks if theres a vertex that can reach all other vertices.shortestPath(Graph& graph, int start, int end)
: Finds the shortest path between two vertices using BFS, Dijkstra or Bellman-Ford algorithm, will return the path or No path found.isContainsCycle(Graph& graph)
: Checks if the graph contains a cycle using DFS, returns any cycle there is, "0" if there isnt.findCycle(Graph& graph)
: A helper function to find a cycle in the graph.isBipartite(Graph& graph)
: Checks if the graph is bipartite, if so, it will return the two sets.negativeCycle(Graph& graph)
: Checks if the graph contains a negative cycle and returns "Negative cycle detected" if there is one, and "Graph does not contain a negative cycle" otherwise.
The project includes a Makefile for easy compilation and running of the code. Here are some commands you can use:
make run
: Compiles the code and runs the demo.make demo
: Compiles the code for the demo.make test
: Compiles the code for the tests.make tidy
: Runs clang-tidy on the source files to check for code quality issues.make valgrind
: Runs valgrind on the demo and test executables to check for memory leaks.make clean
: Removes all compiled files.
The project includes a test file that contains a lot of tests to check the algorithms on directed/undirected graphs with negative weights/no weights/positive weights.