Graph Algorithms API reference¶
This page contains API reference to the implementation of different graph algorithms. More algorithm implementation on the way.
Distance Algorithms¶
Implements algorithms to compute distance between nodes in a graph.
Defines
-
GRAPHS_DISTANCE_H
¶
Functions
-
std::vector<int>
dijkstra_shortest_distance
(graph &graph, int source_node)¶ Implements dijsktra’s shortest path algorithm to find the shortest distance between source_node and all other nodes in the graph.
- Return
[vector<int>]: shortest path between source_node and all other nodes
- Parameters
[graph]
: graph: input graph of any type: edgeList, adjacencyList, adjacencyMatrix[int]
: source_node: the nodes for which shortest path to all other nodes is to be computed
-
int **
all_pair_shortest_path
(graph &graph)¶ Computes all pair shortest path using floyd’s all path shortest path algorithm. As long as there is no cycle, this algorithm works fine. reference: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm.
- Return
[int**] distances: 2D array containing distance between each pair of nodes
- Parameters
[graph]
: graph: input graph of any type: edgeList, adjacencyList, adjacencyMatrix
-
std::vector<int>
bellman_ford
(graph &graph, const int source_node)¶ Implements Bellman Ford algorithm to find shortest distances when the edges are negative Note: Does not work when the total weight of the cycle is negative.
- Return
[std::vector<int>] distances: shortest distance from source_node to all other nodes
- Parameters
[graph]
: graph: input graph of any type: edgeList, adjacencyList, adjacencyMatrix[int]source_node
: The source node from which shortest distance is to be computed
- Exceptions
std::invalid_argument
: error if the graph is not weighted.
Spanning Trees¶
Implements algorithms to compute minimum spanning tree for graphs.
Functions
-
int
mst_kruskal
(graph &graph)¶ implements kruskal’s minimum spanning tree Keep adding minimum edges and don’t form cycle. Requires weighted edge list
- Return
[int] cost of minimum spanning tree computed from the input graph
- Parameters
graph
: input graph of any type: edgeList, adjacencyList, adjacencyMatrix
-
int
mst_prim
(graph &graph)¶ implements prim’s minimum spanning tree Requires the graph to be weighted graph
- Return
[int] cost of minimum spanning tree computed from the input graph
- Parameters
graph
: input graph of any type: edgeList, adjacencyList, adjacencyMatrix
Topological Sort¶
Implements topological sort.
Defines
-
GRAPHS_TOPOLOGICAL_SORT_H
¶
Functions
-
void
topological_sort
(graph *graph, std::vector<int> &result)¶ Implements topological sort.
- Attention
If the nodes are not enumerated in 0 base, then there is segfault and allocated memory won’t be released
- Parameters
graph
: input graph of any type: edgeList, adjacencyList, adjacencyMatrixresult
: [std::vector<int>] all the nodes of the graph in topological sorted order
Traversal Algorithms¶
traverse.h implements traversal methods for graphs. It does not implement inorder, preorder and postorder traversal because they make sense only for binary trees and binary search trees
Defines
-
GRAPHS_TRAVERSE_H
¶
Functions
-
void
bfs
(graph &graph, int source_node, std::vector<int> &result)¶ Implements iterative algorithm for breadth first search traversal on a graph. For undirected graphs we have keep track of visited nodes.
- Parameters
[in] graph
: input graph on which breadth first search traversal has to be performed.[in] source_node
: the node from which to start the traversal[out] result
: the nodes of the graph in bfs order
-
void
dfs
(graph &graph, int source_node, std::vector<int> &result)¶ Implements iterative algorithm for depth first search traversal on a graph. Keep track of the visited nodes in graphs. It’s not required to keep track of visited nodes in directed graphs.
- Parameters
[in] graph
: input graph on which depth first search traversal has to be performed.[in] source_node
: the node from which to start the traversal[out] result
: the nodes of the graph in dfs order
-
void
level_order_traversal
(graph &graph, int source_node, std::vector<std::vector<int>> &result)¶ Implements iterative algorithm for level order search for a graph.
- Parameters
[in] graph
: input graph on which level order traversal has to be performed.[in] source_node
: the node from which to start the traversal[out] result
: the nodes of the graph in level order
Union Find¶
-
class
union_find
¶ Public Functions
-
union_find
(const int size)¶ construct union find object
- Parameters
[in] size
: total number of nodes/elements/objects
-
int
size
() const¶ return the size of the set
- Return
[int] returns the size of the set
-
int
find_parent
(int child)¶ determine the parent of a element
- Return
[int] the parent of the child
- Parameters
[in] child
: the item whose parent is to be determined
-
bool
join
(const int first, const int second)¶ merge/union two elements in a set.
- Return
[bool]: if the join was completed successfully or not. If two elements have same parent, merge/union can not be performed
- Parameters
firstsecond
: the items which should be merged into one subset. Note that their parents or child are also merged into the same subset
-
bool
has_same_parent
(const int first, const int second)¶ Determine if two elements have the same parent of not.
- Return
[bool]: whether two input element have same parent or not
- Parameters
[in] first[in] second
: two elements for which we determine if they have same parent or not
-