Graphs can be represented in three different ways. This library implements all of the three different ways of representing graphs.

Data Structures API reference

Graph(Pure Abstract Class)

class graph

Base class of all other graph data structures: edgeList, adjacencyMatrix, adjacencyList. This is a pure abstract class and is not instantiatable. However, it can be used to point derived classes.

Note: No self loop is allowed and the nodes are enumerated using 0 base. Users not using 0 base for enumeration might experience undefined behavior.

Also, all the data structures have same interface which makes it easy to switch the underlying data structures All algorithms have data structure agnostic implementation. You can pass into them any type of graph

Subclassed by adjacencyList, adjacencyMatrix, edgeList

Public Functions

bool add_edge(std::vector<int> edge)

add edge in the graph. Does nothing if the edge already exists.

Return

[bool] true if the edges were successfully added to the graph, false otherwise. If the edge was already present in the graph, it returns false

Exceptions

• invalid_argument: exception if the size of the edge is not 2 or 3.

bool remove_edge(const std::vector<int> &edge)

See

remove_edge(const int start, const int end)

int **get_adjacentMatrix()

computes adjacency Matrix of the graph. Note: Computation is not required if the data structure is adjacencyMatrix

Return

[int**] adjacencyMatrix of a graph which is a pointer to 2D int array

std::unordered_map<int, std::vector<int>> get_adjacentList()

computes adjacent list of the graph. Note: Computation is not required if the data structure is adjacencyList

Return

[std::unordered_map<int, std::vector<int>>] adjacencyMatrix of a graph which is a pointer to 2D int array

std::vector<std::vector<int>> get_edges()

computes edge list of the graph. Note: Computation is not required if the data structure is edgeList

Return

[std::vector<std::vector<int>>] adjacencyMatrix of a graph which is a pointer to 2D int array

int *get_indegree()

computes indegree of the nodes in the graph.

Return

[int*] pointer to 1D int array of size the number of nodes in the graph

int get_num_nodes() const

returns the number of nodes in the graph

Return

[int*] pointer to 1D int array of size the number of nodes in the graph

Ajdacency List

class adjacencyList : public graph

Implements data structure for representation of graphs as adjacency list. For each vertex, we have it’s list of neighbors. Currently the edges represented by adjacencyList is only unweighted edges.

Public Functions

bool add_edge(std::vector<int> edge)

add edge in the graph. Does nothing if the edge already exists.

Return

[bool] true if the edges were successfully added to the graph, false otherwise. If the edge was already present in the graph, it returns false

Exceptions

• invalid_argument: exception if the size of the edge is not 2 or 3.

bool remove_edge(const std::vector<int> &edge) override

See

remove_edge(const int start, const int end)

int **get_adjacentMatrix() override

computes adjacency Matrix of the graph. Note: Computation is not required if the data structure is adjacencyMatrix

Return

[int**] adjacencyMatrix of a graph which is a pointer to 2D int array

std::vector<std::vector<int>> get_edges() override

computes edge list of the graph. Note: Computation is not required if the data structure is edgeList

Return

[std::vector<std::vector<int>>] adjacencyMatrix of a graph which is a pointer to 2D int array

int *get_indegree() override

computes indegree of the nodes in the graph.

Return

[int*] pointer to 1D int array of size the number of nodes in the graph

int get_num_nodes() const override

returns the number of nodes in the graph

Return

[int*] pointer to 1D int array of size the number of nodes in the graph

Ajdacency Matrix

class adjacencyMatrix : public graph

Implements data structure for representation of graphs as adjacency matrix.

Public Functions

adjacencyMatrix(const int num_nodes, const bool directed = true)

default constructor for adjacency matrix

Return

void

Parameters

• [int]: num_nodes the maximum number of nodes that will be in the graph

• [bool]: directed is the graph directed or not?

bool is_new_edge(const int start, const int end)

is the edge with given start and end node valid? Does it already exist?

Return

[bool] true if the edge can be added to the graph because it is valid and does not already exist

Parameters

• [int]: start, end: the start and end node of the edge

bool add_edge(const int start, const int end, const int weight = 0) override

given start, end and optionally weight describing an edge, insert it into the graph

Return

[bool] was the edge successfully inserted into the graph

Parameters

• [intintint: = 0] start, end, weight: parameters describing an edge(start_node, end_node, weight)

bool add_edge(std::vector<int> &&edge)

given a reference to std::vector<int> describing an edge, insert it into the graph

Return

[bool] was the edge successfully inserted into the graph

Parameters

• [std::vector<int>&]: edge: an edge description (start_node, end_node, (optionally) weight)

bool remove_edge(const std::vector<int> &edge) override

See

remove_edge(const int start, const int end)

int **get_adjacentMatrix() const

returns the adjacency_matrix

Return

[**int] adjacency_matrix

int get_num_nodes() const final

returns the number of nodes in the graph

Return

[int] the number of nodes in the graph

int *get_indegree() final

compute indegree for all the nodes in the graph

Return

[int*] indegree for all the nodes

Edge List

class edgeList : public graph

Public Functions

bool add_edge(std::vector<int> edge) override

add edge in the graph. Does nothing if the edge already exists It is the core function used by every other method that adds edges into the graph.

Return

[bool] true if the edges were successfully added to the graph, false otherwise. If the edge was already present in the graph, it returns false

bool remove_edge(const std::vector<int> &edge) override

See

remove_edge(const int start, const int end)

int **get_adjacentMatrix() override

computes and returns adjacency matrix of the graph

std::unordered_map<int, std::vector<int>> get_adjacentList() final

computes and returns the adjacent list representing the graph

std::vector<std::vector<int>> get_edges() final

returns edges representing the graph. O(1) - no computation required.

int *get_indegree() final

computes and returns the indegree of all the nodes in the graph

int get_num_nodes() const final

returns the total number of nodes/vertex in the graph