Description

Base classes for implementing mathematical graphs. There are three main classes here: the Graph<> base class (for implementing graph containers), the GraphIndexMap class (for reflecting the connectivity structure of graphs), and a basic serializer for Graph<>.

See also: Sparse implementation of graphs, Support for GraphML, Trees

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

Date: 2018-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 Basic graphs support:

Classes
class	elementa::adts::graphs::Graph< Vertex, Edge >
	All graph classes derive from this one. More...

class	elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >
	Serializer for any graph in simple, compact text format. More...

Typedefs
using	elementa::adts::graphs::size_vertex = size_t
	For holding numbers of vertices of a graph. More...

using	elementa::adts::graphs::size_edge = size_t
	For holding numbers of edges of a graph. More...

Functions
	elementa::adts::graphs::Graph< Vertex, Edge >::VectorOfVIts::VectorOfVIts (const Graph &g)
	Fill vector with all vertices in G, forming a map from pos to verts. More...

	elementa::adts::graphs::Graph< Vertex, Edge >::VectorOfEIts::VectorOfEIts (const Graph &g)
	Fill vector with all edges in G, forming a map from pos to edges. More...

	elementa::adts::graphs::Graph< Vertex, Edge >::MapOfVItPos::MapOfVItPos (const Graph &g)
	Fill the map with the info in G. More...

	elementa::adts::graphs::Graph< Vertex, Edge >::MapOfVItPos::MapOfVItPos (const VectorOfVIts &m)
	Fill the map with the info in M. More...

	elementa::adts::graphs::Graph< Vertex, Edge >::MapOfEItPos::MapOfEItPos (const Graph &g)
	Fill the map with the info in G. More...

	elementa::adts::graphs::Graph< Vertex, Edge >::MapOfEItPos::MapOfEItPos (const VectorOfEIts &m)
	Fill the map with the info in M. More...

viterator	elementa::adts::graphs::Graph< Vertex, Edge >::VRange_Pred::begin (void) const
	Return the first vertex that satisfies the predicate, or end. More...

viterator	elementa::adts::graphs::Graph< Vertex, Edge >::VRange_Pred::end (void) const
	Must return an iterator pointing past the last element. More...

eiterator	elementa::adts::graphs::Graph< Vertex, Edge >::ERange_Pred::begin (void) const
	Return the first edge that satisfies the predicate, or end. More...

eiterator	elementa::adts::graphs::Graph< Vertex, Edge >::ERange_Pred::end (void) const
	Must return an iterator pointing past the last element. More...

static size_edge	elementa::adts::graphs::Graph< Vertex, Edge >::ERange_DepthFirst::forceBacktrack (eiterator &eit)
	Forces the given depth-first iterator to do backtrack. More...

std::string	elementa::adts::graphs::Graph< Vertex, Edge >::VItImpl_Pred::to_string (void) const override

std::string	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_Pred::to_string (void) const override

	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::EItImpl_DepthFirst (Graph &gr, const viterator &vi, bool beginorend=true)

Edge &	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::operator* (void)

Edge *	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::pointedData (void) const

EItImpl_DepthFirst &	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::operator++ (void)

std::string	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::to_string (void) const override

	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::EItImpl_BreadthFirst (Graph &gr, const viterator &vi, bool beginorend=true)

Edge &	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::operator* (void)

Edge *	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::pointedData (void) const

EItImpl_BreadthFirst &	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::operator++ (void)

std::string	elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::to_string (void) const override

void	elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::ser (elementa::base::OutSerCh &chout, const GraphType &graph)
	Serialization. More...

Consulting methods
virtual eiterator	elementa::adts::graphs::Graph< Vertex, Edge >::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	elementa::adts::graphs::Graph< Vertex, Edge >::find_vertex (const Vertex &v) const
	Look for the first vertex that contains the given data. More...

virtual eiterator	elementa::adts::graphs::Graph< Vertex, Edge >::find_edge (const Edge &e) const
	Look for the first edge that contains the given data. More...

bool	elementa::adts::graphs::Graph< Vertex, Edge >::toLastChild (const eiterator &it, const viterator &vit) const noexcept
	Return whether the given edge iterator points to the last child of VIT. More...

Numerical indexing methods
virtual size_t	elementa::adts::graphs::Graph< Vertex, Edge >::vertexToPos (const viterator &vit) const
	Calculate a position of a single vertex from its iterator, from 0 to V-1. More...

virtual viterator	elementa::adts::graphs::Graph< Vertex, Edge >::posToVertex (size_t vpos) const
	Return the iterator correponding to the given position (from 0 to V-1). More...

virtual size_t	elementa::adts::graphs::Graph< Vertex, Edge >::edgeToPos (const eiterator &eit) const
	Calculate a position of a single edge from its iterator, from 0 to E-1. More...

virtual eiterator	elementa::adts::graphs::Graph< Vertex, Edge >::posToEdge (size_t epos) const
	Return the iterator correponding to the given position (from 0 to E-1). More...

Class Documentation

◆ elementa::adts::graphs::Graph

class elementa::adts::graphs::Graph

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

All graph classes derive from this one.

Nodes will be of type Vertex, while edges will be of type Edge. Both types need to be CopyConstructible and CopyAssignable, and must be != void since this is a container that must contain something. They must also support == and != operators as long as you use methods find_vertex() or find_edge().

Graphs allow for connecting the same pair of vertices many times (multigraphs) and the same vertex with itself (loops).

This base class provides two iterator behaviours already implemented that work for any derived class: depth-first search and breadth-first search. The derived class must implement the iterator behaviors for scanning all vertices, all edges and all entering/leaving edges of a vertex.

/note - Derived classes must implement the emptyClone() method of the Clonable class.

/note - Remember to call the Validatable class constructors/copies/assignments appropriately in any iterator implementation of derived classes.

/note - All derived classes must provide default constructors.

/note - Iterators can be invalidated during modifications of the graph, as explained in the corresponding methods.

Definition at line 106 of file graphs.h.

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

[legend]

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

[legend]

Public Types
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
virtual Clonable *	clone (void) const =0
	Derived classes must implement this method varying its return type. More...

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

Constructors
	Graph (void)=default
	Default constructor.

	Graph (const Graph &oth)=default
	Copy constructor.

Graph &	operator= (const Graph &oth)=default
	Copy assignment.

	Graph (Graph &&oth)=default
	Move constructor.

Graph &	operator= (Graph &&oth)=default
	Move assignment.

virtual	~Graph (void)=default
	Virtual destructor.

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

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

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

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 void	clear (void)=0
	Must clear the content of the graph. More...

virtual viterator	insert (const Vertex &v)=0
	Must insert one more vertex in the graph, unconnected to any other. More...

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 viterator	vallbegin (void) const =0
	Must return the begin() iterator for VRange_All.

virtual viterator	vallend (void) const =0
	Must return the end() iterator for VRange_All.

virtual eiterator	eallbegin (void) const =0
	Must return the begin() iterator for ERange_All.

virtual eiterator	eallend (void) const =0
	Must return the end() iterator for VRange_All.

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

◆ VertexType

template<class Vertex , class Edge >

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

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

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>

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>

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 &) >

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.

Member Function Documentation

◆ trivial_epred()

template<class Vertex , class Edge >

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

inlinestaticconstexprnoexcept

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 & )

inlinestaticconstexprnoexcept

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().

◆ empty()

template<class Vertex , class Edge >

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

pure virtual

Must return true if the graph is empty.

Implemented in elementa::adts::graphs::SparseGraph< Vertex, Edge >.

◆ size_vertices()

template<class Vertex , class Edge >

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

pure virtual

Must return the number of vertices.

Implemented in elementa::adts::graphs::SparseGraph< Vertex, Edge >.

Referenced by elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall(), elementa::adts::graphs::Graph< Vertex, Edge >::posToVertex(), 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().

◆ size_edges()

template<class Vertex , class Edge >

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

pure virtual

Must return the number of edges.

Implemented in elementa::adts::graphs::SparseGraph< Vertex, Edge >.

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

◆ isLeaf()

template<class Vertex , class Edge >

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

inlinenoexcept

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

inlinenoexcept

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()

template<class Vertex , class Edge >

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

pure virtual

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()

template<class Vertex , class Edge >

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

pure virtual

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

inlinevirtual

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().

◆ clear()

template<class Vertex , class Edge >

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

pure virtual

Must clear the content of the graph.

Implemented in elementa::adts::graphs::SparseGraph< Vertex, Edge >.

◆ insert()

template<class Vertex , class Edge >

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

pure virtual

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.

Implemented in elementa::adts::graphs::SparseGraph< Vertex, Edge >.

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

◆ connect()

template<class Vertex , class Edge >

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

pure virtual

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() [1/2]

template<class Vertex , class Edge >

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

pure virtual

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() [2/2]

template<class Vertex , class Edge >

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

pure virtual

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() [1/2]

template<class Vertex , class Edge >

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

pure virtual

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() [2/2]

template<class Vertex , class Edge >

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

pure virtual

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()

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 virtual

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

inline

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

inline

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

inline

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

inline

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

inline

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

inline

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

inline

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

inline

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

Definition at line 750 of file graphs.h.

◆ clone()

virtual Clonable * elementa::patterns::Clonable::clone ( void ) const

pure virtualinherited

Derived classes must implement this method varying its return type.

Implemented in elementa::adts::graphs::SparseGraph< Vertex, Edge >, elementa::base::SerChLoc, and elementa::base::SerChLocText.

◆ emptyClone()

virtual Clonable * elementa::patterns::Clonable::emptyClone ( void ) const

inlinevirtualinherited

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 in elementa::adts::graphs::SparseGraph< Vertex, Edge >.

Definition at line 93 of file clonable.h.

References ELE_CODE_UNIMPLEMENTED.

◆ elementa::adts::graphs::Szer_GraphCompactText

class elementa::adts::graphs::Szer_GraphCompactText

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

Serializer for any graph in simple, compact text format.

It generates a compact text format of the graph structure:

First 20+1 chars: the number of vertices + "\n"
Next 20+1 chars: the number of edges + "\n"
For each edge:
- First 20+1 chars: index of origin vertex + "\n"
- Next 20+1 chars: index of destination vertex + "\n"
For each vertex:
- Serialization of the vertex object + "\n"
For each edge:
- Serialization of the edge object + "\n"

If some of the Vertex or Edge serializers has been set to nullptr, the corresponding objects (Vertex or Edge) are not serialized; just the structure of the graph.

Definition at line 1111 of file graphs.h.

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

[legend]

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

[legend]

Public Types
using	GraphType = Graph< Vertex, Edge >

using	SType = Graph< Vertex, Edge >
	To access the Sble type parameter of this type. More...

using	RDeserType = Graph< Vertex, Edge >
	To access the ReturnDeserType type parameter of this type. More...

using	RSerType = Graph< Vertex, Edge >
	To access the ReturnSerType type parameter of this type. More...

Public Member Functions
	Szer_GraphCompactText (elementa::base::Serializer< Vertex > &szerv, elementa::base::Serializer< Edge > &szere)
	Constructor. More...

void	ser (elementa::base::OutSerCh &chout, const GraphType &graph)
	Serialization. More...

virtual void	ser (OutSerCh &chout, const Graph< Vertex, Edge > &obj)
	Serializes an object, writing the resulting chars into CHOUT. More...

virtual void	deser (InSerCh &chin, Graph< Vertex, Edge > &obj)
	Deserializes an object from a sequence of chars in CHIN. More...

Member Typedef Documentation

◆ GraphType

template<class Vertex , class Edge >

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

Definition at line 1116 of file graphs.h.

◆ SType

using elementa::base::Serializer< Graph< Vertex, Edge > , void , void >::SType = Graph< Vertex, Edge >

inherited

To access the Sble type parameter of this type.

Definition at line 193 of file serializers.h.

◆ RDeserType

using elementa::base::Serializer< Graph< Vertex, Edge > , void , void >::RDeserType = Graph< Vertex, Edge >

inherited

To access the ReturnDeserType type parameter of this type.

Definition at line 196 of file serializers.h.

◆ RSerType

using elementa::base::Serializer< Graph< Vertex, Edge > , void , void >::RSerType = Graph< Vertex, Edge >

inherited

To access the ReturnSerType type parameter of this type.

Definition at line 199 of file serializers.h.

Constructor & Destructor Documentation

◆ Szer_GraphCompactText()

template<class Vertex , class Edge >

elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::Szer_GraphCompactText	(	elementa::base::Serializer< Vertex > &	szerv,
		elementa::base::Serializer< Edge > &	szere
	)

inline

Constructor.

Configure the serializer.

Parameters

szerv	will be used to serialize the Vertex class. It must outlive the serializer since a reference is held inside it.
szere	will be used to serialize the Edge class. It must outlive the serializer since a reference is held inside it.

Definition at line 1124 of file graphs.h.

Member Function Documentation

◆ ser()

virtual void elementa::base::Serializer< Graph< Vertex, Edge > , void , void >::ser	(	OutSerCh &	chout,
		const Graph< Vertex, Edge > &	obj
	)

inlinevirtualinherited

Serializes an object, writing the resulting chars into CHOUT.

Must throw if any error during serialization, including channel errors (in that case, the channel can be left in the state it was when the error occurred).

Definition at line 206 of file serializers.h.

◆ deser()

virtual void elementa::base::Serializer< Graph< Vertex, Edge > , void , void >::deser	(	InSerCh &	chin,
		Graph< Vertex, Edge > &	obj
	)

inlinevirtualinherited

Deserializes an object from a sequence of chars in CHIN.

Must change the content of OBJ with the result. Throw if any error during serialization, including channel errors (in that case, the channel and the object are left in the state they were at the moment of the error).

Definition at line 214 of file serializers.h.

Typedef Documentation

◆ size_vertex

using elementa::adts::graphs::size_vertex = typedef size_t

#include <elementa/adts/graphs/graphs.h>

For holding numbers of vertices of a graph.

Definition at line 68 of file graphs.h.

◆ size_edge

using elementa::adts::graphs::size_edge = typedef size_t

#include <elementa/adts/graphs/graphs.h>

For holding numbers of edges of a graph.

Definition at line 71 of file graphs.h.

Function Documentation

◆ VectorOfVIts()

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::VectorOfVIts::VectorOfVIts ( const Graph & g )

#include <elementa/adts/graphs/graphs.h>

Fill vector with all vertices in G, forming a map from pos to verts.

This procedure is O(V), which cannot be improved since all the elements must be scanned to fill the map.

Definition at line 1162 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::end(), and elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll().

◆ VectorOfEIts()

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::VectorOfEIts::VectorOfEIts ( const Graph & g )

#include <elementa/adts/graphs/graphs.h>

Fill vector with all edges in G, forming a map from pos to edges.

This procedure is O(E), which cannot be improved since all the elements must be scanned to fill the map.

Definition at line 1180 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::end(), and elementa::adts::graphs::Graph< Vertex, Edge >::erangeAll().

◆ MapOfVItPos() [1/2]

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::MapOfVItPos::MapOfVItPos ( const Graph & g )

#include <elementa/adts/graphs/graphs.h>

Fill the map with the info in G.

This procedure is O(V), which cannot be improved since all the elements must be scanned to fill the map.

Definition at line 1198 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::end(), elementa::base::MultIterator< Data, BIDIR >::implementation(), and elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll().

◆ MapOfVItPos() [2/2]

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::MapOfVItPos::MapOfVItPos ( const VectorOfVIts & m )

#include <elementa/adts/graphs/graphs.h>

Fill the map with the info in M.

This serves to construct an inverse map THIS from a direct map M.

Definition at line 1211 of file graphs.h.

◆ MapOfEItPos() [1/2]

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::MapOfEItPos::MapOfEItPos ( const Graph & g )

#include <elementa/adts/graphs/graphs.h>

Fill the map with the info in G.

This procedure is O(E), which cannot be improved since all the elements must be scanned to fill the map.

Definition at line 1225 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::end(), elementa::adts::graphs::Graph< Vertex, Edge >::erangeAll(), and elementa::base::MultIterator< Data, BIDIR >::implementation().

◆ MapOfEItPos() [2/2]

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::MapOfEItPos::MapOfEItPos ( const VectorOfEIts & m )

#include <elementa/adts/graphs/graphs.h>

Fill the map with the info in M.

This serves to construct an inverse map THIS from a direct map M.

Definition at line 1238 of file graphs.h.

◆ begin() [1/2]

template<class Vertex , class Edge >

Graph< Vertex, Edge >::viterator elementa::adts::graphs::Graph< Vertex, Edge >::VRange_Pred::begin ( void ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Return the first vertex that satisfies the predicate, or end.

The first considered vertex is the destination of the parameter eit of the constructor of this range.

Implements elementa::base::Range< viterator >.

Definition at line 1253 of file graphs.h.

◆ end() [1/2]

template<class Vertex , class Edge >

Graph< Vertex, Edge >::viterator elementa::adts::graphs::Graph< Vertex, Edge >::VRange_Pred::end ( void ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Must return an iterator pointing past the last element.

Implements elementa::base::Range< viterator >.

Definition at line 1263 of file graphs.h.

◆ begin() [2/2]

template<class Vertex , class Edge >

Graph< Vertex, Edge >::eiterator elementa::adts::graphs::Graph< Vertex, Edge >::ERange_Pred::begin ( void ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Return the first edge that satisfies the predicate, or end.

The first edge to explore is the one provided in the eit parameter of the constructor of this range.

Implements elementa::base::Range< eiterator >.

Definition at line 1281 of file graphs.h.

◆ end() [2/2]

template<class Vertex , class Edge >

Graph< Vertex, Edge >::eiterator elementa::adts::graphs::Graph< Vertex, Edge >::ERange_Pred::end ( void ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Must return an iterator pointing past the last element.

Implements elementa::base::Range< eiterator >.

Definition at line 1291 of file graphs.h.

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

◆ forceBacktrack()

template<class Vertex , class Edge >

size_edge elementa::adts::graphs::Graph< Vertex, Edge >::ERange_DepthFirst::forceBacktrack ( eiterator & eit )

static

#include <elementa/adts/graphs/graphs.h>

Forces the given depth-first iterator to do backtrack.

A backtrack consists in looking for the next still unexplored sibling of the current edge; if it exists, the backtrack is over; otherwise, the top edge in the explored stack is popped and its next sibling is checked as before, and so on until either an unexplored sibling is found or no more edges can be explored. Return the number of edges already explored and now backtracked (i.e., 1 if the next sibling of the current edge is the result of the backtrack). The next consult on the iterator will return the already backtracked edge (i.e., no ++eit is needed after this). Throw bad_cast if EIT has not been generated from this range, i.e., if it is not a depth-first iterator. Undefined errors if EIT has no value.

Definition at line 1307 of file graphs.h.

References ELE_CODE_INVSTATE, elementa::base::MultIterator< Data, BIDIR >::implementation(), and elementa::base::MultIterator< Data, BIDIR >::valid().

◆ to_string() [1/4]

template<class Vertex , class Edge >

std::string elementa::adts::graphs::Graph< Vertex, Edge >::VItImpl_Pred::to_string ( void ) const

override

#include <elementa/adts/graphs/graphs.h>

Definition at line 1350 of file graphs.h.

◆ to_string() [2/4]

template<class Vertex , class Edge >

std::string elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_Pred::to_string ( void ) const

override

#include <elementa/adts/graphs/graphs.h>

Definition at line 1392 of file graphs.h.

◆ EItImpl_DepthFirst()

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::EItImpl_DepthFirst	(	Graph &	gr,
		const viterator &	vi,
		bool	beginorend = `true`
	)

#include <elementa/adts/graphs/graphs.h>

Definition at line 1418 of file graphs.h.

◆ operator*() [1/2]

template<class Vertex , class Edge >

Edge & elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::operator* ( void )

#include <elementa/adts/graphs/graphs.h>

Definition at line 1433 of file graphs.h.

◆ pointedData() [1/2]

template<class Vertex , class Edge >

Edge * elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::pointedData ( void ) const

#include <elementa/adts/graphs/graphs.h>

Definition at line 1440 of file graphs.h.

◆ operator++() [1/2]

template<class Vertex , class Edge >

Graph< Vertex, Edge >::EItImpl_DepthFirst & elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::operator++ ( void )

#include <elementa/adts/graphs/graphs.h>

Definition at line 1482 of file graphs.h.

◆ to_string() [3/4]

template<class Vertex , class Edge >

std::string elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_DepthFirst::to_string ( void ) const

override

#include <elementa/adts/graphs/graphs.h>

Definition at line 1502 of file graphs.h.

◆ EItImpl_BreadthFirst()

template<class Vertex , class Edge >

elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::EItImpl_BreadthFirst	(	Graph &	gr,
		const viterator &	vi,
		bool	beginorend = `true`
	)

#include <elementa/adts/graphs/graphs.h>

Definition at line 1526 of file graphs.h.

◆ operator*() [2/2]

template<class Vertex , class Edge >

Edge & elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::operator* ( void )

#include <elementa/adts/graphs/graphs.h>

Definition at line 1541 of file graphs.h.

◆ pointedData() [2/2]

template<class Vertex , class Edge >

Edge * elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::pointedData ( void ) const

#include <elementa/adts/graphs/graphs.h>

Definition at line 1548 of file graphs.h.

◆ operator++() [2/2]

template<class Vertex , class Edge >

Graph< Vertex, Edge >::EItImpl_BreadthFirst & elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::operator++ ( void )

#include <elementa/adts/graphs/graphs.h>

Definition at line 1558 of file graphs.h.

◆ to_string() [4/4]

template<class Vertex , class Edge >

std::string elementa::adts::graphs::Graph< Vertex, Edge >::EItImpl_BreadthFirst::to_string ( void ) const

override

#include <elementa/adts/graphs/graphs.h>

Definition at line 1583 of file graphs.h.

◆ connected()

template<class Vertex , class Edge >

Graph< Vertex, Edge >::eiterator elementa::adts::graphs::Graph< Vertex, Edge >::connected	(	const viterator &	v0,
		const viterator &	v1,
		const EPred &	epred = `trivial_epred`
	)		const

virtual

#include <elementa/adts/graphs/graphs.h>

Return the first edge that connects V0 to V1 or erangeLeaving().end().

Only checks edges leaving V0 to V1 that satisfy EPRED. This base implementation is O(E), where E is the number of leaving edges from V0 (assuming the iteration on leaving edges of a node is O(1)).

Definition at line 1662 of file graphs.h.

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

◆ find_vertex()

template<class Vertex , class Edge >

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

virtual

#include <elementa/adts/graphs/graphs.h>

Look for the first vertex that contains the given data.

Return VRange_All().end() if not found. This base method is O(V) (assuming the iteration of vertices of the graph is O(1)).

Definition at line 1677 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), and elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll().

◆ find_edge()

template<class Vertex , class Edge >

Graph< Vertex, Edge >::eiterator elementa::adts::graphs::Graph< Vertex, Edge >::find_edge ( const Edge & e ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Look for the first edge that contains the given data.

Return ERange_All().end() if not found. This base method is O(E) (assuming the iteration of edges of the graph is O(1)).

Definition at line 1686 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::begin(), and elementa::adts::graphs::Graph< Vertex, Edge >::erangeAll().

◆ toLastChild()

template<class Vertex , class Edge >

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

noexcept

#include <elementa/adts/graphs/graphs.h>

Return whether the given edge iterator points to the last child of VIT.

This method does a search on all children of VIT.

Definition at line 1694 of file graphs.h.

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

◆ vertexToPos()

template<class Vertex , class Edge >

size_t elementa::adts::graphs::Graph< Vertex, Edge >::vertexToPos ( const viterator & vit ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Calculate a position of a single vertex from its iterator, from 0 to V-1.

This procedure is O(V) (assuming the iteration of vertices of the graph is O(1)). Derived implementations may provide more efficient versions. Use vertexToPosMap for more efficient implementations in case you need to consult more than sporadically positions of vertices. The returned position may be invalidated after modification of the graph.

See also: MapOfVItPos

Definition at line 1713 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), ELE_CODE_INTERNALERR, elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::end(), and elementa::base::MultIterator< Data, BIDIR >::to_string().

Referenced by elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::ser().

◆ posToVertex()

template<class Vertex , class Edge >

Graph< Vertex, Edge >::viterator elementa::adts::graphs::Graph< Vertex, Edge >::posToVertex ( size_t vpos ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Return the iterator correponding to the given position (from 0 to V-1).

This procedure is O(V) (assuming the iteration of vertices of the graph is O(1)). Derived implementations may provide more efficient versions. The returned iterator may be invalidated after modification of the graph.

See also: VectorOfVits

Definition at line 1732 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), ELE_CODE_INVARG, elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::end(), and elementa::adts::graphs::Graph< Vertex, Edge >::size_vertices().

◆ edgeToPos()

template<class Vertex , class Edge >

size_t elementa::adts::graphs::Graph< Vertex, Edge >::edgeToPos ( const eiterator & eit ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Calculate a position of a single edge from its iterator, from 0 to E-1.

This procedure is O(E) (assuming the iteration of edges of the graph is O(1)). Derived implementations may provide more efficient versions. Use edgeToPosMap for more efficient implementations in case you need to consult more than sporadically positions of edges. The returned position may be invalidated after modification of the graph.

See also: MapOfEItPos

Definition at line 1745 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::begin(), ELE_CODE_INTERNALERR, elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::end(), and elementa::base::MultIterator< Data, BIDIR >::to_string().

◆ posToEdge()

template<class Vertex , class Edge >

Graph< Vertex, Edge >::eiterator elementa::adts::graphs::Graph< Vertex, Edge >::posToEdge ( size_t epos ) const

virtual

#include <elementa/adts/graphs/graphs.h>

Return the iterator correponding to the given position (from 0 to E-1).

This procedure is O(E) (assuming the iteration of edges of the graph is O(1)). Derived implementations may provide more efficient versions. The returned iterator may be invalidated after modification of the graph.

See also: VectorOfEIts

Definition at line 1764 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::begin(), ELE_CODE_INVARG, elementa::adts::graphs::Graph< Vertex, Edge >::ERange_All::end(), and elementa::adts::graphs::Graph< Vertex, Edge >::size_edges().

◆ ser()

template<class Vertex , class Edge >

void elementa::adts::graphs::Szer_GraphCompactText< Vertex, Edge >::ser	(	elementa::base::OutSerCh &	chout,
		const GraphType &	graph
	)

#include <elementa/adts/graphs/graphs.h>

Serialization.

Definition at line 1784 of file graphs.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::connection(), ELE_CODE_PLACE, ELE_CODE_TRACE_OFF, elementa::adts::graphs::Graph< Vertex, Edge >::erangeAll(), elementa::base::Szer_IntText::ser(), elementa::base::serch_isgood(), elementa::adts::graphs::Graph< Vertex, Edge >::size_edges(), elementa::adts::graphs::Graph< Vertex, Edge >::size_vertices(), elementa::base::MultIterator< Data, BIDIR >::to_string(), elementa::adts::graphs::Graph< Vertex, Edge >::vertexToPos(), and elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll().

Description

Classes

Typedefs

Functions

Consulting methods

Numerical indexing methods

Class Documentation

◆ elementa::adts::graphs::Graph

Public Types

Public Member Functions

Protected Member Functions

Iterator ranges and therefore iterator behaviours

Member Typedef Documentation

◆ VertexType

◆ EdgeType

◆ viterator

◆ eiterator

◆ EPred

Member Function Documentation

◆ trivial_epred()

◆ nil_epred()

◆ empty()

◆ size_vertices()

◆ size_edges()

◆ isLeaf()

◆ toLeaf()

◆ origin()

◆ destination()

◆ connection()

◆ clear()

◆ insert()

◆ connect()

◆ unconnect() [1/2]

◆ unconnect() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ splice()

◆ vrangeAll()

◆ vrangePred()

◆ erangeAll()

◆ erangePred()

◆ erangeLeaving()

◆ erangeEntering()

◆ erangeDepthFirst()

◆ erangeBreadthFirst()

◆ clone()

◆ emptyClone()

◆ elementa::adts::graphs::Szer_GraphCompactText

Public Types

Public Member Functions

Member Typedef Documentation

◆ GraphType

◆ SType

◆ RDeserType

◆ RSerType

Constructor & Destructor Documentation

◆ Szer_GraphCompactText()

Member Function Documentation

◆ ser()

◆ deser()

Typedef Documentation

◆ size_vertex

◆ size_edge

Function Documentation

◆ VectorOfVIts()

◆ VectorOfEIts()

◆ MapOfVItPos() [1/2]

◆ MapOfVItPos() [2/2]

◆ MapOfEItPos() [1/2]

◆ MapOfEItPos() [2/2]

◆ begin() [1/2]

◆ end() [1/2]

◆ begin() [2/2]

◆ end() [2/2]

◆ forceBacktrack()

◆ to_string() [1/4]

◆ to_string() [2/4]

◆ EItImpl_DepthFirst()

◆ operator*() [1/2]

◆ pointedData() [1/2]