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

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

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

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

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

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