Reference Guide: Graphs

This section is a reference guide to classes/interfaces built by API on top of Graph abstract data type:

Graph: interface that defines operations of Graph abstract data type
UnweightedGraph: abstract class that implements Graph using Unweighted Graph data structure
- DirectedUnweightedGraph: class that extends UnweightedGraph using Unweighted Directed Graph data structure
- UndirectedUnweightedGraph: class that extends UnweightedGraph using Unweighted Undirected Graph data structure
WeightedGraph: abstract class that implements Graph using Weighted Graph data structure
- DirectedWeightedGraph: class that extends WeightedGraph using Weighted Undirected Graph data structure
- UndirectedWeightedGraph: class that extends WeightedGraph using Weighted Undirected Graph data structure

To see how can above classes/interfaces be iterated, please review iterators section. To see a real life example how can above classes be used, please have a look at unit tests.

Graph

Interface that defines operations one can perform on a Graph abstract data type

Signature

template <typename NODE, typename VALUE>
class Graph

Methods

Method	Signature	Description
~Graph	virtual ~Graph ()	Clears all data allocated in heap memory
createVertex	virtual NODE* createVertex (const VALUE& data) = 0	Creates vertex and adds it to graph
removeVertex	virtual void removeVertex (NODE* const& vertex) = 0	Removes vertex from graph
isPath	virtual bool isPath (NODE* const& left, NODE* const& right) = 0	Checks if there is a path of edges between vertexes
getSize	virtual std::size_t getSize () const = 0	Gets number of vertexes in graph
contains	virtual bool contains (const VALUE& data) const = 0	Checks if graph contains a vertex by value
search	virtual NODE* search (const VALUE& data) = 0	Searches graph for a vertex by value

UnweightedGraph

Abstract class that defines operations one can perform on an Unweighted Graph abstract data structure on top of Graph abstract data type, backed by a Hash Table implementing Set to insure vertex value uniqueness

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class UnweightedGraph : public Graph<UnweightedGraphVertex<T, compare, hash>, T>

Additional Methods

Method	Signature	Description
createEdge	virtual void createEdge (UnweightedGraphVertex<T, compare, hash>* const& left, UnweightedGraphVertex<T, compare, hash>* const& right) = 0	Creates edge between vertexes
removeEdge	virtual void removeEdge (UnweightedGraphVertex<T, compare, hash>* const& left, UnweightedGraphVertex<T, compare, hash>* const& right) = 0	Removes edge between vertexes

WeightedGraph

Abstract class that defines operations one can perform on a Weighted Graph abstract data structure on top of Graph abstract data type, backed by a Hash Table implementing Set to insure vertex value uniqueness

Signature

template <typename T,typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class WeightedGraph : public Graph<WeightedGraphVertex<T,W,compare,hash>, T>

Additional Methods

Method	Signature	Description
createEdge	virtual void createEdge (WeightedGraphVertex<T,W, compare, hash>* const& left, WeightedGraphVertex<T,W, compare, hash>* const& right, const W& weight) = 0	Creates edge between vertexes
removeEdge	virtual void removeEdge (WeightedGraphVertex<T,W, compare, hash>* const& left, WeightedGraphVertex<T,W, compare, hash>* const& right) = 0	Removes edge between vertexes

DirectedUnweightedGraph

Class that implements Unweighted Directed Graph data structure on top of Unweighted Graph abstract data structure

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class DirectedUnweightedGraph : public UnweightedGraph<T,compare,hash>

DirectedWeightedGraph

Class that implements Weighted Directed Graph data structure on top of Weighted Graph abstract data structure

Signature

template <typename T,typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class DirectedWeightedGraph : public WeightedGraph<T,W,compare,hash>

UndirectedUnweightedGraph

Class that implements Unweighted Undirected Graph data structure on top of Unweighted Graph abstract data structure

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class UndirectedUnweightedGraph : public UnweightedGraph<T,compare,hash>

UndirectedWeightedGraph

Class that implements Weighted Undirected Graph data structure on top of Weighted Graph abstract data structure

Signature

template <typename T,typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class UndirectedWeightedGraph : public WeightedGraph<T,W,compare,hash>

UnweightedGraphVertex

Defines logic of a VERTEX in a Unweighted Graph abstract data structure, backed by a Hash Table implementing Set to insure value uniqueness, along with operations it can perform

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class UnweightedGraphVertex

Methods

Method	Signature	Description
GraphVertex	GraphVertex (const T& data)	Creates a vertex by value inside
~GraphVertex	~GraphVertex ()	Clears all edges it points to from heap memory
setData	void setData (const T& data)	Sets value inside vertex
getData	const T& getData () const	Gets value inside vertex
getEdges	Set<UnweightedGraphVertex<T, compare, hash>> const& getEdges ()	Gets all edges current vertex points to
isEdge	bool isEdge (UnweightedGraphVertex<T, compare, hash>* const& vertex) const	Checks if current vertex has an edge with that of input
addEdge	void addEdge (UnweightedGraphVertex<T, compare, hash>* const& vertex)	Creates an edge between current vertex and that of input
removeEdge	void removeEdge (UnweightedGraphVertex<T, compare, hash>* const& vertex)	Removes edge between current vertex and that of input

WeightedGraphVertex

Defines logic of a VERTEX in a Weighted Graph abstract data structure, backed by a Hash Table implementing Set to insure value uniqueness, along with operations it can perform

Signature

template <typename T, typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class WeightedGraphVertex

Methods

Method	Signature	Description
WeightedGraphVertex	WeightedGraphVertex (const T& data)	Creates a vertex by value inside
~WeightedGraphVertex	~WeightedGraphVertex ()	Clears all edges it points to from heap memory
setData	void setData (const T& data)	Sets value inside vertex
getData	const T& getData () const	Gets value inside vertex
getEdges	Map<WeightedGraphVertex<T, W, compare, hash>, W> const& getEdges ()	Gets all edges current vertex points to
isEdge	bool isEdge (WeightedGraphVertex<T,W,compare,hash>* const& vertex) const	Checks if current vertex has an edge with that of input
getEdgeWeight	const W& getEdgeWeight (WeightedGraphVertex<T,W,compare,hash>* const& vertex) const	Gets weight of edge between current vertex and that of input
setEdgeWeight	void setEdgeWeight (WeightedGraphVertex<T,W,compare,hash>* const& vertex, const W& weight)	Sets weight of edge between current vertex and that of input
addEdge	void addEdge (WeightedGraphVertex<T,W,compare,hash>* const& vertex, const W& weight)	Creates an edge between current vertex and that of input
removeEdge	void removeEdge (WeightedGraphVertex<T,W,compare,hash>* const& vertex)	Removes edge between current vertex and that of input