graph< T > Class Template Reference

Class for Unweighted Graph. More...

#include <graph.h>

Public Member Functions
	graph (std::string _type, std::vector< std::pair< T, std::vector< T > > > _adj={})
	Constructor for the unweighted graph.
	graph (const graph &g)
	Construct a new graph object.
graph &	operator= (const graph &g)
	operator = for the graph class
	~graph ()
	Destroy the graph object.
void	add_edge (T u, T v)
	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 Checks if a graph is empty.
size_t	size ()
	size function
std::vector< T >	dfs (T start)
	dfs function
std::vector< T >	bfs (T start)
	bfs function
int64_t	connected_components ()
	connected_components function.
bool	cycle ()
	cycle function.
std::vector< T >	topological_sort ()
	topological_sort 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.
void	visualize ()
	visualize function.

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

Detailed Description

template<typename T>
class graph< T >

Class for Unweighted Graph.

Constructor & Destructor Documentation

graph() [1/2]

template<typename T >

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

inline

Constructor for the unweighted graph.

Parameters

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

graph() [2/2]

template<typename T >

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

inline

Construct a new graph object.

Parameters

g	the graph we want to copy

Member Function Documentation

add_edge()

template<typename T >

void graph< T >::add_edge ( T u, T v )

inline

add_edge function

Parameters

u	first node
v	second node

bfs()

template<typename T >

std::vector< T > 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 graph< T >::bipartite

(

)

bipartite function.

Returns

true if the graph is bipartite.

bridge()

template<typename T >

std::vector< std::vector< T > > 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 graph< T >::connected

(

)

connected function.

Returns

true if a graph is connected.

connected_components()

template<typename T >

int64_t graph< T >::connected_components

(

)

connected_components function.

Returns

the connected components(islands) of the graph.

cycle()

template<typename T >

bool graph< T >::cycle

(

)

cycle function.

Returns

true if a cycle exist in the graph.

dfs()

template<typename T >

std::vector< T > graph< T >::dfs

(

T

start

)

dfs function

Parameters

start

starting node of the dfs.

Returns

vector<T>, the path of the dfs.

eulerian()

template<typename T >

int 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 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. false if a direct edge from start to end does not exist.

operator=()

template<typename T >

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

inline

operator = for the graph class

Parameters

g	the graph we want to copy

Returns

graph&

scc()

template<typename T >

int64_t graph< T >::scc

(

)

scc(strongly connected components) function.

Returns

int64_t the number of scc's in the graph using kosaraju's algorithm.

size()

template<typename T >

size_t graph< T >::size

(

)

size function

Returns

size_t the size of the graph.

topological_sort()

template<typename T >

std::vector< T > graph< T >::topological_sort

(

)

topological_sort function.

Returns

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

visualize()

template<typename T >

void 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, graph< T > & g )

friend

operator << for the graph class.

Returns

ostream &out for std::cout.

---

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

• /Users/spirosmag/Documents/AlgoPlus/src/classes/graph/graph.h