Reference Guide: Graphs

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

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

Share