Description

A sparse implementation of graphs that achieves O(1) in most 
operations.

See also: Basic graphs support

Author: Juan-Antonio Fernandez-Madrigal. http://jafma.net

Date: 2019

Copyright: Copyright (c), Individual contributors, see AUTHORS file. This program is free for non-commercial uses. For the rest, contact the AUTHORS. Please include a mention in your programs to the main developer and the web page of the library.

Collaboration diagram for Sparse implementation of graphs:

Classes
class	elementa::adts::graphs::SparseGraph< Vertex, Edge >
	A graph that stores all its info in a sparse manner. More...

Class Documentation

◆ elementa::adts::graphs::SparseGraph

class elementa::adts::graphs::SparseGraph

template<class Vertex, class Edge>
class elementa::adts::graphs::SparseGraph< Vertex, Edge >

A graph that stores all its info in a sparse manner.

This type of graph stores only once each vertex and edge datum, but contains redundant information in edges and vertices to improve time efficiency in many operations. Therefore, it is more memory-efficient when the Vertex and Edge types are large.

In this kind of graph, all operations are O(1) except erasing a node, which is O(degree(node)) due to the need of deleting all edges involved in that node.

Copying an entire graph into another is O(V) + 3*O(E).

All iterators in this implementation of graphs are never invalidated except when they are deleted (not affecting any other one).

Definition at line 73 of file sparse_graphs.h.

Inheritance diagram for elementa::adts::graphs::SparseGraph< Vertex, Edge >:

[legend]

Collaboration diagram for elementa::adts::graphs::SparseGraph< Vertex, Edge >:

[legend]

Public Types
Basic types, consts, etc.
using	BaseGraph = Graph< Vertex, Edge >

Basic types, consts, etc.
using	VertexType = Vertex
	For making Vertex and Edge available to the public. More...

using	EdgeType = Edge

using	viterator = elementa::base::MultIterator< Vertex >
	Vertex iterator. ForwardLegacyIterator. More...

using	eiterator = elementa::base::MultIterator< Edge >
	Edge iterator. ForwardLegacyIterator. More...

Public Member Functions
Constructors
	SparseGraph (void)
	Default constructor. More...

	SparseGraph (const SparseGraph &oth)
	Copy constructor. More...

SparseGraph &	operator= (const SparseGraph &oth)
	Copy assignment. More...

	SparseGraph (SparseGraph &&oth)
	Move constructor. More...

SparseGraph &	operator= (SparseGraph &&oth)
	Move assignment. More...

virtual	~SparseGraph (void)
	Destructor. More...

SparseGraph *	clone (void) const
	Derived classes must implement this method varying its return type. More...

SparseGraph *	emptyClone (void) const override
	Derived classes can override this to provide a clone that is "empty". More...

Consulting methods
bool	empty (void) const
	Must return true if the graph is empty. More...

void	clear (void)
	Must clear the content of the graph. More...

size_vertex	size_vertices (void) const
	Must return the number of vertices. More...

size_edge	size_edges (void) const
	Must return the number of edges. More...

BaseGraph::viterator	origin (const typename BaseGraph::eiterator &it) const

BaseGraph::viterator	destination (const typename BaseGraph::eiterator &it) const

Modification methods
BaseGraph::viterator	insert (const Vertex &v)
	Must insert one more vertex in the graph, unconnected to any other. More...

BaseGraph::eiterator	connect (const typename BaseGraph::viterator &itv0, const typename BaseGraph::viterator &itv1, const Edge &e)

void	unconnect (const typename BaseGraph::eiterator &ite)

void	unconnect (const typename BaseGraph::VectorOfEIts &sinds)

void	erase (const typename BaseGraph::viterator &itv)

void	erase (const typename BaseGraph::VectorOfVIts &sinds)

void	splice (BaseGraph &oth, typename BaseGraph::VectorOfVIts svothinds=nullptr, typename BaseGraph::VectorOfEIts seothinds=nullptr, typename BaseGraph::VectorOfVIts svinds=nullptr, typename BaseGraph::VectorOfEIts seinds=nullptr)

Consulting methods
bool	isLeaf (const viterator &it) const noexcept
	Return whether the given vertex iterator points to a leaf vertex. More...

bool	toLeaf (const eiterator &it) const noexcept
	Return whether the given edge iterator points to an edge ending in leaf. More...

bool	toLastChild (const eiterator &it, const viterator &vit) const noexcept
	Return whether the given edge iterator points to the last child of VIT. More...

virtual viterator	origin (const eiterator &it) const =0
	Must return a VRange_All iterator to the origin vertex of an edge. More...

virtual viterator	destination (const eiterator &it) const =0
	Must return a VRange_All iterator to the destination vertex of an edge. More...

virtual void	connection (const eiterator &it, viterator &vorg, viterator &vdest) const
	Fill VORG and VDEST with VRange_All iterators to the edge vertices. More...

virtual eiterator	connected (const viterator &v0, const viterator &v1, const EPred &epred=trivial_epred) const
	Return the first edge that connects V0 to V1 or erangeLeaving().end(). More...

virtual viterator	find_vertex (const Vertex &v) const
	Look for the first vertex that contains the given data. More...

virtual eiterator	find_edge (const Edge &e) const
	Look for the first edge that contains the given data. More...

Numerical indexing methods
virtual size_t	vertexToPos (const viterator &vit) const
	Calculate a position of a single vertex from its iterator, from 0 to V-1. More...

virtual viterator	posToVertex (size_t vpos) const
	Return the iterator correponding to the given position (from 0 to V-1). More...

virtual size_t	edgeToPos (const eiterator &eit) const
	Calculate a position of a single edge from its iterator, from 0 to E-1. More...

virtual eiterator	posToEdge (size_t epos) const
	Return the iterator correponding to the given position (from 0 to E-1). More...

Modification methods
virtual eiterator	connect (const viterator &itv0, const viterator &itv1, const Edge &e)=0
	Must add a new edge in the graph connecting two existing vertices. More...

virtual void	unconnect (const eiterator &ite)=0
	Must delete the given edge. More...

virtual void	unconnect (const VectorOfEIts &sinds)=0
	Must delete all edges indicated in SINDS (they must not be repeated) More...

virtual void	erase (const viterator &itv)=0
	Must delete the given vertex and all edges connected to it. More...

virtual void	erase (const VectorOfVIts &sinds)=0
	Must delete all verts indicated in SINDS (they must not be repeated) More...

virtual void	splice (Graph &oth, VectorOfVIts svothits=nullptr, VectorOfEIts seothits=nullptr, VectorOfVIts svits=nullptr, VectorOfEIts seits=nullptr)=0
	Must add another graph to the one existing in this object. More...

Iteration methods
VRange_All	vrangeAll (void) const
	Return a range to iterate on all Vertex data, no special order. More...

VRange_Pred	vrangePred (eiterator &eit, typename VRange_Pred::Pred &pred) const
	Return a range for iterating on a predicate of the vertices. More...

ERange_All	erangeAll (void) const
	Return a range to iterate on all Edge data, no special order. More...

ERange_Pred	erangePred (eiterator &eit, const EPred &pred) const
	Return a range for iterating on a predicate of the edges. More...

ERange_Leaving	erangeLeaving (const viterator &v) const
	Return a range to iterate on edges leaving a vertex, no special order. More...

ERange_Entering	erangeEntering (const viterator &v) const
	Return a range to iterate on edges entering a vertex, no special order. More...

ERange_DepthFirst	erangeDepthFirst (const viterator &v) const
	Return a range to iterate on edges in depth-first fashion. More...

ERange_BreadthFirst	erangeBreadthFirst (const viterator &v) const
	Return a range to iterate on edges in breadth-first fashion. More...

Protected Member Functions
virtual eiterator	eleavingbegin (const viterator &v) const =0
	Must return the begin() iterator for ERange_Leaving.

virtual eiterator	eleavingend (const viterator &v) const =0
	Must return the end() iterator for ERange_Leaving.

virtual eiterator	eenteringbegin (const viterator &v) const =0
	Must return the begin() iterator for ERange_Entering.

virtual eiterator	eenteringend (const viterator &v) const =0
	Must return the end() iterator for ERange_Entering.

Iterator ranges and therefore iterator behaviours
using	EPred = std::function< bool(const Edge &) >
	Predicate that indicates which edges to iterate on. More...

static constexpr bool	trivial_epred (const Edge &) noexcept
	A trivial predicate that always return true. More...

static constexpr bool	nil_epred (const Edge &) noexcept
	A trivial predicate that always return false. More...

Member Typedef Documentation

◆ BaseGraph

template<class Vertex , class Edge >

using elementa::adts::graphs::SparseGraph< Vertex, Edge >::BaseGraph = Graph<Vertex,Edge>

Definition at line 80 of file sparse_graphs.h.

◆ VertexType

template<class Vertex , class Edge >

using elementa::adts::graphs::Graph< Vertex, Edge >::VertexType = Vertex

inherited

For making Vertex and Edge available to the public.

Definition at line 114 of file graphs.h.

◆ EdgeType

template<class Vertex , class Edge >

using elementa::adts::graphs::Graph< Vertex, Edge >::EdgeType = Edge

inherited

Definition at line 115 of file graphs.h.

◆ viterator

template<class Vertex , class Edge >

using elementa::adts::graphs::Graph< Vertex, Edge >::viterator = elementa::base::MultIterator<Vertex>

inherited

Vertex iterator. ForwardLegacyIterator.

Definition at line 118 of file graphs.h.

◆ eiterator

template<class Vertex , class Edge >

using elementa::adts::graphs::Graph< Vertex, Edge >::eiterator = elementa::base::MultIterator<Edge>

inherited

Edge iterator. ForwardLegacyIterator.

Definition at line 121 of file graphs.h.

◆ EPred

template<class Vertex , class Edge >

using elementa::adts::graphs::Graph< Vertex, Edge >::EPred = std::function< bool(const Edge &) >

inherited

Predicate that indicates which edges to iterate on.

It must return TRUE if the given edge is one of the edges we are interested in iterating on.

Definition at line 279 of file graphs.h.

Constructor & Destructor Documentation

◆ SparseGraph() [1/3]

template<class Vertex , class Edge >

elementa::adts::graphs::SparseGraph< Vertex, Edge >::SparseGraph ( void )

inline

Default constructor.

Definition at line 89 of file sparse_graphs.h.

◆ SparseGraph() [2/3]

template<class Vertex , class Edge >

elementa::adts::graphs::SparseGraph< Vertex, Edge >::SparseGraph ( const SparseGraph< Vertex, Edge > & oth )

inline

Copy constructor.

Definition at line 92 of file sparse_graphs.h.

◆ SparseGraph() [3/3]

template<class Vertex , class Edge >

elementa::adts::graphs::SparseGraph< Vertex, Edge >::SparseGraph ( SparseGraph< Vertex, Edge > && oth )

inline

Move constructor.

Definition at line 102 of file sparse_graphs.h.

◆ ~SparseGraph()

template<class Vertex , class Edge >

virtual elementa::adts::graphs::SparseGraph< Vertex, Edge >::~SparseGraph ( void )

inlinevirtual

Destructor.

Definition at line 112 of file sparse_graphs.h.

Member Function Documentation

◆ operator=() [1/2]

template<class Vertex , class Edge >

SparseGraph & elementa::adts::graphs::SparseGraph< Vertex, Edge >::operator= ( const SparseGraph< Vertex, Edge > & oth )

inline

Copy assignment.

Definition at line 97 of file sparse_graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::operator=().

◆ operator=() [2/2]

template<class Vertex , class Edge >

SparseGraph & elementa::adts::graphs::SparseGraph< Vertex, Edge >::operator= ( SparseGraph< Vertex, Edge > && oth )

inline

Move assignment.

Definition at line 107 of file sparse_graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::operator=().

◆ clone()

template<class Vertex , class Edge >

SparseGraph * elementa::adts::graphs::SparseGraph< Vertex, Edge >::clone ( void ) const

inlinevirtual

Derived classes must implement this method varying its return type.

Implements elementa::patterns::Clonable.

Definition at line 114 of file sparse_graphs.h.

◆ emptyClone()

template<class Vertex , class Edge >

SparseGraph * elementa::adts::graphs::SparseGraph< Vertex, Edge >::emptyClone ( void ) const

inlineoverridevirtual

Derived classes can override this to provide a clone that is "empty".

"Emptiness" here means that the clone is not actually a clone of the derived object, but a new object of the same class of the derived object, without no content (i.e., right after creation).

Reimplemented from elementa::patterns::Clonable.

Definition at line 117 of file sparse_graphs.h.

◆ empty()

template<class Vertex , class Edge >

bool elementa::adts::graphs::SparseGraph< Vertex, Edge >::empty ( void ) const

inlinevirtual

Must return true if the graph is empty.

Implements elementa::adts::graphs::Graph< Vertex, Edge >.

Definition at line 126 of file sparse_graphs.h.

◆ clear()

template<class Vertex , class Edge >

void elementa::adts::graphs::SparseGraph< Vertex, Edge >::clear ( void )

inlinevirtual

Must clear the content of the graph.

Implements elementa::adts::graphs::Graph< Vertex, Edge >.

Definition at line 129 of file sparse_graphs.h.

◆ size_vertices()

template<class Vertex , class Edge >

size_vertex elementa::adts::graphs::SparseGraph< Vertex, Edge >::size_vertices ( void ) const

inlinevirtual

Must return the number of vertices.

Implements elementa::adts::graphs::Graph< Vertex, Edge >.

Definition at line 132 of file sparse_graphs.h.

◆ size_edges()

template<class Vertex , class Edge >

size_edge elementa::adts::graphs::SparseGraph< Vertex, Edge >::size_edges ( void ) const

inlinevirtual

Must return the number of edges.

Implements elementa::adts::graphs::Graph< Vertex, Edge >.

Definition at line 134 of file sparse_graphs.h.

◆ origin() [1/2]

template<class Vertex , class Edge >

BaseGraph::viterator elementa::adts::graphs::SparseGraph< Vertex, Edge >::origin ( const typename BaseGraph::eiterator & it ) const

inline

Definition at line 136 of file sparse_graphs.h.

◆ destination() [1/2]

template<class Vertex , class Edge >

BaseGraph::viterator elementa::adts::graphs::SparseGraph< Vertex, Edge >::destination ( const typename BaseGraph::eiterator & it ) const

inline

Definition at line 141 of file sparse_graphs.h.

◆ insert()

template<class Vertex , class Edge >

BaseGraph::viterator elementa::adts::graphs::SparseGraph< Vertex, Edge >::insert ( const Vertex & v )

inlinevirtual

Must insert one more vertex in the graph, unconnected to any other.

Copy V inside the graph and return a VRange_All iterator to it.

Inserting a vertex could invalidate ALL existing vertex iterators and also existing edge iterators, depending on the implementation of the graph.

Implements elementa::adts::graphs::Graph< Vertex, Edge >.

Definition at line 152 of file sparse_graphs.h.

◆ connect() [1/2]

template<class Vertex , class Edge >

BaseGraph::eiterator elementa::adts::graphs::SparseGraph< Vertex, Edge >::connect	(	const typename BaseGraph::viterator &	itv0,
		const typename BaseGraph::viterator &	itv1,
		const Edge &	e
	)

inline

Definition at line 155 of file sparse_graphs.h.

◆ unconnect() [1/4]

template<class Vertex , class Edge >

void elementa::adts::graphs::SparseGraph< Vertex, Edge >::unconnect ( const typename BaseGraph::eiterator & ite )

inline

Definition at line 164 of file sparse_graphs.h.

◆ unconnect() [2/4]

template<class Vertex , class Edge >

void elementa::adts::graphs::SparseGraph< Vertex, Edge >::unconnect ( const typename BaseGraph::VectorOfEIts & sinds )

inline

Definition at line 168 of file sparse_graphs.h.

◆ erase() [1/4]

template<class Vertex , class Edge >

void elementa::adts::graphs::SparseGraph< Vertex, Edge >::erase ( const typename BaseGraph::viterator & itv )

inline

Definition at line 171 of file sparse_graphs.h.

◆ erase() [2/4]

template<class Vertex , class Edge >

void elementa::adts::graphs::SparseGraph< Vertex, Edge >::erase ( const typename BaseGraph::VectorOfVIts & sinds )

inline

Definition at line 175 of file sparse_graphs.h.

◆ splice() [1/2]

template<class Vertex , class Edge >

void elementa::adts::graphs::SparseGraph< Vertex, Edge >::splice	(	BaseGraph &	oth,
		typename BaseGraph::VectorOfVIts *	svothinds = `nullptr`,
		typename BaseGraph::VectorOfEIts *	seothinds = `nullptr`,
		typename BaseGraph::VectorOfVIts *	svinds = `nullptr`,
		typename BaseGraph::VectorOfEIts *	seinds = `nullptr`
	)

inline

There is no need to pass more than one argument, since iterators are not invalidated in this kind of graph

Definition at line 180 of file sparse_graphs.h.

◆ trivial_epred()

template<class Vertex , class Edge >

static constexpr bool elementa::adts::graphs::Graph< Vertex, Edge >::trivial_epred ( const Edge & )

inlinestaticconstexprnoexceptinherited

A trivial predicate that always return true.

Definition at line 282 of file graphs.h.

◆ nil_epred()

template<class Vertex , class Edge >

static constexpr bool elementa::adts::graphs::Graph< Vertex, Edge >::nil_epred ( const Edge & )

inlinestaticconstexprnoexceptinherited

A trivial predicate that always return false.

Definition at line 285 of file graphs.h.

Referenced by elementa::adts::graphs::Graph< Vertex, Edge >::ERange_Pred::end().

◆ isLeaf()

template<class Vertex , class Edge >

bool elementa::adts::graphs::Graph< Vertex, Edge >::isLeaf ( const viterator & it ) const

inlinenoexceptinherited

Return whether the given vertex iterator points to a leaf vertex.

Definition at line 553 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::erangeLeaving().

Referenced by elementa::adts::graphs::Graph< Vertex, Edge >::toLeaf().

◆ toLeaf()

template<class Vertex , class Edge >

bool elementa::adts::graphs::Graph< Vertex, Edge >::toLeaf ( const eiterator & it ) const

inlinenoexceptinherited

Return whether the given edge iterator points to an edge ending in leaf.

Definition at line 557 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::destination(), and elementa::adts::graphs::Graph< Vertex, Edge >::isLeaf().

◆ origin() [2/2]

template<class Vertex , class Edge >

virtual viterator elementa::adts::graphs::Graph< Vertex, Edge >::origin ( const eiterator & it ) const

pure virtualinherited

Must return a VRange_All iterator to the origin vertex of an edge.

If the edge is invalid or does not point anywhere, must throw.

Referenced by elementa::adts::graphs::Graph< Vertex, Edge >::connection(), and elementa::adts::Tree< Vertex, Edge >::depth().

◆ destination() [2/2]

template<class Vertex , class Edge >

virtual viterator elementa::adts::graphs::Graph< Vertex, Edge >::destination ( const eiterator & it ) const

pure virtualinherited

Must return a VRange_All iterator to the destination vertex of an edge.

If the edge is invalid or does not point anywhere, must throw.

Referenced by elementa::adts::graphs::Graph< Vertex, Edge >::connected(), elementa::adts::graphs::Graph< Vertex, Edge >::connection(), and elementa::adts::graphs::Graph< Vertex, Edge >::toLeaf().

◆ connection()

template<class Vertex , class Edge >

virtual void elementa::adts::graphs::Graph< Vertex, Edge >::connection	(	const eiterator &	it,
		viterator &	vorg,
		viterator &	vdest
	)		const

inlinevirtualinherited

Fill VORG and VDEST with VRange_All iterators to the edge vertices.

This trivial implementation can be improved in derived classes.

Definition at line 574 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::destination(), and elementa::adts::graphs::Graph< Vertex, Edge >::origin().

Referenced by elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall(), elementa::adts::Tree< Vertex, Edge >::eraseNode(), elementa::adts::graphs::Szer_GraphML< Vertex, Edge >::ser(), and elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::ser().

◆ connect() [2/2]

template<class Vertex , class Edge >

virtual eiterator elementa::adts::graphs::Graph< Vertex, Edge >::connect	(	const viterator &	itv0,
		const viterator &	itv1,
		const Edge &	e
	)

pure virtualinherited

Must add a new edge in the graph connecting two existing vertices.

Copy E inside the graph and return an ERange_All iterator to it.

Connecting vertices must not invalidate existing vertex iterators, but may invalidate ALL existing edge iterators (depending on the graph implementation).

Referenced by elementa::adts::Tree< Vertex, Edge >::addChild(), and elementa::adts::Tree< Vertex, Edge >::splice().

◆ unconnect() [3/4]

template<class Vertex , class Edge >

virtual void elementa::adts::graphs::Graph< Vertex, Edge >::unconnect ( const eiterator & ite )

pure virtualinherited

Must delete the given edge.

Unconnecting an edge invalidates that iterator and may invalidate ALL existing edge iterators (depending on the implementation), but must not invalidate existing vertex iterators.

◆ unconnect() [4/4]

template<class Vertex , class Edge >

virtual void elementa::adts::graphs::Graph< Vertex, Edge >::unconnect ( const VectorOfEIts & sinds )

pure virtualinherited

Must delete all edges indicated in SINDS (they must not be repeated)

If some of the iterators is invalid or do not point to an edge, throw. If throw, the status of the graph is undefined but it can be safely cleared.

This method is needed for unconnecting sets of edges while making sure that the successive invalidations of the iterators pointing to those edges do not affect the whole unconnecting operation.

After this operation, vertex iterators already existing must not be invalidated, but ALL edge iterators may be (depending on the implementation) and all iterators used for the indicators in SINDS certainly are invalidated.

◆ erase() [3/4]

template<class Vertex , class Edge >

virtual void elementa::adts::graphs::Graph< Vertex, Edge >::erase ( const viterator & itv )

pure virtualinherited

Must delete the given vertex and all edges connected to it.

Deleting a vertex invalidates this vertex iterator and (depending on the implementation of the graph) also existing vertex and edge iterators.

Referenced by elementa::adts::Tree< Vertex, Edge >::eraseNode().

◆ erase() [4/4]

template<class Vertex , class Edge >

virtual void elementa::adts::graphs::Graph< Vertex, Edge >::erase ( const VectorOfVIts & sinds )

pure virtualinherited

Must delete all verts indicated in SINDS (they must not be repeated)

If some of the iterators is invalid or do not point to a vertex, throw. If throw, the status of the graph is undefined but it can be safely cleared.

This method is needed for erasing sets of vertices while making sure that the successive invalidations of the iterators pointing to those vertices do not affect the whole erasing operation.

After this operation, vertex and iterators already existing may be invalidated (depending on the implementation), and all iterators used for the indicators in SINDS certainly are invalidate.

◆ splice() [2/2]

template<class Vertex , class Edge >

virtual void elementa::adts::graphs::Graph< Vertex, Edge >::splice	(	Graph< Vertex, Edge > &	oth,
		VectorOfVIts *	svothits = `nullptr`,
		VectorOfEIts *	seothits = `nullptr`,
		VectorOfVIts *	svits = `nullptr`,
		VectorOfEIts *	seits = `nullptr`
	)

pure virtualinherited

Must add another graph to the one existing in this object.

By default, the intended behaviour is to move the graph in OTH (leaving it empty) to this one, but depending on the implementation the move may be a copy (although OTH will always be empty after the operation). Vertices and edges of OTH will not clash with the vertices and edges in this graph, but considered as new and unconnected to vertices of this graph. If SVOTHITS/SEOTHITS/SVITS/SEITS are not empty, they must have iterators in OTH and this, respectively, and after the merging will be changed by new iterators pointing to those same vertices and edges once they are moved to this graph, maybe in another order with respect to the original vectors.

Referenced by elementa::adts::Tree< Vertex, Edge >::splice().

◆ vrangeAll()

template<class Vertex , class Edge >

VRange_All elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll ( void ) const

inlineinherited

Return a range to iterate on all Vertex data, no special order.

Definition at line 721 of file graphs.h.

Referenced by elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall(), elementa::adts::graphs::Graph< Vertex, Edge >::MapOfVItPos::MapOfVItPos(), elementa::adts::graphs::Graph< Vertex, Edge >::VectorOfVIts::VectorOfVIts(), elementa::adts::graphs::Graph< Vertex, Edge >::find_vertex(), elementa::adts::Tree< Vertex, Edge >::root(), elementa::adts::graphs::Szer_GraphML< Vertex, Edge >::ser(), elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::ser(), and elementa::adts::Tree< Vertex, Edge >::setRoot().

◆ vrangePred()

template<class Vertex , class Edge >

VRange_Pred elementa::adts::graphs::Graph< Vertex, Edge >::vrangePred	(	eiterator &	eit,
		typename VRange_Pred::Pred &	pred
	)		const

inlineinherited

Return a range for iterating on a predicate of the vertices.

Definition at line 725 of file graphs.h.

◆ erangeAll()

template<class Vertex , class Edge >

ERange_All elementa::adts::graphs::Graph< Vertex, Edge >::erangeAll ( void ) const

inlineinherited

Return a range to iterate on all Edge data, no special order.

Definition at line 730 of file graphs.h.

Referenced by elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall(), elementa::adts::graphs::Graph< Vertex, Edge >::MapOfEItPos::MapOfEItPos(), elementa::adts::graphs::Graph< Vertex, Edge >::VectorOfEIts::VectorOfEIts(), elementa::adts::graphs::Graph< Vertex, Edge >::find_edge(), elementa::adts::graphs::Szer_GraphML< Vertex, Edge >::ser(), and elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::ser().

◆ erangePred()

template<class Vertex , class Edge >

ERange_Pred elementa::adts::graphs::Graph< Vertex, Edge >::erangePred	(	eiterator &	eit,
		const EPred &	pred
	)		const

inlineinherited

Return a range for iterating on a predicate of the edges.

Definition at line 734 of file graphs.h.

◆ erangeLeaving()

template<class Vertex , class Edge >

ERange_Leaving elementa::adts::graphs::Graph< Vertex, Edge >::erangeLeaving ( const viterator & v ) const

inlineinherited

Return a range to iterate on edges leaving a vertex, no special order.

Definition at line 738 of file graphs.h.

Referenced by elementa::adts::graphs::Graph< Vertex, Edge >::connected(), elementa::adts::graphs::Graph< Vertex, Edge >::isLeaf(), and elementa::adts::graphs::Graph< Vertex, Edge >::toLastChild().

◆ erangeEntering()

template<class Vertex , class Edge >

ERange_Entering elementa::adts::graphs::Graph< Vertex, Edge >::erangeEntering ( const viterator & v ) const

inlineinherited

Return a range to iterate on edges entering a vertex, no special order.

Definition at line 742 of file graphs.h.

Referenced by elementa::adts::Tree< Vertex, Edge >::depth().

◆ erangeDepthFirst()

template<class Vertex , class Edge >

ERange_DepthFirst elementa::adts::graphs::Graph< Vertex, Edge >::erangeDepthFirst ( const viterator & v ) const

inlineinherited

Return a range to iterate on edges in depth-first fashion.

Definition at line 746 of file graphs.h.

Referenced by elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::AllPathsVertices(), and elementa::adts::Tree< Vertex, Edge >::eraseNode().

◆ erangeBreadthFirst()

template<class Vertex , class Edge >

ERange_BreadthFirst elementa::adts::graphs::Graph< Vertex, Edge >::erangeBreadthFirst ( const viterator & v ) const

inlineinherited

Return a range to iterate on edges in breadth-first fashion.

Definition at line 750 of file graphs.h.

Description

Classes

Class Documentation

◆ elementa::adts::graphs::SparseGraph

Public Types

Public Member Functions

Protected Member Functions

Iterator ranges and therefore iterator behaviours

Member Typedef Documentation

◆ BaseGraph

◆ VertexType

◆ EdgeType

◆ viterator

◆ eiterator

◆ EPred

Constructor & Destructor Documentation

◆ SparseGraph() [1/3]

◆ SparseGraph() [2/3]

◆ SparseGraph() [3/3]

◆ ~SparseGraph()

Member Function Documentation

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ clone()

◆ emptyClone()

◆ empty()

◆ clear()

◆ size_vertices()

◆ size_edges()

◆ origin() [1/2]

◆ destination() [1/2]

◆ insert()

◆ connect() [1/2]

◆ unconnect() [1/4]

◆ unconnect() [2/4]

◆ erase() [1/4]

◆ erase() [2/4]

◆ splice() [1/2]

◆ trivial_epred()

◆ nil_epred()

◆ isLeaf()

◆ toLeaf()

◆ origin() [2/2]

◆ destination() [2/2]

◆ connection()

◆ connect() [2/2]

◆ unconnect() [3/4]

◆ unconnect() [4/4]

◆ erase() [3/4]

◆ erase() [4/4]

◆ splice() [2/2]

◆ vrangeAll()

◆ vrangePred()

◆ erangeAll()

◆ erangePred()

◆ erangeLeaving()

◆ erangeEntering()

◆ erangeDepthFirst()

◆ erangeBreadthFirst()