Represents a directed (by nature) Adjacency List Graph Structure. More...

#include <adjacency_list.h>

Public Types
using	id_type = I
	Alias for the node ID type.
using	edge_type = E
	Alias for the edge type.

Public Member Functions
bool	has_node_id (const id_type node_id) const
	Checks if a node with given ID exists in the graph.
std::unordered_set< id_type >	get_node_ids () const
	Retrieves all node IDs present in the graph.
std::set< id_type >	get_neighboring_node_ids (const id_type node_id) const
	Gets the neighboring node IDs of a given node.
void	add_node_id (const id_type node_id)
	Adds a node with the specified ID to the graph.
void	remove_node_id (const id_type node_id)
	Removes the node with the specified ID and all edges pointing to it.
bool	has_edge (const id_type from_id, const id_type to_id) const
	Checks if an edge from from_id to to_id exists.
edge_type	get_edge (const id_type from_id, const id_type to_id) const
	Retrieves the edge from from_id to to_id.
std::set< edge_type >	get_edges (const id_type from_id) const
	Retrieves all edges outgoing from the specified node.
void	add_edge (const id_type from_id, edge_type edge)
	Adds an edge from from_id to the edge's target node.
void	remove_edge (const id_type from_id, const id_type to_id)
	Removes the edge from from_id to to_id.
std::size_t	node_id_count () const
	Returns the number of nodes in the graph.
std::size_t	edge_count () const
	Returns the total number of edges in the graph.
constexpr bool	operator== (const AdjacencyList &other) const
	Equality comparison operator.
template<typename D> requires GraphLib::Internal::is_printable<D> && GraphLib::Internal::valid_data_type<D>
void	print_with_data_map (std::ostream &os, const std::unordered_map< I, D > data_map) const
	Outputs the adjacency map to the given output stream, but with data instead of IDs.

Private Attributes
std::unordered_map< id_type, std::set< edge_type > >	adj_map_ {}
	Maps node IDs to their outgoing edges.

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

Detailed Description

template<valid_id_type I, valid_edge_type E>
class GraphLib::Internal::AdjacencyList< I, E >

Represents a directed (by nature) Adjacency List Graph Structure.

Parameters

I	Type of node ID, must satisfy valid_id_type concept.
E	Edge type, must satisfy valid_edge_type with ID type I. Must at least contain the target node ID.

Definition at line 39 of file adjacency_list.h.

Member Typedef Documentation

◆ edge_type

template<valid_id_type I, valid_edge_type E>

using GraphLib::Internal::AdjacencyList< I, E >::edge_type = E

Alias for the edge type.

Definition at line 42 of file adjacency_list.h.

◆ id_type

template<valid_id_type I, valid_edge_type E>

using GraphLib::Internal::AdjacencyList< I, E >::id_type = I

Alias for the node ID type.

Definition at line 41 of file adjacency_list.h.

Member Function Documentation

◆ add_edge()

template<valid_id_type I, valid_edge_type E>

void GraphLib::Internal::AdjacencyList< I, E >::add_edge	(	const id_type	from_id,
		edge_type	edge )

inline

Adds an edge from from_id to the edge's target node.

Parameters

from_id	Source node ID.
edge	The edge to add.

Note: Requires that both node IDs exist and the edge does not already exist.

Definition at line 176 of file adjacency_list.h.

◆ add_node_id()

template<valid_id_type I, valid_edge_type E>

void GraphLib::Internal::AdjacencyList< I, E >::add_node_id ( const id_type node_id )

inline

Adds a node with the specified ID to the graph.

If the node ID already exists, this function does nothing.

Parameters

node_id The ID of the node to add.

Definition at line 93 of file adjacency_list.h.

◆ edge_count()

template<valid_id_type I, valid_edge_type E>

std::size_t GraphLib::Internal::AdjacencyList< I, E >::edge_count ( ) const

inline

Returns the total number of edges in the graph.

Counts all edges outgoing from every node.

Returns: The total edge count.

Definition at line 213 of file adjacency_list.h.

◆ get_edge()

template<valid_id_type I, valid_edge_type E>

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

inline

Retrieves the edge from from_id to to_id.

Parameters

from_id	Source node ID.
to_id	Target node ID.

Returns: The edge object representing the connection.

Note: Asserts that the edge exists.

Definition at line 147 of file adjacency_list.h.

◆ get_edges()

template<valid_id_type I, valid_edge_type E>

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

inline

Retrieves all edges outgoing from the specified node.

Parameters

from_id The node ID whose outgoing edges to retrieve.

Returns: A set containing all outgoing edges from the node.

Definition at line 162 of file adjacency_list.h.

◆ get_neighboring_node_ids()

template<valid_id_type I, valid_edge_type E>

std::set< id_type > GraphLib::Internal::AdjacencyList< I, E >::get_neighboring_node_ids ( const id_type node_id ) const

inline

Gets the neighboring node IDs of a given node.

Parameters

node_id The ID of the node whose neighbors to retrieve.

Returns: A set of node IDs that are neighbors (targets of edges) of the given node.

Note: Asserts that the node exists.

Definition at line 75 of file adjacency_list.h.

◆ get_node_ids()

template<valid_id_type I, valid_edge_type E>

std::unordered_set< id_type > GraphLib::Internal::AdjacencyList< I, E >::get_node_ids ( ) const

inline

Retrieves all node IDs present in the graph.

Returns: An unordered_set containing all node IDs.

Definition at line 60 of file adjacency_list.h.

◆ has_edge()

template<valid_id_type I, valid_edge_type E>

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

inline

Checks if an edge from from_id to to_id exists.

Parameters

from_id	Source node ID.
to_id	Target node ID.

Returns: true if such an edge exists, false otherwise.

Definition at line 130 of file adjacency_list.h.

◆ has_node_id()

template<valid_id_type I, valid_edge_type E>

bool GraphLib::Internal::AdjacencyList< I, E >::has_node_id ( const id_type node_id ) const

inline

Checks if a node with given ID exists in the graph.

Parameters

node_id The ID of the node to check.

Returns: true if the node exists, false otherwise.

Definition at line 50 of file adjacency_list.h.

◆ node_id_count()

template<valid_id_type I, valid_edge_type E>

std::size_t GraphLib::Internal::AdjacencyList< I, E >::node_id_count ( ) const

inline

Returns the number of nodes in the graph.

Returns: The count of node IDs.

Definition at line 201 of file adjacency_list.h.

◆ operator==()

template<valid_id_type I, valid_edge_type E>

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

inlineconstexpr

Equality comparison operator.

Compares two adjacency lists for equality of their internal adjacency maps.

Parameters

other Another adjacency list to compare with.

Returns: true if both adjacency lists have identical adjacency maps.

Definition at line 229 of file adjacency_list.h.

◆ print_with_data_map()

template<valid_id_type I, valid_edge_type E>

template<typename D>
requires GraphLib::Internal::is_printable<D> && GraphLib::Internal::valid_data_type<D>

void GraphLib::Internal::AdjacencyList< I, E >::print_with_data_map	(	std::ostream &	os,
		const std::unordered_map< I, D >	data_map ) const

inline

Outputs the adjacency map to the given output stream, but with data instead of IDs.

Iterates over each node and its associated edges, printing the node value followed by a list of its edges in a human-readable format. Format: NODE_VALUE : [EDGE, EDGE] with EDGE being either "NODE_VALUE" or "NODE_VALUE (WEIGHT)" depending on edge type.

Template Parameters

D	the Data Type.

Parameters

os	The output stream to write to.
data_map	the data_map from the graph, which maps NodeIDs to their data.

Definition at line 250 of file adjacency_list.h.

◆ remove_edge()

template<valid_id_type I, valid_edge_type E>

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

inline

Removes the edge from from_id to to_id.

Parameters

from_id	Source node ID.
to_id	Target node ID.

Definition at line 189 of file adjacency_list.h.

◆ remove_node_id()

template<valid_id_type I, valid_edge_type E>

void GraphLib::Internal::AdjacencyList< I, E >::remove_node_id ( const id_type node_id )

inline

Removes the node with the specified ID and all edges pointing to it.

Also removes all edges from other nodes that target this node.

Parameters

node_id The ID of the node to remove.

Definition at line 107 of file adjacency_list.h.

Member Data Documentation

◆ adj_map_

template<valid_id_type I, valid_edge_type E>

std::unordered_map<id_type, std::set<edge_type> > GraphLib::Internal::AdjacencyList< I, E >::adj_map_ {}

private

Maps node IDs to their outgoing edges.

Definition at line 267 of file adjacency_list.h.

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

include/GraphLib/internal/adjacency_list.h

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

Public Types

Public Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ edge_type

◆ id_type

Member Function Documentation

◆ add_edge()

◆ add_node_id()

◆ edge_count()

◆ get_edge()

◆ get_edges()

◆ get_neighboring_node_ids()

◆ get_node_ids()

◆ has_edge()

◆ has_node_id()

◆ node_id_count()

◆ operator==()

◆ print_with_data_map()

◆ remove_edge()

◆ remove_node_id()

Member Data Documentation

◆ adj_map_