Collaboration diagram for Graph:

[legend]

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

std::vector< 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).

Definition at line 14 of file bellman_ford.cpp.

Constructor & Destructor Documentation

◆ Graph() [1/6]

Graph::Graph	(	int	V,
		int	E )

inline

Definition at line 20 of file bellman_ford.cpp.

                        {
        this->vertexNum = V;
        this->edgeNum = E;
        this->edges.reserve(E);
    }

◆ Graph() [2/6]

Graph::Graph ( int V )

inline

Definition at line 17 of file floyd_warshall.cpp.

                 {
        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

Definition at line 27 of file floyd_warshall.cpp.

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

◆ Graph() [3/6]

Graph::Graph ( )

inline

Definition at line 57 of file cycle_check_directed_graph.cpp.

57: 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.

Definition at line 69 of file cycle_check_directed_graph.cpp.

70 : 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.

Definition at line 77 of file cycle_check_directed_graph.cpp.

78 : 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.

Definition at line 89 of file cycle_check_directed_graph.cpp.

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

Definition at line 125 of file cycle_check_directed_graph.cpp.

                                   {
        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

Definition at line 27 of file bellman_ford.cpp.

                                               {
        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

Definition at line 35 of file floyd_warshall.cpp.

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

Definition at line 137 of file cycle_check_directed_graph.cpp.

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

Definition at line 119 of file cycle_check_directed_graph.cpp.

119{ m_vertices += num; }

◆ bfs()

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

inlineprivate

Definition at line 26 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

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

Definition at line 62 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

                          {
        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

Definition at line 104 of file cycle_check_directed_graph.cpp.

                                                               {
        return m_adjList;
    }

◆ getVertices()

unsigned int Graph::getVertices ( ) const

inline

Returns: number of vertices in the graph.

Definition at line 111 of file cycle_check_directed_graph.cpp.

111{ return m_vertices; }

◆ print_flow_info()

void Graph::print_flow_info ( )

inline

Definition at line 81 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

                           {
        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

Definition at line 50 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

                     {
        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_;
        }
    }

Member Data Documentation

◆ capacity

std::vector<std::vector<int> > Graph::capacity

private

Definition at line 19 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ edge_participated

std::vector<std::tuple<int, int, int> > Graph::edge_participated

private

Definition at line 23 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ edgeNum

int Graph::edgeNum

Definition at line 16 of file bellman_ford.cpp.

◆ edges [1/2]

std::vector<Edge> Graph::edges

Definition at line 17 of file bellman_ford.cpp.

◆ edges [2/2]

int** Graph::edges

Definition at line 14 of file floyd_warshall.cpp.

◆ m_adjList

AdjList Graph::m_adjList

private

Definition at line 147 of file cycle_check_directed_graph.cpp.

◆ m_vertices

unsigned int Graph::m_vertices = 0

private

Definition at line 146 of file cycle_check_directed_graph.cpp.

◆ max_flow

int Graph::max_flow = 0

private

Definition at line 25 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ parent

std::vector<int> Graph::parent

private

Definition at line 22 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ residual_capacity

std::vector<std::vector<int> > Graph::residual_capacity

private

Definition at line 19 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ sink

int Graph::sink = 0

private

Definition at line 21 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ source

int Graph::source = 0

private

Definition at line 21 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ total_edges

int Graph::total_edges = 0

private

Definition at line 21 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ total_nodes

int Graph::total_nodes = 0

private

Definition at line 20 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

◆ vertexNum

int Graph::vertexNum

Definition at line 16 of file bellman_ford.cpp.

◆ visited

std::bitset<MAXN> Graph::visited

private

Definition at line 24 of file max_flow_with_ford_fulkerson_and_edmond_karp_algo.cpp.

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

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Graph() [1/6]

◆ Graph() [2/6]

◆ ~Graph()

◆ Graph() [3/6]

◆ Graph() [4/6]

◆ Graph() [5/6]

◆ Graph() [6/6]

Member Function Documentation

◆ addEdge() [1/4]

◆ addEdge() [2/4]

◆ addEdge() [3/4]

◆ addEdge() [4/4]

◆ addVertices()

◆ bfs()

◆ ford_fulkerson()

◆ getAdjList()

◆ getVertices()

◆ print_flow_info()

◆ set_graph()

Member Data Documentation

◆ capacity

◆ edge_participated

◆ edgeNum

◆ edges [1/2]

◆ edges [2/2]

◆ m_adjList

◆ m_vertices

◆ max_flow

◆ parent

◆ residual_capacity

◆ sink

◆ source

◆ total_edges

◆ total_nodes

◆ vertexNum

◆ visited