Graph Class Reference

Collaboration diagram for Graph:

Public Member Functions
	Graph (int V, int E)
void	addEdge (int src, int dst, int weight)
	Graph (int V)
void	addEdge (int src, int dst, int weight)
	Graph (Graph &&)=default
Graph &	operator= (Graph &&)=default
	Graph (Graph const &)=default
Graph &	operator= (Graph const &)=default
	Graph (unsigned int vertices, AdjList adjList)
	Graph (unsigned int vertices, AdjList &&adjList)
	Graph (unsigned int vertices, std::vector< Edge > const &edges)
std::remove_reference< AdjList >::type const &	getAdjList () const
unsigned int	getVertices () const
void	addVertices (unsigned int num=1)
void	addEdge (Edge const &edge)
void	addEdge (unsigned int source, unsigned int destination)
void	set_graph ()
void	ford_fulkerson ()
void	print_flow_info ()

Public Attributes
int	vertexNum
int	edgeNum
Edge *	edges
int **	edges

Private Member Functions
bool	bfs (int source, int sink)

Private Attributes
unsigned int	m_vertices = 0
AdjList	m_adjList
std::vector< std::vector< int > >	residual_capacity
std::vector< std::vector< int > >	capacity
int	total_nodes = 0
int	total_edges = 0
int	source = 0
int	sink = 0
std::vector< int >	parent
std::vector< std::tuple< int, int, int > >	edge_participated
std::bitset< MAXN >	visited
int	max_flow = 0

Detailed Description

Implementation of graph class.

The graph will be represented using Adjacency List representation. This class contains 2 data members "m_vertices" & "m_adjList" used to represent the number of vertices and adjacency list of the graph respectively. The vertices are labelled 0 - (m_vertices - 1).

Constructor & Destructor Documentation

Graph() [1/6]

Graph::Graph ( int V, int E )

inline

                        {
        this->vertexNum = V;
        this->edgeNum = E;
        this->edges = (Edge *)malloc(E * sizeof(Edge));
    }

Graph() [2/6]

Graph::Graph ( int V )

inline

                 {
        this->vertexNum = V;
        this->edges = new int *[V];
        for (int i = 0; i < V; i++) {
            this->edges[i] = new int[V];
            for (int j = 0; j < V; j++) this->edges[i][j] = INT_MAX;
            this->edges[i][i] = 0;
        }
    }

~Graph()

Graph::~Graph ( )

inline

             {
        for (int i = 0; i < vertexNum; i++) delete[] edges[i];
        delete[] edges;
    }

Graph() [3/6]

Graph::Graph ( )

inline

: m_adjList({}) {}

Graph() [4/6]

Graph::Graph ( unsigned int vertices, AdjList adjList )

inline

Create a graph from vertices and adjacency list.

Parameters

vertices	specify the number of vertices the graph would contain.
adjList	is the adjacency list representation of graph.

        : m_vertices(vertices), m_adjList(std::move(adjList)) {}

Graph() [5/6]

Graph::Graph ( unsigned int vertices, AdjList && adjList )

inline

Create a graph from vertices and adjacency list.

Parameters

vertices	specify the number of vertices the graph would contain.
adjList	is the adjacency list representation of graph.

        : m_vertices(vertices), m_adjList(std::move(adjList)) {}

Graph() [6/6]

Graph::Graph ( unsigned int vertices, std::vector< Edge > const & edges )

inline

Create a graph from vertices and a set of edges.

Adjacency list of the graph would be created from the set of edges. If the source or destination of any edge has a value greater or equal to number of vertices, then it would throw a range_error.

Parameters

vertices	specify the number of vertices the graph would contain.
edges	is a vector of edges.

        : m_vertices(vertices) {
        for (auto const& edge : edges) {
            if (edge.src >= vertices || edge.dest >= vertices) {
                throw std::range_error(
                    "Either src or dest of edge out of range");
            }
            m_adjList[edge.src].emplace_back(edge.dest);
        }
    }

Member Function Documentation

addEdge() [1/4]

void Graph::addEdge ( Edge const & edge )

inline

Add an edge in the graph.

Parameters

edge	that needs to be added.

                                   {
        if (edge.src >= m_vertices || edge.dest >= m_vertices) {
            throw std::range_error("Either src or dest of edge out of range");
        }
        m_adjList[edge.src].emplace_back(edge.dest);
    }

addEdge() [2/4]

void Graph::addEdge ( int src, int dst, int weight )

inline

                                               {
        static int edgeInd = 0;
        if (edgeInd < this->edgeNum) {
            Edge newEdge;
            newEdge.src = src;
            newEdge.dst = dst;
            newEdge.weight = weight;
            this->edges[edgeInd++] = newEdge;
        }
    }

addEdge() [3/4]

void Graph::addEdge ( int src, int dst, int weight )

inline

                                               {
        this->edges[src][dst] = weight;
    }

addEdge() [4/4]

void Graph::addEdge ( unsigned int source, unsigned int destination )

inline

Add an Edge in the graph

Parameters

source	is source vertex of the edge.
destination	is the destination vertex of the edge.

                                                                {
        if (source >= m_vertices || destination >= m_vertices) {
            throw std::range_error(
                "Either source or destination of edge out of range");
        }
        m_adjList[source].emplace_back(destination);
    }

addVertices()

void Graph::addVertices ( unsigned int num = 1 )

inline

Add vertices in the graph.

Parameters

num	is the number of vertices to be added. It adds 1 vertex by default.

{ m_vertices += num; }

bfs()

bool Graph::bfs ( int source, int sink )

inlineprivate

                                   {  //  to find the augmented - path
        visited.reset();
        std::queue<int> q;
        q.push(source);
        bool is_path_found = false;
        while (q.empty() == false && is_path_found == false) {
            int current_node = q.front();
            visited.set(current_node);
            q.pop();
            for (int i = 0; i < total_nodes; ++i) {
                if (residual_capacity[current_node][i] > 0 && !visited[i]) {
                    visited.set(i);
                    parent[i] = current_node;
                    if (i == sink) {
                        return true;
                    }
                    q.push(i);
                }
            }
        }
        return false;
    }

ford_fulkerson()

void Graph::ford_fulkerson ( )

inline

                          {
        while (bfs(source, sink)) {
            int current_node = sink;
            int flow = std::numeric_limits<int>::max();
            while (current_node != source) {
                int parent_ = parent[current_node];
                flow = std::min(flow, residual_capacity[parent_][current_node]);
                current_node = parent_;
            }
            current_node = sink;
            max_flow += flow;
            while (current_node != source) {
                int parent_ = parent[current_node];
                residual_capacity[parent_][current_node] -= flow;
                residual_capacity[current_node][parent_] += flow;
                current_node = parent_;
            }
        }
    }

getAdjList()

std::remove_reference< AdjList >::type const & Graph::getAdjList ( ) const

inline

Return a const reference of the adjacency list.

Returns

const reference to the adjacency list

                                                               {
        return m_adjList;
    }

getVertices()

unsigned int Graph::getVertices ( ) const

inline

Returns

number of vertices in the graph.

{ return m_vertices; }

print_flow_info()

void Graph::print_flow_info ( )

inline

                           {
        for (int i = 0; i < total_nodes; ++i) {
            for (int j = 0; j < total_nodes; ++j) {
                if (capacity[i][j] &&
                    residual_capacity[i][j] < capacity[i][j]) {
                    edge_participated.emplace_back(std::make_tuple(
                        i, j, capacity[i][j] - residual_capacity[i][j]));
                }
            }
        }
        std::cout << "\nNodes : " << total_nodes << "\nMax flow: " << max_flow
                  << "\nEdge present in flow: " << edge_participated.size()
                  << '\n';
        std::cout << "\nSource\tDestination\tCapacity\total_nodes";
        for (auto& edge_data : edge_participated) {
            int source = 0, destination = 0, capacity_ = 0;
            std::tie(source, destination, capacity_) = edge_data;
            std::cout << source << "\t" << destination << "\t\t" << capacity_
                      << '\t';
        }
    }

set_graph()

void Graph::set_graph ( )

inline

                     {
        std::cin >> total_nodes >> total_edges >> source >> sink;
        parent = std::vector<int>(total_nodes, -1);
        capacity = residual_capacity = std::vector<std::vector<int> >(
            total_nodes, std::vector<int>(total_nodes));
        for (int start = 0, destination = 0, capacity_ = 0, i = 0;
             i < total_edges; ++i) {
            std::cin >> start >> destination >> capacity_;
            residual_capacity[start][destination] = capacity_;
            capacity[start][destination] = capacity_;
        }
    }

---

The documentation for this class was generated from the following files:

• dynamic_programming/bellman_ford.cpp
• dynamic_programming/floyd_warshall.cpp
• graph/cycle_check_directed_graph.cpp
• graph/max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp