Abstract base class for a generic graph structure. More...

#include <abstract_graph.h>

Inheritance diagram for GraphLib::Internal::Graph< D, I, E >:

Public Types
using	data_type = D
	Alias for the data type of nodes.
using	id_type = I
	Alias for the node ID type.
using	edge_type = E
	Alias for the edge type.

Public Member Functions
virtual	~Graph ()=default
	Virtual destructor for safe polymorphic use.
virtual bool	is_directed () const =0
	Check if the graph is directed.
virtual bool	is_weighted () const =0
	Check if the graph edges are weighted.
constexpr bool	operator== (const Graph &other) const
	Equality comparison between graphs.
bool	is_full ()
	Checks if the graph has reached the maximum number of nodes.
bool	node_exists (const id_type id) const
	Check if a node with the specified ID exists.
id_type	node_count () const
	Get the number of nodes in the graph.
size_t	edge_count () const
	Get the number of edges in the graph.
std::unordered_set< id_type >	get_nodes () const
	Retrieve the set of all node IDs in the graph.
const data_type &	get_node_data (const id_type id) const
	Access the data associated with a node by its ID.
const std::set< id_type >	get_neighbors (const id_type id) const
	Get neighbors (adjacent node IDs) of a given node.
bool	has_edge (const id_type from_id, const id_type to_id) const
	Check if an edge exists between two nodes.
edge_type	get_edge (const id_type from_id, const id_type to_id) const
	Retrieve the edge information between two nodes.
std::set< edge_type >	get_edges (const id_type from_id) const
	Get all edges originating from a given node.
void	print_data_map () const
	Prints the contents of the data_map_ to standard output.
void	print_adjacency_list () const
	Outputs the graph as an adjacency list to the given stream.
void	print_with_data (std::ostream &os) const
	Outputs the graph as an adjacency list to the given stream but with its data.
void	print_adjacency_matrix () const
	Prints the adjacency matrix of the graph.
id_type	add_node (const data_type data)
	Add a new node with the given data.
id_type	add_node ()
	Add a new node with default data.
void	add_node_with_id (const id_type id, const data_type data)
	Insert a new node with a specified ID and associated data.
void	add_node_with_id (const id_type id)
	Insert a new node with a specified ID.
void	remove_node (const id_type id)
	Remove a node by ID.
void	set_node_data (const id_type id, const data_type data)
	Update the data of a node.
virtual void	add_edge (const id_type from_id, const id_type to_id)=0
	Add an edge from one node to another.
virtual void	remove_edge (const id_type from_id, const id_type to_id)=0
	Remove an edge from one node to another.

Protected Member Functions
virtual void	add_edge_impl (const id_type from_id, const edge_type edge)
	Helper to add an edge including reverse edge if undirected.

Protected Attributes
AdjacencyList< id_type, edge_type >	adj_list_ {}
	Stores edges as adjacency list.
std::unordered_map< id_type, data_type >	data_map_ {}
	Maps node IDs to node data.
id_type	highest_id_ {}
	IDs start at 1 to avoid off-by-one errors when giving node count.

Private Attributes
std::queue< id_type >	reusable_ids_ {}
	Queue of reusable node IDs freed from removed nodes.

Friends
std::ostream &	operator (std::ostream &os, const Graph< data_type, id_type, edge_type > &graph)
	friend for outputting to a std::ostream.

Detailed Description

template<valid_data_type D, valid_id_type I, valid_edge_type E>
class GraphLib::Internal::Graph< D, I, E >

Abstract base class for a generic graph structure.

Supports directed or undirected graphs and weighted or unweighted edges. Manages nodes identified by IDs, associated with data of type D. Edges are represented by type E and stored in an adjacency list.

Provides functionality for node and edge insertion, deletion, querying, and basic graph inspection.

Template Parameters

D	Data type stored within each node.
I	Type used for node IDs.
E	Edge type stored in adjacency list; must be compatible with node IDs.

Definition at line 57 of file abstract_graph.h.

Member Typedef Documentation

◆ data_type

template<valid_data_type D, valid_id_type I, valid_edge_type E>

using GraphLib::Internal::Graph< D, I, E >::data_type = D

Alias for the data type of nodes.

Definition at line 59 of file abstract_graph.h.

◆ edge_type

template<valid_data_type D, valid_id_type I, valid_edge_type E>

using GraphLib::Internal::Graph< D, I, E >::edge_type = E

Alias for the edge type.

Definition at line 61 of file abstract_graph.h.

◆ id_type

template<valid_data_type D, valid_id_type I, valid_edge_type E>

using GraphLib::Internal::Graph< D, I, E >::id_type = I

Alias for the node ID type.

Definition at line 60 of file abstract_graph.h.

Member Function Documentation

◆ add_edge()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

virtual void GraphLib::Internal::Graph< D, I, E >::add_edge	(	const id_type	from_id,
		const id_type	to_id )

pure virtual

Add an edge from one node to another.

This is a pure virtual function that must be implemented by derived classes. It adds an edge from the node with ID from_id to the node with ID to_id.

Parameters

from_id	The ID of the origin node.
to_id	The ID of the target node.

Implemented in GraphLib::Internal::UnweightedGraph< D, I, E >, GraphLib::Internal::UnweightedGraph< int, std::size_t, Internal::Edge< std::size_t > >, GraphLib::Internal::WeightedGraph< D, I, E >, and GraphLib::Internal::WeightedGraph< int, std::size_t, Internal::WeightedEdge< std::size_t, double > >.

◆ add_edge_impl()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

virtual void GraphLib::Internal::Graph< D, I, E >::add_edge_impl	(	const id_type	from_id,
		const edge_type	edge )

inlineprotectedvirtual

Helper to add an edge including reverse edge if undirected.

Adds an edge from from_id to edge.node_id. If the graph is undirected, adds the reverse edge automatically.

Parameters

from_id	The origin node ID.
edge	The edge data including target node ID and weight.

Exceptions

std::invalid_argument if nodes do not exist or edge already exists.

Definition at line 483 of file abstract_graph.h.

◆ add_node() [1/2]

template<valid_data_type D, valid_id_type I, valid_edge_type E>

id_type GraphLib::Internal::Graph< D, I, E >::add_node ( )

inline

Add a new node with default data.

For more Information see add_node(const data_type data), as this Function is only an overload.

Definition at line 365 of file abstract_graph.h.

◆ add_node() [2/2]

template<valid_data_type D, valid_id_type I, valid_edge_type E>

id_type GraphLib::Internal::Graph< D, I, E >::add_node ( const data_type data )

inline

Add a new node with the given data.

Assigns a new unique ID to the node and adds it to the graph. Throws if the graph is full.

Parameters

data	The data to store in the new node.

Returns: The assigned ID of the new node.

Exceptions

std::overflow_error	if graph is full.
std::runtime_error	if insertion fails.

Definition at line 326 of file abstract_graph.h.

◆ add_node_with_id() [1/2]

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::add_node_with_id ( const id_type id )

inline

Insert a new node with a specified ID.

For more Information see add_node_with_id(const id_type id, const data_type data), as this function is just an overload.

Definition at line 401 of file abstract_graph.h.

◆ add_node_with_id() [2/2]

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::add_node_with_id	(	const id_type	id,
		const data_type	data )

inline

Insert a new node with a specified ID and associated data.

This method explicitly inserts a node using the provided ID. It throws an exception if the graph is full or if the ID already exists.

Parameters

id	The node ID to assign.
data	The data to associate with the new node.

Exceptions

std::overflow_error	if the graph is full.
std::runtime_error	if the given ID already exists or insertion fails.

Definition at line 381 of file abstract_graph.h.

◆ edge_count()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

size_t GraphLib::Internal::Graph< D, I, E >::edge_count ( ) const

inline

Get the number of edges in the graph.

divides number of edges by 2 in undirected graphs to account for n1->n2 and n2->1 being essentially a single edge

Returns: Number of edges.

Definition at line 134 of file abstract_graph.h.

◆ get_edge()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

edge_type GraphLib::Internal::Graph< D, I, E >::get_edge	(	const id_type	from_id,
		const id_type	to_id ) const

inline

Retrieve the edge information between two nodes.

Throws if the edge does not exist.

Parameters

from_id	Origin node ID.
to_id	Target node ID.

Returns: Edge data associated with the edge.

Exceptions

std::invalid_argument if edge does not exist.

Definition at line 201 of file abstract_graph.h.

◆ get_edges()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

std::set< edge_type > GraphLib::Internal::Graph< D, I, E >::get_edges ( const id_type from_id ) const

inline

Get all edges originating from a given node.

Parameters

from_id The origin node ID.

Returns: A set of edges starting at from_id.

Definition at line 215 of file abstract_graph.h.

◆ get_neighbors()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

const std::set< id_type > GraphLib::Internal::Graph< D, I, E >::get_neighbors ( const id_type id ) const

inline

Get neighbors (adjacent node IDs) of a given node.

Parameters

id	The node ID.

Returns: A set of neighboring node IDs.

Definition at line 174 of file abstract_graph.h.

◆ get_node_data()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

const data_type & GraphLib::Internal::Graph< D, I, E >::get_node_data ( const id_type id ) const

inline

Access the data associated with a node by its ID.

Throws if the node ID does not exist.

Parameters

id	The node ID.

Returns: Const reference to the node's data.

Exceptions

std::invalid_argument if node does not exist.

Definition at line 160 of file abstract_graph.h.

◆ get_nodes()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

std::unordered_set< id_type > GraphLib::Internal::Graph< D, I, E >::get_nodes ( ) const

inline

Retrieve the set of all node IDs in the graph.

Returns: A set containing all node IDs.

Definition at line 146 of file abstract_graph.h.

◆ has_edge()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

bool GraphLib::Internal::Graph< D, I, E >::has_edge	(	const id_type	from_id,
		const id_type	to_id ) const

inline

Check if an edge exists between two nodes.

Parameters

from_id	Origin node ID.
to_id	Target node ID.

Returns: true if the edge exists.

Definition at line 186 of file abstract_graph.h.

◆ is_directed()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

virtual bool GraphLib::Internal::Graph< D, I, E >::is_directed ( ) const

nodiscardpure virtual

Check if the graph is directed.

Returns: true if directed, false if undirected.

Implemented in GraphLib::Internal::DirectedGraph< D, I, E >, GraphLib::Internal::DirectedGraph< int, std::size_t, Internal::Edge< std::size_t > >, GraphLib::Internal::DirectedGraph< int, std::size_t, Internal::WeightedEdge< std::size_t, double > >, GraphLib::Internal::UndirectedGraph< D, I, E >, GraphLib::Internal::UndirectedGraph< int, std::size_t, Internal::Edge< std::size_t > >, and GraphLib::Internal::UndirectedGraph< int, std::size_t, Internal::WeightedEdge< std::size_t, double > >.

◆ is_full()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

bool GraphLib::Internal::Graph< D, I, E >::is_full ( )

inline

Checks if the graph has reached the maximum number of nodes.

This depends on the maximum value representable by the node ID type.

Returns: true if no more nodes can be added, false otherwise.

Definition at line 101 of file abstract_graph.h.

◆ is_weighted()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

virtual bool GraphLib::Internal::Graph< D, I, E >::is_weighted ( ) const

nodiscardpure virtual

Check if the graph edges are weighted.

Returns: true if weighted, false otherwise.

Implemented in GraphLib::Internal::UnweightedGraph< D, I, E >, GraphLib::Internal::UnweightedGraph< int, std::size_t, Internal::Edge< std::size_t > >, GraphLib::Internal::WeightedGraph< D, I, E >, and GraphLib::Internal::WeightedGraph< int, std::size_t, Internal::WeightedEdge< std::size_t, double > >.

◆ node_count()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

id_type GraphLib::Internal::Graph< D, I, E >::node_count ( ) const

inline

Get the number of nodes in the graph.

Returns: Number of nodes.

Definition at line 121 of file abstract_graph.h.

◆ node_exists()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

bool GraphLib::Internal::Graph< D, I, E >::node_exists ( const id_type id ) const

inline

Check if a node with the specified ID exists.

Parameters

id	The ID of the node to check.

Returns: true if node exists, false otherwise.

Definition at line 112 of file abstract_graph.h.

◆ operator==()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

bool GraphLib::Internal::Graph< D, I, E >::operator== ( const Graph< D, I, E > & other ) const

inlineconstexpr

Equality comparison between graphs.

Checks if both node data and adjacency lists are identical.

Parameters

other Another graph instance to compare to.

Returns: true if both graphs have the same structure and data.

Definition at line 89 of file abstract_graph.h.

◆ print_adjacency_list()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::print_adjacency_list ( ) const

inline

Outputs the graph as an adjacency list to the given stream.

Internally, this simply does std::cout << *this.

Definition at line 239 of file abstract_graph.h.

◆ print_adjacency_matrix()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::print_adjacency_matrix ( ) const

inline

Prints the adjacency matrix of the graph.

Prints node IDs as headers and rows, and shows 0 for no edge, 1 for unweighted edges, or the weight for weighted edges.

Definition at line 266 of file abstract_graph.h.

◆ print_data_map()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::print_data_map ( ) const

inline

Prints the contents of the data_map_ to standard output.

Outputs each key-value pair on its own line, followed by a separator.

Definition at line 225 of file abstract_graph.h.

◆ print_with_data()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::print_with_data ( std::ostream & os ) const

inline

Outputs the graph as an adjacency list to the given stream but with its data.

Instead of printing the Node IDs the values behind the Nodes gets streamed.

Exceptions

Throws if the Data is not streamable (printable).

Parameters

os	Output stream to write the graph visualization.

Definition at line 252 of file abstract_graph.h.

◆ remove_edge()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

virtual void GraphLib::Internal::Graph< D, I, E >::remove_edge	(	const id_type	from_id,
		const id_type	to_id )

pure virtual

Remove an edge from one node to another.

This is a pure virtual function that must be implemented by derived classes. It removes the edge from the node with ID from_id to the node with ID to_id.

Parameters

from_id	The ID of the origin node.
to_id	The ID of the target node.

Implemented in GraphLib::Internal::DirectedGraph< D, I, E >, GraphLib::Internal::DirectedGraph< int, std::size_t, Internal::Edge< std::size_t > >, GraphLib::Internal::DirectedGraph< int, std::size_t, Internal::WeightedEdge< std::size_t, double > >, GraphLib::Internal::UndirectedGraph< D, I, E >, GraphLib::Internal::UndirectedGraph< int, std::size_t, Internal::Edge< std::size_t > >, and GraphLib::Internal::UndirectedGraph< int, std::size_t, Internal::WeightedEdge< std::size_t, double > >.

◆ remove_node()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::remove_node ( const id_type id )

inline

Remove a node by ID.

Removes the node's data and adjacency edges. The ID becomes reusable.

Parameters

id	Node ID to remove.

Exceptions

std::invalid_argument If the node with the given ID does not exist.

Definition at line 415 of file abstract_graph.h.

◆ set_node_data()

template<valid_data_type D, valid_id_type I, valid_edge_type E>

void GraphLib::Internal::Graph< D, I, E >::set_node_data	(	const id_type	id,
		const data_type	data )

inline

Update the data of a node.

Parameters

id	The node ID.
data	New data to assign.

Exceptions

std::invalid_argument If the node with the given ID does not exist.

Definition at line 432 of file abstract_graph.h.

Member Data Documentation

◆ adj_list_

template<valid_data_type D, valid_id_type I, valid_edge_type E>

AdjacencyList<id_type, edge_type> GraphLib::Internal::Graph< D, I, E >::adj_list_ {}

protected

Stores edges as adjacency list.

Definition at line 465 of file abstract_graph.h.

◆ data_map_

template<valid_data_type D, valid_id_type I, valid_edge_type E>

std::unordered_map<id_type, data_type> GraphLib::Internal::Graph< D, I, E >::data_map_ {}

protected

Maps node IDs to node data.

Definition at line 466 of file abstract_graph.h.

◆ highest_id_

template<valid_data_type D, valid_id_type I, valid_edge_type E>

id_type GraphLib::Internal::Graph< D, I, E >::highest_id_ {}

protected

IDs start at 1 to avoid off-by-one errors when giving node count.

Highest assigned node ID so far.

Definition at line 467 of file abstract_graph.h.

◆ reusable_ids_

template<valid_data_type D, valid_id_type I, valid_edge_type E>

std::queue<id_type> GraphLib::Internal::Graph< D, I, E >::reusable_ids_ {}

private

Queue of reusable node IDs freed from removed nodes.

Definition at line 505 of file abstract_graph.h.

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

include/GraphLib/internal/abstract_graphs/abstract_graph.h

GraphLib Bearbeitung der Aufgabe Mini Graph Library für OOP WiSe 2023/24

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ data_type

◆ edge_type

◆ id_type

Member Function Documentation

◆ add_edge()

◆ add_edge_impl()

◆ add_node() [1/2]

◆ add_node() [2/2]

◆ add_node_with_id() [1/2]

◆ add_node_with_id() [2/2]

◆ edge_count()

◆ get_edge()

◆ get_edges()

◆ get_neighbors()

◆ get_node_data()

◆ get_nodes()

◆ has_edge()

◆ is_directed()

◆ is_full()

◆ is_weighted()

◆ node_count()

◆ node_exists()

◆ operator==()

◆ print_adjacency_list()

◆ print_adjacency_matrix()

◆ print_data_map()

◆ print_with_data()

◆ remove_edge()

◆ remove_node()

◆ set_node_data()

Member Data Documentation

◆ adj_list_

◆ data_map_

◆ highest_id_

◆ reusable_ids_