Graph Module

The Graph submodule contains classes and functions related defining the system network. It is a submodule of the Utils module.

Graph Components

Graph.h

class Graph

#include <Graph.h>

A C++ program to print topological sorting of a graph using indegrees.

Created by bernardo on 2/2/17.

Public Functions

Graph(int V)

Constructs a graph with a specified number of vertices. This constructor initializes the graph’s adjacency list and downstream sources structure.

Parameters:: V – The number of vertices in the graph.

Graph(): Base constructor for a new Graph object.

const vector<int> getTopological_order() const

Retrieves the topological order of the graph. This function returns the precomputed topological order of the water sources (vertices) in the graph.

Returns:: A constant vector containing the topological order of the vertices.

void addEdge(int u, int v)

Adds a directed edge (stream/pipes) to the graph and updates related structures. This function adds an connection from vertex u to vertex v, recalculates the topological order, updates upstream sources for all vertices, and adjusts the continuity matrix transpose.

Parameters:

u – The source vertex of the edge.
v – The destination vertex of the edge.

Returns:

void

const vector<vector<int>> &getUpstream_sources() const

Retrieves the upstream sources of each water source (vertex) in the graph.

Returns:: A constant 2D vector containing the IDs of each vertex mapped to their respective upstream sources.

const vector<vector<double>> getContinuityMatrix() const

Constructs and returns the continuity matrix of the graph. This function returns a matrix in which rows correspond to vertexes. The first set of columns correspond to pipes/streams and the second set to flows in and out of vertexes.

Throws:: std::invalid_argument – If the number of edges and sources is inconsistent with the graph structure.
Returns:: A 2D vector representing the continuity matrix of the graph.

virtual ~Graph(): Destroy the Graph object.

const vector<vector<int>> getDownSources() const

Retrieves the downstream sources of each water source (vertex) in the graph.

Returns:: A constant 2D vector containing the IDs of each vertex mapped to their respective downstream sources.

Protected Functions

void addEdgeToEdgesList(int u, int v)

Adds a directed edge (a stream) to the graph’s adjacency list and updates edge-related data structures. This function adds an edge from vertex u to vertex v in the adjacency list, updates the list of downstream sources for vertex u, and increments the total edge count.

Parameters:

u – The source vertex (water source) of the edge.
v – The destination (water source) vertex of the edge.

Returns:

void

vector<int> topologicalSort()

Performs a topological sort on the directed graph to sout sources from upstream to downstream.. This function computes a topological ordering of the vertices in the graph using Kahn’s algorithm. It detects cycles and returns an empty ordering if the graph contains a cycle.

Returns:: A vector containing the topological order of the vertices. If the graph contains a cycle, the returned vector may be incomplete, and a message is printed to indicate the cycle detection.

vector<int> findUpstreamSources(int id) const

Finds the upstream sources for a given vertex. This function identifies all vertices in the graph that have a directed edge leading to the specified vertex id.

Parameters:: id – The vertex for which upstream sources are to be found.
Returns:: A vector containing all upstream source vertices for the given vertex id.

Protected Attributes

int V: The number of water sources represented as vertices of the Graph.

int n_edges = 0: The number of streams (edges) in the Graph.

list<int> *adj: A pointer to an array containing adjacency lists.

vector<vector<int>> upstream_sources: A 2D vector containing the list of upstream sources for each vertex.

vector<vector<int>> downstream_sources: A 2D vector containing the list of downstream sources for each vertex.

vector<int> topological_order: A vector containing the IDs of the water sources (vertices) in topological order.

vector<vector<double>> continuity_matrix_transpose: A 2D vector containing the continuity matrix of the Graph.