#include <tpl_graph.H>

Classes
class	Iterator

Public Types
using	Node_Type = typename GT::Node_Type
	The type of dfata stored in the nodes.

using	Arc_Type = typename GT::Arc_Type
	The type of data stored in the arc.

Public Member Functions
bool	check () const
	Return `true` if the path is consistent.

bool	check_directed () const
	Return `true` if the directed path is consistent.

const GT &	get_graph () const noexcept
	Get a constant reference to the graph.

bool	inside_graph (const GT &gr) const noexcept
	Return `true` if `this` is on graph `gr`

	Path (const GT &__g) noexcept
	Construct a empty path on graph `__g`

void	init (Node *start_node)

	Path (const GT &_g, Node *start_node)

void	set_graph (const GT &__g, Node *start_node=nullptr)

size_t	size () const noexcept
	Return the path length in nodes.

bool	is_empty () const noexcept
	Return `true` if the path is empty.

void	empty ()
	Clean the path: all the nodes and arc are removed.

	Path (const Path &path)
	Copy constructor.

	Path (Path &&path)
	Move constructor.

Path &	operator= (const Path &path)
	Copy assignment.

Path &	operator= (Path &&path)
	Move assignment.

void	append (Arc *arc)

void	append (Node *node)

void	append_directed (Node *p)

void	append_directed (Arc *arc)

void	insert (Arc *arc)

void	insert (Node *node)

void	insert_directed (Node *p)

void	insert_directed (Arc *arc)

Node *	get_first_node () const

Node *	get_last_node () const

Arc *	get_first_arc () const

Arc *	get_last_arc () const

bool	is_cycle () const noexcept
	Return `true` if `this` is a cycle.

Node *	remove_last_node () noexcept(noexcept(list.remove_last()))

Node *	remove_first_node () noexcept(noexcept(list.remove_first()))

void	swap (Path &path) noexcept
	Fast spat between two paths (constant time)

Iterator	get_it () const
	Returns an iterator on the path.

template<class Operation >
void	for_each_node (Operation op=Operation()) const noexcept(noexcept(op))

template<class Operation >
void	for_each_arc (Operation op=Operation()) const noexcept(noexcept(op))

bool	contains_node (Node *node) const noexcept
	Return `true` if `node` belongs to the path.

bool	contains_arc (Arc *arc) const noexcept
	Return `true` if `arc` belongs to the path.

DynList< Node * >	nodes () const
	Return a list with the nodes of path (order according to the path)

DynList< Arc * >	arcs () const
	Return a list with the arcs of path (order according to the path)

bool	operator== (const Path &p) const noexcept

bool	operator!= (const Path &p) const noexcept
	Return `true` if `this` is not equal to `p`,.

Detailed Description

template<class GT>
class Aleph::Path< GT >

Path on a graph.

Many problems on graphs require dynamic building of partial or complete paths. This class models a path on a graph and it is designed for dynamically and sequentially building the path during graph's traversal.

The paths are built by their ends; that is by inserting or appending. A path is a dequeue.

Using on directed graphs

Path<GT> operates on both directed and non directed graphs. However, it is necessary to take some previsions.

Paths on explict directed graphs

If the graph is directed (ListDigraph,List_SGraph or Array_Graph), then the class operates transparently and equivalently than on non directed graphs.

Paths on implicit directed graphs

If for practice circumstances you are treating a non directed graph as a directed one, for example, because you need to know the incoming arcs, the you must advertice to Path class about this fact.

The way that we are designed consists in separating the path construction through specific methods; concretely, the methods insert_directed() and append_directed(). You could observe very extraneous behaviors if you forget this separation.

See also: Path::Iterator

Constructor & Destructor Documentation

◆ Path()

template<class GT>

Aleph::Path< GT >::Path	(	const GT &	_g,
		Node *	start_node
	)

inline

Construct a path starting from a given node

Parameters

[in]	__g	the graph
[in]	start_node	pointer to start node of path

Exceptions

bad_alloc if there is no enough memory

Here is the call graph for this function:

Member Function Documentation

◆ append() [1/2]

template<class GT>

void Aleph::Path< GT >::append ( Arc * arc )

inline

Append an arc to the path.

This method searches the last node of path and appends it an arc.

The arc must be connected to the last node.

Parameters

[in] arc pointer to arc

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if arc is not linked to the last node of path
domain_error	if the graph has not neen specified ed
domain_error	if the path is empty

Here is the call graph for this function:

Here is the caller graph for this function:

◆ append() [2/2]

template<class GT>

void Aleph::Path< GT >::append ( Node * node )

inline

Append a node to the path

This method appends node at the end of path. For this, the adjacent arcs of the last node are examinated until finding an arc linking node.

If the path is empty, the node becomes its first node.

If the operation is successful, then node becomes the last node of path.

Parameters

[in] node pointer to the node to append in the path

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the last node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

◆ append_directed() [1/2]

template<class GT>

void Aleph::Path< GT >::append_directed ( Node * p )

inline

Append a node to a directed path

This method inserts node at the end of a directed path. For this, the outcoming arcs of the last node of path are examinated until finding an arc linking node.

Note: This method is exclusively for graphs non directed treated as directed.

If the path is empty, the node becomes its first node.

If the operation is successful, then node becomes the last node of path.

Parameters

[in] node pointer to the node to append in the path

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the last node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

Here is the caller graph for this function:

◆ append_directed() [2/2]

template<class GT>

void Aleph::Path< GT >::append_directed ( Arc * arc )

inline

Append an arc to a directed path

This method appends arc at the end of a directed path. For this, the source node of arc must match the current last node of directed path.

Note: This method is exclusively for graphs non directed treated as directed.

If the operation is successful, then node becomes the last node of path.

Parameters

[in] arc pointer

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the last node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

◆ for_each_arc()

template<class GT>

template<class Operation >

void Aleph::Path< GT >::for_each_arc ( Operation op = Operation() ) const

inlinenoexcept

Execute an operation on each arc of path

Parameters

[in] op operation

Here is the caller graph for this function:

◆ for_each_node()

template<class GT>

template<class Operation >

void Aleph::Path< GT >::for_each_node ( Operation op = Operation() ) const

inlinenoexcept

Execute an operation on each node of path

Parameters

[in] op operation

◆ get_first_arc()

template<class GT>

Arc* Aleph::Path< GT >::get_first_arc ( ) const

inline

Return the first arc of path; throws overflow_error if path is empty

Here is the call graph for this function:

◆ get_first_node()

template<class GT>

Node* Aleph::Path< GT >::get_first_node ( ) const

inline

Return the first node of path; throws overflow_error if path is empty

Here is the call graph for this function:

◆ get_last_arc()

template<class GT>

Arc* Aleph::Path< GT >::get_last_arc ( ) const

inline

Return the last arc of path; throws overflow_error if path is empty

Here is the call graph for this function:

◆ get_last_node()

template<class GT>

Node* Aleph::Path< GT >::get_last_node ( ) const

inline

Return the last node of path; throws overflow_error if path is empty

Here is the call graph for this function:

◆ init()

template<class GT>

void Aleph::Path< GT >::init ( Node * start_node )

inline

Set the first node of a path

Parameters

start_node pointer to start node of path

Exceptions

bad_alloc if there is no enough memory

Note: start_node (of course) must belong to the graph. This is not verified

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [1/2]

template<class GT>

void Aleph::Path< GT >::insert ( Arc * arc )

inline

Insert an arc as the first of path.

This method inserts arc at the beginning of a path. For this, the adjacent arcs of the current first node of path are examinated until find a arc linking node.

If the operation is successful, then node becomes the first node of path.

Parameters

[in] arc pointer

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the first node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

◆ insert() [2/2]

template<class GT>

void Aleph::Path< GT >::insert ( Node * node )

inline

Insert a node to the path

This method inserts node at the beginning of path. For this, the adjacent arcs of the last node are examinated until finding an arc linking node.

If the operation is successful, then node becomes the first node of path.

Parameters

[in] node pointer to the node to insert in the path

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the last node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

◆ insert_directed() [1/2]

template<class GT>

void Aleph::Path< GT >::insert_directed ( Node * p )

inline

Append a node to a directed path

This method inserts node at the end of a directed path. For this, the outcoming arcs of the last node of path are examinated until finding an arc linking node.

Note: This method is exclusively for graphs non directed treated as directed.

If the operation is successful, then node becomes the last node of path.

Parameters

[in] node pointer to the node to insert in the path

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the last node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

◆ insert_directed() [2/2]

template<class GT>

void Aleph::Path< GT >::insert_directed ( Arc * arc )

inline

Append an arc to a directed path

This method appends arc at the beginning of a directed path. For this, the target node of arc must be the current first node of directed path.

Note: This method is exclusively for graphs non directed treated as directed.

Parameters

[in] arc pointer

Exceptions

bad_alloc	if there is no enough memory
invalid_argument	if `node` is not reachable from the last node of path
domain_error	if the graph has not been specfied

Here is the call graph for this function:

◆ operator==()

template<class GT>

bool Aleph::Path< GT >::operator== ( const Path< GT > & p ) const

inlinenoexcept

Return true if this is equal to p,

Note: The comparison is done between node and arcs contents. This implicates that the operator == must be defined for the data types stored in the nodes and arcs respectively.

Parameters

[in] p path to compare with this

Returns: true if node to node and arc to arc the paths are equal; false otherwise.

◆ remove_first_node()

template<class GT>

Node* Aleph::Path< GT >::remove_first_node ( )

inlinenoexcept

Remove the first node of path

Returns: pointer to the extracted node

Exceptions

overlow_error if path is empty

Here is the call graph for this function:

◆ remove_last_node()

template<class GT>

Node* Aleph::Path< GT >::remove_last_node ( )

inlinenoexcept

Remove the last node of path

Returns: pointer to the extracted node

Exceptions

overlow_error if path is empty

Here is the call graph for this function:

◆ set_graph()

template<class GT>

void Aleph::Path< GT >::set_graph	(	const GT &	__g,
		Node *	start_node = `nullptr`
	)

inline

Set the graph of the path.

Sometimes, by example, if you manage a path attribute inside a class, you do not the graph, but you need to declare the path. This method is intended to set the graph of a path.

Eventually, if a path is already built, then this one is erased before to set the graph.

Parameters

[in]	__g	the graph
[in]	start_node	pointer to start node of path

Exceptions

bad_alloc if there is no enough memory

Here is the call graph for this function:

Here is the caller graph for this function:

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

tpl_graph.H

Classes

Public Types

Public Member Functions

Detailed Description

template<class GT> class Aleph::Path< GT >

Using on directed graphs

Paths on explict directed graphs

Paths on implicit directed graphs

Constructor & Destructor Documentation

◆ Path()

Member Function Documentation

◆ append() [1/2]

◆ append() [2/2]

◆ append_directed() [1/2]

◆ append_directed() [2/2]

◆ for_each_arc()

◆ for_each_node()

◆ get_first_arc()

◆ get_first_node()

◆ get_last_arc()

◆ get_last_node()

◆ init()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_directed() [1/2]

◆ insert_directed() [2/2]

◆ operator==()

◆ remove_first_node()

◆ remove_last_node()

◆ set_graph()

template<class GT>
class Aleph::Path< GT >