The Graph class represents a graph in the network. More...

#include <Graph.hpp>

Public Member Functions
	Graph (const SparseMatrix< bool > &adj)
	Construct a new Graph object.

	Graph (const std::unordered_map< Id, std::unique_ptr< Street > > &streetSet)
	Construct a new Graph object.

	Graph (const Graph &other)

Graph &	operator= (const Graph &other)

	Graph (Graph &&)=default

Graph &	operator= (Graph &&)=default

void	buildAdj ()
	Build the graph's adjacency matrix and computes max capacity.

void	buildStreetAngles ()
	Build the graph's street angles using the node's coordinates.

void	adjustNodeCapacities ()
	Adjust the nodes' transport capacity.

void	importMatrix (const std::string &fileName, bool isAdj=true, double defaultSpeed=13.8888888889)
	Import the graph's adjacency matrix from a file. If the file is not of a supported format, it will read the file as a matrix with the first two elements being the number of rows and columns and the following elements being the matrix elements.

void	importCoordinates (const std::string &fileName)
	Import the graph's nodes from a file.

void	importOSMNodes (const std::string &fileName)
	Import the graph's nodes from a file.

void	importOSMEdges (const std::string &fileName)
	Import the graph's streets from a file.

void	exportMatrix (std::string path="./matrix.dsm", bool isAdj=true)
	Export the graph's adjacency matrix to a file.

void	exportCoordinates (std::string const &path="./coordinates.csv")
	Export the nodes' coordinates to a file.

void	addNode (std::unique_ptr< Node > node)
	Add a node to the graph.

template<typename node_t, typename... TArgs> requires (std::is_base_of_v<Node, node_t>, std::constructible_from<node_t, Id, TArgs...>)
node_t &	addNode (Id id, TArgs &&... args)
	Add a node of type node_t to the graph.

template<typename T1, typename... Tn> requires is_node_v<std::remove_reference_t<T1>> && (is_node_v<std::remove_reference_t<Tn>> && ...)
void	addNodes (T1 &&node, Tn &&... nodes)

TrafficLight &	makeTrafficLight (Id const nodeId, Delay const cycleTime, Delay const counter=0)
	Convert an existing node to a traffic light.

Roundabout &	makeRoundabout (Id nodeId)
	Convert an existing node into a roundabout.

StochasticStreet &	makeStochasticStreet (Id streetId, double const flowRate)

void	makeSpireStreet (Id streetId)
	Convert an existing street into a spire street.

Station &	makeStation (Id nodeId, const unsigned int managementTime)
	Convert an existing node into a station.

template<typename edge_t, typename... TArgs> requires (std::is_base_of_v<Street, edge_t>, std::constructible_from<edge_t, Id, TArgs...>)
edge_t &	addEdge (Id id, TArgs &&... args)
	Add an edge of type edge_t to the graph.

void	addStreet (std::unique_ptr< Street > street)
	Add a street to the graph.

void	addStreet (const Street &street)
	Add a street to the graph.

template<typename T1> requires is_street_v<std::remove_reference_t<T1>>
void	addStreets (T1 &&street)

template<typename T1, typename... Tn> requires is_street_v<std::remove_reference_t<T1>> && (is_street_v<std::remove_reference_t<Tn>> && ...)
void	addStreets (T1 &&street, Tn &&... streets)

const SparseMatrix< bool > &	adjMatrix () const
	Get the graph's adjacency matrix.

size_t	nNodes () const
	Get the graph's number of nodes.

const std::unordered_map< Id, std::unique_ptr< Node > > &	nodeSet () const
	Get the graph's node map.

std::unordered_map< Id, std::unique_ptr< Node > > &	nodeSet ()
	Get the graph's node map.

const std::unique_ptr< Node > &	node (Id id) const
	Get a node from the graph.

size_t	nEdges () const
	Get the Graph's number of streets.

const std::unordered_map< Id, std::unique_ptr< Street > > &	streetSet () const
	Get the graph's street map.

std::unordered_map< Id, std::unique_ptr< Street > > &	streetSet ()
	Get the graph's street map.

const std::unique_ptr< Street > &	street (Id id) const
	Get a street from the graph.

const std::unique_ptr< Street > *	street (Id source, Id destination) const
	Get a street from the graph.

const std::unique_ptr< Street > *	oppositeStreet (Id streetId) const
	Get the opposite street of a street in the graph.

unsigned long long	maxCapacity () const
	Get the maximum agent capacity.

template<typename Func = std::function<double(const Graph, Id, Id)>> requires (std::is_same_v<std::invoke_result_t<Func, const Graph, Id, Id>, double>)
std::optional< DijkstraResult >	shortestPath (const Node &source, const Node &destination, Func f=streetLength) const
	Get the shortest path between two nodes using dijkstra algorithm.

template<typename Func = std::function<double(const Graph, Id, Id)>> requires (std::is_same_v<std::invoke_result_t<Func, const Graph, Id, Id>, double>)
std::optional< DijkstraResult >	shortestPath (Id source, Id destination, Func f=streetLength) const
	Get the shortest path between two nodes using dijkstra algorithm.

Detailed Description

The Graph class represents a graph in the network.

Template Parameters

Id,The	type of the graph's id. It must be an unsigned integral type.
Size,The	type of the graph's capacity. It must be an unsigned integral type.

Constructor & Destructor Documentation

◆ Graph() [1/2]

dsm::Graph::Graph ( const SparseMatrix< bool > & adj )

Construct a new Graph object.

Parameters

adj	An adjacency matrix made by a SparseMatrix representing the graph's adjacency matrix

◆ Graph() [2/2]

dsm::Graph::Graph ( const std::unordered_map< Id, std::unique_ptr< Street > > & streetSet )

Construct a new Graph object.

Parameters

streetSet A map of streets representing the graph's streets

Member Function Documentation

◆ addEdge()

template<typename edge_t, typename... TArgs>
requires (std::is_base_of_v<Street, edge_t>, std::constructible_from<edge_t, Id, TArgs...>)

edge_t & dsm::Graph::addEdge	(	Id	id,
		TArgs &&...	args )

Add an edge of type edge_t to the graph.

Parameters

edge	A std::unique_ptr to the edge to add
args	The edge's arguments to forward to the constructor

Returns: A reference to the added edge

◆ addNode() [1/2]

template<typename node_t, typename... TArgs>
requires (std::is_base_of_v<Node, node_t>, std::constructible_from<node_t, Id, TArgs...>)

node_t & dsm::Graph::addNode	(	Id	id,
		TArgs &&...	args )

Add a node of type node_t to the graph.

Parameters

id	The node's id
args	The node's arguments to forward to the constructor

Returns: A reference to the added node

◆ addNode() [2/2]

void dsm::Graph::addNode ( std::unique_ptr< Node > node )

Add a node to the graph.

Parameters

node	A std::unique_ptr to the node to add

◆ addStreet() [1/2]

void dsm::Graph::addStreet ( const Street & street )

Add a street to the graph.

Parameters

street A reference to the street to add

◆ addStreet() [2/2]

void dsm::Graph::addStreet ( std::unique_ptr< Street > street )

Add a street to the graph.

Parameters

street A std::unique_ptr to the street to add

◆ adjMatrix()

const SparseMatrix< bool > & dsm::Graph::adjMatrix ( ) const

inline

Get the graph's adjacency matrix.

Returns: A std::shared_ptr to the graph's adjacency matrix

◆ adjustNodeCapacities()

void dsm::Graph::adjustNodeCapacities ( )

Adjust the nodes' transport capacity.

The nodes' capacity is adjusted using the graph's streets transport capacity, which may vary basing on the number of lanes. The node capacity will be set to the sum of the incoming streets' transport capacity.

◆ buildAdj()

void dsm::Graph::buildAdj ( )

Build the graph's adjacency matrix and computes max capacity.

The adjacency matrix is built using the graph's streets and nodes. N.B.: The street ids are reassigned using the max node id, i.e. newStreetId = srcId * n + dstId, where n is the max node id.

◆ exportCoordinates()

void dsm::Graph::exportCoordinates ( std::string const & path = "./coordinates.csv" )

Export the nodes' coordinates to a file.

Parameters

path	The path to the file to export the nodes' coordinates to (default: ./nodes.dsm)

◆ exportMatrix()

void dsm::Graph::exportMatrix	(	std::string	path = "./matrix.dsm",
		bool	isAdj = true )

Export the graph's adjacency matrix to a file.

Parameters

path	The path to the file to export the adjacency matrix to (default: ./matrix.dsm)
isAdj	A boolean value indicating if the file contains the adjacency matrix or the distance matrix.

Exceptions

std::invalid_argument if the file is not found or invalid

◆ importCoordinates()

void dsm::Graph::importCoordinates ( const std::string & fileName )

Import the graph's nodes from a file.

Parameters

fileName The name of the file to import the nodes from.

Exceptions

std::invalid_argument if the file is not found, invalid or the format is not supported

The file format is deduced from the file extension. Currently only .dsm files are supported. The first input number is the number of nodes, followed by the coordinates of each node. In the i-th row of the file, the (i - 1)-th node's coordinates are expected.

◆ importMatrix()

void dsm::Graph::importMatrix	(	const std::string &	fileName,
		bool	isAdj = true,
		double	defaultSpeed = 13.8888888889 )

Import the graph's adjacency matrix from a file. If the file is not of a supported format, it will read the file as a matrix with the first two elements being the number of rows and columns and the following elements being the matrix elements.

Parameters

fileName	The name of the file to import the adjacency matrix from.
isAdj	A boolean value indicating if the file contains the adjacency matrix or the distance matrix.
defaultSpeed	The default speed limit for the streets

Exceptions

std::invalid_argument if the file is not found or invalid The matrix format is deduced from the file extension. Currently only .dsm files are supported.

◆ importOSMEdges()

void dsm::Graph::importOSMEdges ( const std::string & fileName )

Import the graph's streets from a file.

Parameters

fileName The name of the file to import the streets from.

Exceptions

std::invalid_argument if the file is not found, invalid or the format is not supported

◆ importOSMNodes()

void dsm::Graph::importOSMNodes ( const std::string & fileName )

Import the graph's nodes from a file.

Parameters

fileName The name of the file to import the nodes from.

Exceptions

std::invalid_argument if the file is not found, invalid or the format is not supported

◆ makeRoundabout()

Roundabout & dsm::Graph::makeRoundabout ( Id nodeId )

Convert an existing node into a roundabout.

Parameters

nodeId The id of the node to convert to a roundabout

Returns: A reference to the roundabout

Exceptions

std::invalid_argument if the node does not exist

◆ makeSpireStreet()

void dsm::Graph::makeSpireStreet ( Id streetId )

Convert an existing street into a spire street.

Parameters

streetId The id of the street to convert to a spire street

Exceptions

std::invalid_argument if the street does not exist

◆ makeStation()

Station & dsm::Graph::makeStation	(	Id	nodeId,
		const unsigned int	managementTime )

Convert an existing node into a station.

Parameters

nodeId	The id of the node to convert to a station
managementTime	The station's management time

Returns: A reference to the station

Exceptions

std::invalid_argument if the node does not exist

◆ makeTrafficLight()

TrafficLight & dsm::Graph::makeTrafficLight	(	Id const	nodeId,
		Delay const	cycleTime,
		Delay const	counter = 0 )

Convert an existing node to a traffic light.

Parameters

nodeId	The id of the node to convert to a traffic light
cycleTime	The traffic light's cycle time
counter	The traffic light's counter initial value. Default is 0

Returns: A reference to the traffic light

Exceptions

std::invalid_argument if the node does not exist

◆ maxCapacity()

unsigned long long dsm::Graph::maxCapacity ( ) const

inline

Get the maximum agent capacity.

Returns: unsigned long long The maximum agent capacity of the graph

◆ nEdges()

size_t dsm::Graph::nEdges ( ) const

inline

Get the Graph's number of streets.

Returns: size_t The number of streets in the graph

◆ nNodes()

size_t dsm::Graph::nNodes ( ) const

inline

Get the graph's number of nodes.

Returns: size_t The number of nodes in the graph

◆ node()

const std::unique_ptr< Node > & dsm::Graph::node ( Id id ) const

inline

Get a node from the graph.

Parameters

id	The node's id

◆ nodeSet() [1/2]

std::unordered_map< Id, std::unique_ptr< Node > > & dsm::Graph::nodeSet ( )

inline

Get the graph's node map.

Returns: A std::unordered_map containing the graph's nodes

◆ nodeSet() [2/2]

const std::unordered_map< Id, std::unique_ptr< Node > > & dsm::Graph::nodeSet ( ) const

inline

Get the graph's node map.

Returns: A std::unordered_map containing the graph's nodes

◆ oppositeStreet()

const std::unique_ptr< Street > * dsm::Graph::oppositeStreet ( Id streetId ) const

Get the opposite street of a street in the graph.

Parameters

streetId The id of the street

Exceptions

std::invalid_argument if the street does not exist

Returns: A std::unique_ptr to the street if it exists, nullptr otherwise

◆ shortestPath() [1/2]

template<typename Func>
requires (std::is_same_v<std::invoke_result_t<Func, const Graph*, Id, Id>, double>)

std::optional< DijkstraResult > dsm::Graph::shortestPath	(	const Node &	source,
		const Node &	destination,
		Func	f = streetLength ) const

Get the shortest path between two nodes using dijkstra algorithm.

Parameters

source	The source node
destination	The destination node

Returns: A DijkstraResult object containing the path and the distance

◆ shortestPath() [2/2]

template<typename Func>
requires (std::is_same_v<std::invoke_result_t<Func, const Graph*, Id, Id>, double>)

std::optional< DijkstraResult > dsm::Graph::shortestPath	(	Id	source,
		Id	destination,
		Func	f = streetLength ) const

Get the shortest path between two nodes using dijkstra algorithm.

Parameters

source	The source node id
destination	The destination node id

Returns: A DijkstraResult object containing the path and the distance

◆ street() [1/2]

const std::unique_ptr< Street > & dsm::Graph::street ( Id id ) const

inline

Get a street from the graph.

Parameters

id	The street's id

◆ street() [2/2]

const std::unique_ptr< Street > * dsm::Graph::street	(	Id	source,
		Id	destination ) const

Get a street from the graph.

Parameters

source	The source node
destination	The destination node

Returns: A std::unique_ptr to the street if it exists, nullptr otherwise

◆ streetSet() [1/2]

std::unordered_map< Id, std::unique_ptr< Street > > & dsm::Graph::streetSet ( )

inline

Get the graph's street map.

Returns: A std::unordered_map containing the graph's streets

◆ streetSet() [2/2]

const std::unordered_map< Id, std::unique_ptr< Street > > & dsm::Graph::streetSet ( ) const

inline

Get the graph's street map.

Returns: A std::unordered_map containing the graph's streets

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

src/dsm/headers/Graph.hpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

Member Function Documentation

◆ addEdge()

◆ addNode() [1/2]

◆ addNode() [2/2]

◆ addStreet() [1/2]

◆ addStreet() [2/2]

◆ adjMatrix()

◆ adjustNodeCapacities()

◆ buildAdj()

◆ exportCoordinates()

◆ exportMatrix()

◆ importCoordinates()

◆ importMatrix()

◆ importOSMEdges()

◆ importOSMNodes()

◆ makeRoundabout()

◆ makeSpireStreet()

◆ makeStation()

◆ makeTrafficLight()

◆ maxCapacity()

◆ nEdges()

◆ nNodes()

◆ node()

◆ nodeSet() [1/2]

◆ nodeSet() [2/2]

◆ oppositeStreet()

◆ shortestPath() [1/2]

◆ shortestPath() [2/2]

◆ street() [1/2]

◆ street() [2/2]

◆ streetSet() [1/2]

◆ streetSet() [2/2]