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

	weighted_graph (const weighted_graph &g)
	Copy constructor for weighted graph class. More...

weighted_graph &	operator= (const weighted_graph &g)
	operator = for weighted graph class More...

	~weighted_graph ()
	Destroy the weighted graph object.

void	add_edge (T u, T v, int64_t w)
	add_edge function. More...

bool	has_edge (T start, T end)
	has_edge function. More...

void	clear ()
	clear function. Clearing the entire graph.

bool	empty ()
	empty function. More...

size_t	size ()
	size function. More...

std::vector< T >	dfs (T start)
	dfs function. More...

std::vector< T >	bfs (T start)
	bfs function. More...

double	shortest_path (T start, T end)
	shortest_path function. More...

int64_t	connected_components ()
	connected_components function. More...

bool	cycle ()
	cycle function. More...

std::vector< T >	topological_sort ()
	topological sort function. More...

int64_t	prim (T start)
	prim function. More...

bool	bipartite ()
	bipartite function. More...

std::vector< std::vector< T > >	bridge (T start)
	bridge function. More...

int64_t	scc ()
	scc(strongly connected components) function. More...

bool	connected ()
	connected function. More...

int	eulerian ()
	eulerian function. More...

std::unordered_map< T, double >	bellman_ford (T start)
	find SSSP and identify negative cycles. More...

void	visualize ()
	visualize function. More...

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

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.

◆ 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 Function 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:

/home/spiros/Documents/AlgoPlus/src/classes/graph/graph.h

Public Member Functions

Friends

Detailed Description

template<typename T> class weighted_graph< T >

Constructor & Destructor Documentation

◆ weighted_graph() [1/2]

◆ weighted_graph() [2/2]

Member Function Documentation

◆ add_edge()

◆ bellman_ford()

◆ bfs()

◆ bipartite()

◆ bridge()

◆ connected()

◆ connected_components()

◆ cycle()

◆ dfs()

◆ empty()

◆ eulerian()

◆ has_edge()

◆ operator=()

◆ prim()

◆ scc()

◆ shortest_path()

◆ size()

◆ topological_sort()

◆ visualize()

Friends And Related Function Documentation

◆ operator<<

template<typename T>
class weighted_graph< T >