Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
Aleph::Path< GT > Class Template Reference
Graphs

Path on a graph. More...

#include <tpl_graph.H>

Inheritance diagram for Aleph::Path< GT >:
[legend]
Collaboration diagram for Aleph::Path< GT >:
[legend]

Classes

class  Iterator
 Iterator on nodes and arcs of a path. More...
 
struct  Path_Desc
 

Public Types

using Node_Type = typename GT::Node_Type
 The type of data 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
 
 Path () noexcept
 
void init (Node *start_node)
 Set the first node of a path.
 
 Path (const GT &_g, Node *start_node)
 Construct a path starting from a given node.
 
void set_graph (const GT &__g, Node *start_node=nullptr)
 Set the graph of the path.
 
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) noexcept
 Move constructor.
 
Path & operator= (const Path &path)
 Copy assignment.
 
Path & operator= (Path &&path) noexcept
 Move assignment.
 
void append (Arc *arc)
 Append an arc to the path.
 
void append (Node *node)
 Append a node to the path.
 
void append_directed (Node *p)
 Append a node to a directed path.
 
void append_directed (Arc *arc)
 Append an arc to a directed path.
 
void insert (Arc *arc)
 Insert an arc as the first of a path.
 
void insert (Node *node)
 Insert a node to the path.
 
void insert_directed (Node *p)
 Append a node to a directed path.
 
void insert_directed (Arc *arc)
 Append an arc to a directed path.
 
Node * get_first_node () const
 Return the first node of path; throws overflow_error if path is empty.
 
Node * get_last_node () const
 Return the last node of path; throws overflow_error if path is empty.
 
Arc * get_first_arc () const
 Return the first arc of path; throws overflow_error if path is empty.
 
Arc * get_last_arc () const
 Return the last arc of a path; throws overflow_error if the path is empty.
 
bool is_cycle () const
 Return true if this is a cycle; throws if path is empty.
 
Node * remove_last_node ()
 Remove the last node of path.
 
Node * remove_first_node ()
 Remove the first node of a path.
 
void swap (Path &path) noexcept
 Fast swap 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
 Execute an operation on each node of path.
 
template<class Operation >
void for_each_arc (Operation op=Operation()) const
 Execute an operation on each arc of path.
 
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 a path (order, according to the path)
 
bool operator== (const Path &p) const noexcept
 Return true if this is equal to p,.
 
bool operator!= (const Path &p) const noexcept
 Return true if this is not equal to p,.
 

Private Types

using Node = typename GT::Node
 
using Arc = typename GT::Arc
 

Private Member Functions

void check_graph ()
 

Private Attributes

const GT * g = nullptr
 
DynDlist< Path_Desc > list
 

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 deque.

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, you must advertise 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

Definition at line 2668 of file tpl_graph.H.

Member Typedef Documentation

◆ Arc

template<class GT >
using Aleph::Path< GT >::Arc = typename GT::Arc
private

Definition at line 2681 of file tpl_graph.H.

◆ Arc_Type

template<class GT >
using Aleph::Path< GT >::Arc_Type = typename GT::Arc_Type

The type of data stored in the arc.

Definition at line 2675 of file tpl_graph.H.

◆ Node

template<class GT >
using Aleph::Path< GT >::Node = typename GT::Node
private

Definition at line 2680 of file tpl_graph.H.

◆ Node_Type

template<class GT >
using Aleph::Path< GT >::Node_Type = typename GT::Node_Type

The type of data stored in the nodes.

Definition at line 2672 of file tpl_graph.H.

Constructor & Destructor Documentation

◆ Path() [1/5]

template<class GT >
Aleph::Path< GT >::Path ( const GT &  __g)
inlinenoexcept

Construct a empty path on graph __g

Definition at line 2753 of file tpl_graph.H.

◆ Path() [2/5]

template<class GT >
Aleph::Path< GT >::Path ( )
inlinenoexcept

Definition at line 2756 of file tpl_graph.H.

◆ Path() [3/5]

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

Construct a path starting from a given node.

Parameters
[in]_gthe graph
[in]start_nodepointer to start node of a path
Exceptions
bad_allocif there is no enough memory

Definition at line 2779 of file tpl_graph.H.

References Aleph::init, and Aleph::maps().

◆ Path() [4/5]

template<class GT >
Aleph::Path< GT >::Path ( const Path< GT > &  path)
inline

Copy constructor.

Definition at line 2827 of file tpl_graph.H.

◆ Path() [5/5]

template<class GT >
Aleph::Path< GT >::Path ( Path< GT > &&  path)
inlinenoexcept

Move constructor.

Definition at line 2830 of file tpl_graph.H.

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]arcpointer to arc
Exceptions
bad_allocif there is no enough memory
invalid_argumentif arc is not linked to the last node of path
domain_errorif the graph has not been specified
domain_errorif the path is empty

Definition at line 2865 of file tpl_graph.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::DynList< T >::append(), Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynList< T >::get_last(), Aleph::Path< GT >::list, and Aleph::maps().

Referenced by Aleph::__find_path_depth_first(), Aleph::Path< GT >::append(), Aleph::find_min_path(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::get_min_path(), Aleph::get_min_path(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ 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 examined 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 the path.

Parameters
[in]nodepointer to the node to append in the path
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the last node of the path
domain_errorif the graph has not been specified

Definition at line 2898 of file tpl_graph.H.

References ah_invalid_argument_if, Aleph::Path< GT >::append(), Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::g, Aleph::Path< GT >::get_last_node(), Aleph::init, Aleph::Path< GT >::list, Aleph::maps(), and Aleph::search_arc().

◆ append_directed() [1/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 a 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 the path.

Parameters
[in]arcpointer
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the last node of the path
domain_errorif the graph has not been specified

Definition at line 2977 of file tpl_graph.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::DynList< T >::append(), Aleph::Path< GT >::check_graph(), Aleph::DynList< T >::get_last(), Aleph::Path< GT >::list, and Aleph::maps().

◆ append_directed() [2/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 examined 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 the path.

Parameters
[in]pnode pointer to the node to append in the path
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the last node of the path
domain_errorif the graph has not been specified

Definition at line 2937 of file tpl_graph.H.

References ah_invalid_argument_if, Aleph::DynList< T >::append(), Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::g, Aleph::DynList< T >::get_last(), Aleph::init, Aleph::Path< GT >::list, Aleph::maps(), and Aleph::search_directed_arc().

Referenced by Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_min_path(), TEST_F(), and TEST_F().

◆ arcs()

template<class GT >
DynList< Arc * > Aleph::Path< GT >::arcs ( ) const
inline

Return a list with the arcs of a path (order, according to the path)

Definition at line 3378 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::Path< GT >::for_each_arc(), and Aleph::maps().

Referenced by TEST_F().

◆ check()

template<class GT >
bool Aleph::Path< GT >::check ( ) const
inline

Return true if the path is consistent.

Definition at line 2716 of file tpl_graph.H.

References Aleph::Path< GT >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynList< T >::get_first(), Aleph::HTList::is_unitarian_or_empty(), l, Aleph::Path< GT >::list, Aleph::maps(), and Aleph::DynList< T >::remove_first().

◆ check_directed()

template<class GT >
bool Aleph::Path< GT >::check_directed ( ) const
inline

Return true if the directed path is consistent.

Definition at line 2731 of file tpl_graph.H.

References Aleph::Path< GT >::g, Aleph::DynList< T >::get_last(), GraphCommon< GT, Node, Arc >::get_src_node(), Aleph::Path< GT >::list, and Aleph::maps().

◆ check_graph()

template<class GT >
void Aleph::Path< GT >::check_graph ( )
inlineprivate

Definition at line 2709 of file tpl_graph.H.

References ah_domain_error_if, and Aleph::Path< GT >::g.

Referenced by Aleph::Path< GT >::append(), Aleph::Path< GT >::append(), Aleph::Path< GT >::append_directed(), Aleph::Path< GT >::append_directed(), Aleph::Path< GT >::empty(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert_directed(), and Aleph::Path< GT >::insert_directed().

◆ contains_arc()

template<class GT >
bool Aleph::Path< GT >::contains_arc ( Arc *  arc) const
inlinenoexcept

Return true if arc belongs to the path.

Definition at line 3358 of file tpl_graph.H.

References Aleph::Path< GT >::Iterator::has_current_arc().

Referenced by TEST_F().

◆ contains_node()

template<class GT >
bool Aleph::Path< GT >::contains_node ( Node *  node) const
inlinenoexcept

Return true if node belongs to the path.

Definition at line 3349 of file tpl_graph.H.

References Aleph::Path< GT >::Iterator::has_current_node().

Referenced by TEST_F().

◆ empty()

template<class GT >
void Aleph::Path< GT >::empty ( )
inline

Clean the path: all the nodes and arc are removed.

Definition at line 2819 of file tpl_graph.H.

References Aleph::Path< GT >::check_graph(), Aleph::HTList::is_empty(), Aleph::Path< GT >::list, and Aleph::maps().

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_path(), Aleph::find_path_depth_first(), Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::get_min_path(), Aleph::get_min_path(), Aleph::Path< GT >::operator=(), and Aleph::Path< GT >::set_graph().

◆ for_each_arc()

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

Execute an operation on each arc of path.

Parameters
[in]opoperation

Definition at line 3342 of file tpl_graph.H.

References Aleph::Path< GT >::Iterator::has_current_arc().

Referenced by Aleph::Path< GT >::arcs(), Aleph::cancel_cycle(), print_path(), and print_path_detailed().

◆ for_each_node()

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

Execute an operation on each node of path.

Parameters
[in]opoperation

Definition at line 3331 of file tpl_graph.H.

References Aleph::Path< GT >::Iterator::has_current_node().

Referenced by Aleph::Path< GT >::nodes(), print_path(), and print_path_detailed().

◆ 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.

Definition at line 3141 of file tpl_graph.H.

References Aleph::Path< GT >::list.

◆ 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.

Definition at line 3125 of file tpl_graph.H.

References Aleph::Path< GT >::list.

Referenced by Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert_directed(), Aleph::Path< GT >::is_cycle(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_graph()

template<class GT >
const GT & Aleph::Path< GT >::get_graph ( ) const
inlinenoexcept

Get a constant reference to the graph.

Definition at line 2741 of file tpl_graph.H.

References Aleph::Path< GT >::g.

Referenced by Aleph::get_min_path().

◆ get_it()

template<class GT >
Iterator Aleph::Path< GT >::get_it ( ) const
inline

Returns an iterator on the path.

Definition at line 3321 of file tpl_graph.H.

Referenced by demo_any_path(), and demo_degrees_of_separation().

◆ get_last_arc()

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

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

Definition at line 3148 of file tpl_graph.H.

References ah_domain_error_if, Aleph::DynDlist< T >::Iterator::get_curr(), Aleph::Path< GT >::list, Aleph::DynDlist< T >::Iterator::prev(), and Aleph::DynDlist< T >::Iterator::reset_last().

◆ 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.

Definition at line 3132 of file tpl_graph.H.

References Aleph::DynList< T >::get_last(), Aleph::Path< GT >::list, and Aleph::maps().

Referenced by Aleph::__find_path_depth_first(), Aleph::Path< GT >::append(), Aleph::Path< GT >::is_cycle(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ init()

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

Set the first node of a path.

Parameters
start_nodepointer to start node of a path
Exceptions
bad_allocif there is no enough memory
Note
start_node (of course) must belong to the graph. This is not verified

Definition at line 2767 of file tpl_graph.H.

References Aleph::Path< GT >::list, and Aleph::maps().

Referenced by Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::get_min_path(), and Aleph::get_min_path().

◆ insert() [1/2]

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

Insert an arc as the first of a path.

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

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

Parameters
[in]arcpointer
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the first node of the path
domain_errorif the graph has not been specified

Definition at line 3008 of file tpl_graph.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynList< T >::get_first(), Aleph::Path< GT >::list, and Aleph::maps().

Referenced by Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::find_path_breadth_first(), TEST_F(), TEST_F(), and TEST_F().

◆ 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 the path. For this, the adjacent arcs of the last node are examined until finding an arc linking node.

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

Parameters
[in]nodepointer to the node to insert in the path
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the last node of the path
domain_errorif the graph has not been specified

Definition at line 3039 of file tpl_graph.H.

References ah_domain_error_if, Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::g, Aleph::Path< GT >::get_first_node(), Aleph::init, Aleph::Path< GT >::list, Aleph::maps(), and Aleph::search_arc().

◆ insert_directed() [1/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 a directed path.

Note
This method is exclusively for graphs non-directed treated as directed.
Parameters
[in]arcpointer
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the last node of the path
domain_errorif the graph has not been specified

Definition at line 3108 of file tpl_graph.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::Path< GT >::check_graph(), Aleph::DynList< T >::get_first(), Aleph::DynList< T >::insert(), Aleph::Path< GT >::list, and Aleph::maps().

◆ insert_directed() [2/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 the path are examined 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 the path.

Parameters
[in]pnode pointer to the node to insert in the path
Exceptions
bad_allocif there is no enough memory
invalid_argumentif node is not reachable from the last node of the path
domain_errorif the graph has not been specified

Definition at line 3075 of file tpl_graph.H.

References ah_domain_error_if, Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::g, Aleph::Path< GT >::get_first_node(), Aleph::init, Aleph::Path< GT >::list, Aleph::maps(), and Aleph::search_directed_arc().

Referenced by TEST_F(), and TEST_F().

◆ inside_graph()

template<class GT >
bool Aleph::Path< GT >::inside_graph ( const GT &  gr) const
inlinenoexcept

Return true if this is on graph gr

Definition at line 2747 of file tpl_graph.H.

References Aleph::Path< GT >::g, and Aleph::maps().

Referenced by Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), and TEST().

◆ is_cycle()

template<class GT >
bool Aleph::Path< GT >::is_cycle ( ) const
inline

Return true if this is a cycle; throws if path is empty.

Definition at line 3160 of file tpl_graph.H.

References Aleph::Path< GT >::get_first_node(), and Aleph::Path< GT >::get_last_node().

Referenced by Aleph::cancel_cycle(), TEST_F(), and TEST_F().

◆ is_empty()

template<class GT >
bool Aleph::Path< GT >::is_empty ( ) const
inlinenoexcept

Return true if the path is empty.

Definition at line 2813 of file tpl_graph.H.

References Aleph::HTList::is_empty(), and Aleph::Path< GT >::list.

Referenced by Aleph::cancel_cycle(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), and TYPED_TEST().

◆ nodes()

template<class GT >
DynList< Node * > Aleph::Path< GT >::nodes ( ) const
inline

Return a list with the nodes of path (order according to the path)

Definition at line 3367 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::Path< GT >::for_each_node(), and Aleph::maps().

Referenced by TEST_F().

◆ operator!=()

template<class GT >
bool Aleph::Path< GT >::operator!= ( const Path< GT > &  p) const
inlinenoexcept

Return true if this is not equal to p,.

Definition at line 3404 of file tpl_graph.H.

References Aleph::eq(), and Aleph::maps().

◆ operator=() [1/2]

template<class GT >
Path & Aleph::Path< GT >::operator= ( const Path< GT > &  path)
inline

Copy assignment.

Definition at line 2833 of file tpl_graph.H.

References Aleph::Path< GT >::empty(), Aleph::Path< GT >::g, and Aleph::Path< GT >::list.

◆ operator=() [2/2]

template<class GT >
Path & Aleph::Path< GT >::operator= ( Path< GT > &&  path)
inlinenoexcept

Move assignment.

Definition at line 2845 of file tpl_graph.H.

References Aleph::Path< GT >::g, and Aleph::Path< GT >::list.

◆ 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]ppath to compare with this
Returns
true if node to node and arc to arc the paths are equal; false otherwise.

Definition at line 3398 of file tpl_graph.H.

References Aleph::eq().

◆ remove_first_node()

template<class GT >
Node * Aleph::Path< GT >::remove_first_node ( )
inline

Remove the first node of a path.

Returns
pointer to the extracted node
Exceptions
overflow_errorif the path is empty

Definition at line 3182 of file tpl_graph.H.

References Aleph::Path< GT >::list.

Referenced by TEST_F().

◆ remove_last_node()

template<class GT >
Node * Aleph::Path< GT >::remove_last_node ( )
inline

Remove the last node of path.

Returns
pointer to the extracted node
Exceptions
overflow_errorif path is empty

Definition at line 3170 of file tpl_graph.H.

References Aleph::Path< GT >::list.

Referenced by Aleph::__find_path_depth_first(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path(), and TEST_F().

◆ 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 use 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]__gthe graph
[in]start_nodepointer to start node of path
Exceptions
bad_allocif there is no enough memory

Definition at line 2797 of file tpl_graph.H.

References Aleph::Path< GT >::empty(), Aleph::Path< GT >::g, Aleph::init, and Aleph::maps().

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), and Aleph::find_min_path().

◆ size()

template<class GT >
size_t Aleph::Path< GT >::size ( ) const
inlinenoexcept

Return the path length in nodes.

Definition at line 2807 of file tpl_graph.H.

References Aleph::Path< GT >::list, and Aleph::HTList::size().

Referenced by demo_any_path(), demo_degrees_of_separation(), main(), print_path(), print_path_detailed(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TYPED_TEST().

◆ swap()

template<class GT >
void Aleph::Path< GT >::swap ( Path< GT > &  path)
inlinenoexcept

Fast swap between two paths (constant time)

Definition at line 3189 of file tpl_graph.H.

References Aleph::Path< GT >::g, and Aleph::Path< GT >::list.

Member Data Documentation

◆ g

template<class GT >
const GT* Aleph::Path< GT >::g = nullptr
private

Definition at line 2678 of file tpl_graph.H.

Referenced by Aleph::Path< GT >::append(), Aleph::Path< GT >::append(), Aleph::Path< GT >::append_directed(), Aleph::Path< GT >::check(), Aleph::Path< GT >::check_directed(), Aleph::Path< GT >::check_graph(), Aleph::Path< GT >::get_graph(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert_directed(), Aleph::Path< GT >::inside_graph(), Aleph::Path< GT >::operator=(), Aleph::Path< GT >::operator=(), Aleph::Path< GT >::set_graph(), and Aleph::Path< GT >::swap().

◆ list

template<class GT >
DynDlist<Path_Desc> Aleph::Path< GT >::list
private

Definition at line 2707 of file tpl_graph.H.

Referenced by Aleph::Path< GT >::append(), Aleph::Path< GT >::append(), Aleph::Path< GT >::append_directed(), Aleph::Path< GT >::append_directed(), Aleph::Path< GT >::check(), Aleph::Path< GT >::check_directed(), Aleph::Path< GT >::empty(), Aleph::Path< GT >::get_first_arc(), Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::get_last_arc(), Aleph::Path< GT >::get_last_node(), Aleph::Path< GT >::init(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::insert_directed(), Aleph::Path< GT >::insert_directed(), Aleph::Path< GT >::is_empty(), Aleph::Path< GT >::operator=(), Aleph::Path< GT >::operator=(), Aleph::Path< GT >::remove_first_node(), Aleph::Path< GT >::remove_last_node(), Aleph::Path< GT >::size(), and Aleph::Path< GT >::swap().

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