weighted_graph< T > Class Template Reference

class for weighted graph More...

#include <graph.h>

Public Member Functions
	weighted_graph (std::string _type, std::vector< std::pair< std::pair< T, T >, int64_t > > _adj={})
	Constructor for weighted graph.
	weighted_graph (const weighted_graph &g)
	Copy constructor for weighted graph class.
weighted_graph &	operator= (const weighted_graph &g)
	operator = for weighted graph class
	~weighted_graph ()
	Destroy the weighted graph object.
void	add_edge (T u, T v, int64_t w)
	add_edge function.
bool	has_edge (T start, T end)
	has_edge function.
void	clear ()
	clear function. Clearing the entire graph.
bool	empty ()
	empty function.
size_t	size ()
	size function.
std::vector< T >	dfs (T start)
	dfs function.
std::vector< T >	bfs (T start)
	bfs function.
double	shortest_path (T start, T end)
	shortest_path function.
int64_t	connected_components ()
	connected_components function.
bool	cycle ()
	cycle function.
std::vector< T >	topological_sort ()
	topological sort function.
int64_t	prim (T start)
	prim function.
bool	bipartite ()
	bipartite function.
std::vector< std::vector< T > >	bridge (T start)
	bridge function.
int64_t	scc ()
	scc(strongly connected components) function.
bool	connected ()
	connected function.
int	eulerian ()
	eulerian function.
std::unordered_map< T, double >	bellman_ford (T start)
	find SSSP and identify negative cycles.
int	max_flow (T start, T end)
	maximum flow function
void	visualize ()
	visualize function.

Friends
std::ostream &	operator<< (std::ostream &out, weighted_graph< T > &g)
	<< operator for the weighted graph class.

Detailed Description

template<typename T>
class weighted_graph< T >

class for weighted graph

Constructor & Destructor Documentation

weighted_graph() [1/2]

template<typename T>

weighted_graph< T >::weighted_graph ( std::string _type, std::vector< std::pair< std::pair< T, T >, int64_t > > _adj = {} )

inline

Constructor for weighted graph.

Parameters

__type	type of the graph, either "directed" or "undirected".
__adj	vector<pair<pair<T,T>, int64_t>>, you can pass a vector of pairs to construct the graph without doing multiple add_edge.

weighted_graph() [2/2]

template<typename T>

weighted_graph< T >::weighted_graph ( const weighted_graph< T > & g )

inlineexplicit

Copy constructor for weighted graph class.

Parameters

g	the graph we want to copy

Member Function Documentation

add_edge()

template<typename T>

void weighted_graph< T >::add_edge ( T u, T v, int64_t w )

inline

add_edge function.

Parameters

u	first node.
v	second node.
w	weight between u and v.

bellman_ford()

template<typename T>

std::unordered_map< T, double > weighted_graph< T >::bellman_ford

(

T

start

)

find SSSP and identify negative cycles.

Returns

unordered_map of SSSP.

bfs()

template<typename T>

std::vector< T > weighted_graph< T >::bfs

(

T

start

)

bfs function.

Parameters

start

starting node of the bfs.

Returns

vector<T>, the path of the bfs.

bipartite()

template<typename T>

bool weighted_graph< T >::bipartite

(

)

bipartite function.

Returns

true if the graph is bipartite.

bridge()

template<typename T>

std::vector< std::vector< T > > weighted_graph< T >::bridge

(

T

start

)

bridge function.

Parameters

start

starting point of search for the bridges.

Returns

vector<vector<T>> the bridges of the graph.

connected()

template<typename T>

bool weighted_graph< T >::connected

(

)

connected function.

Returns

true if a graph is connected.

connected_components()

template<typename T>

int64_t weighted_graph< T >::connected_components

(

)

connected_components function.

Returns

the connected componenets(islands) of the graph.

cycle()

template<typename T>

bool weighted_graph< T >::cycle

(

)

cycle function.

Returns

true if a cycle exists in the graph.

dfs()

template<typename T>

std::vector< T > weighted_graph< T >::dfs

(

T

start

)

dfs function.

Parameters

start

starting node of the bfs.

Returns

vector<T>, the path of the dfs.

empty()

template<typename T>

bool weighted_graph< T >::empty ( )

inline

empty function.

Returns

true if the graph is empty.

eulerian()

template<typename T>

int weighted_graph< T >::eulerian

(

)

eulerian function.

Returns

0 if a graph is not eulerian. 1 if a graph is semi-eulerian. 2 if a graph is eulerian.

has_edge()

template<typename T>

bool weighted_graph< T >::has_edge ( T start, T end )

inline

has_edge function.

Parameters

start	starting node.
end	ending node.

Returns

true if a direct edge from start to end exists.

max_flow()

template<typename T>

int weighted_graph< T >::max_flow	(	T	start,
		T	end )

maximum flow function

Returns the maximum flow from a starting node 's' to an ending node(sink) 't'

Returns

int: the maximum flow from 's' to 't'

operator=()

template<typename T>

weighted_graph & weighted_graph< T >::operator= ( const weighted_graph< T > & g )

inline

operator = for weighted graph class

Parameters

g	the graph we want to copy

Returns

weighted_graph&

prim()

template<typename T>

int64_t weighted_graph< T >::prim

(

T

start

)

prim function.

Parameters

start

starting node.

Returns

int64_t, the total cost of the minimum spanning tree of the graph.

scc()

template<typename T>

int64_t weighted_graph< T >::scc

(

)

scc(strongly connected components) function.

Returns

int64_t the total scc's of the graph.

shortest_path()

template<typename T>

double weighted_graph< T >::shortest_path	(	T	start,
		T	end )

shortest_path function.

Parameters

start	starting node.
end	ending node.

Returns

int64_t, the total cost of the path.

size()

template<typename T>

size_t weighted_graph< T >::size

(

)

size function.

Returns

the size of the graph.

topological_sort()

template<typename T>

std::vector< T > weighted_graph< T >::topological_sort

(

)

topological sort function.

Returns

vector<T>, the topological order of the elements of the graph.

visualize()

template<typename T>

void weighted_graph< T >::visualize

(

)

visualize function.

Returns

.dot file that can be previewed in vscode with graphviz.

Friends And Related Symbol Documentation

operator<<

template<typename T>

std::ostream & operator<< ( std::ostream & out, weighted_graph< T > & g )

friend

<< operator for the weighted graph class.

Returns

ostream &out for std::cout.

---

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

• /Users/runner/work/AlgoPlus/AlgoPlus/src/classes/graph/graph.h