Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
Graph Class Reference
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
 
Graphoperator= (Graph &&)=default
 
 Graph (Graph const &)=default
 
Graphoperator= (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 ()
 
 Graph (const int V)
 
void addEdge (int src, int dst, int weight)
 

Public Attributes

int vertexNum
 
int edgeNum
 
Edgeedges
 
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/3]

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

Create a graph from vertices and adjacency list.

Parameters
verticesspecify the number of vertices the graph would contain.
adjListis the adjacency list representation of graph.
69  : m_vertices(vertices), m_adjList(std::move(adjList)) {}

◆ Graph() [2/3]

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

Create a graph from vertices and adjacency list.

Parameters
verticesspecify the number of vertices the graph would contain.
adjListis the adjacency list representation of graph.
77  : m_vertices(vertices), m_adjList(std::move(adjList)) {}

◆ Graph() [3/3]

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
verticesspecify the number of vertices the graph would contain.
edgesis a vector of edges.
89  : m_vertices(vertices) {
90  for (auto const& edge : edges) {
91  if (edge.src >= vertices || edge.dest >= vertices) {
92  throw std::range_error(
93  "Either src or dest of edge out of range");
94  }
95  m_adjList[edge.src].emplace_back(edge.dest);
96  }
97  }

Member Function Documentation

◆ addEdge() [1/2]

void Graph::addEdge ( Edge const &  edge)
inline

Add an edge in the graph.

Parameters
edgethat needs to be added.
124  {
125  if (edge.src >= m_vertices || edge.dest >= m_vertices) {
126  throw std::range_error("Either src or dest of edge out of range");
127  }
128  m_adjList[edge.src].emplace_back(edge.dest);
129  }

◆ addEdge() [2/2]

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

Add an Edge in the graph

Parameters
sourceis source vertex of the edge.
destinationis the destination vertex of the edge.
136  {
137  if (source >= m_vertices || destination >= m_vertices) {
138  throw std::range_error(
139  "Either source or destination of edge out of range");
140  }
141  m_adjList[source].emplace_back(destination);
142  }

◆ addVertices()

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

Add vertices in the graph.

Parameters
numis the number of vertices to be added. It adds 1 vertex by default.
118 { m_vertices += num; }

◆ 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
103  {
104  return m_adjList;
105  }

◆ getVertices()

unsigned int Graph::getVertices ( ) const
inline
Returns
number of vertices in the graph.
110 { return m_vertices; }

The documentation for this class was generated from the following files:
std::move
T move(T... args)
std::range_error
STL class.