#include <quetzal/coalescence/graph/network.hpp>

Detailed Description

template<class VertexProperty, class EdgeProperty>
requires (!std::is_same_v<VertexProperty, no_property> && !std::is_same_v<EdgeProperty, no_property>)
class quetzal::coalescence::network< VertexProperty, EdgeProperty >

A network class with information attached to vertices.

Template Parameters

VertexProperty	The type of information to store at each vertex.
EdgeProperty	The type of information to store at each edge.

This class can be used as a simple way to describe the kind of topology and mutational process that emerge from evolutionary relationships between a sample of sequences for a non-recombining locus. Vertices and edges embed additional information as user-defined types. This graph structure is bidirected and allows to model a forest of disconnected networks and isolated vertices.

Invariant: Guarantees that each vertex \(v\) has exactly \(0\) or \(n \geq 2\) successors, never \(1\).; Guarantees that each vertex \(v\) has exactly \(0\) or \(1\) predecessor.; Guarantees that if \((u,v)\) is an edge of the graph, then \((v,u)\) is also an edge.

Remarks: As it would be too costly to enforce non-cyclicity, it is left to the user responsability not to introduce any cycle.

Example

Output

Public Types
using	edge_descriptor = typename base::edge_descriptor
	Edge descriptor.

using	vertex_descriptor = typename base::vertex_descriptor
	Vertex descriptor.

using	vertex_property = VertexProperty
	Vertex information.

using	edge_property = EdgeProperty
	Edge information.

using	degree_size_type = typename base::degree_size_type
	Degree size type.

using	traversal_category = typename base::traversal_category
	The ways in which the vertices in the graph can be traversed.

using	directed_category = typename base::directed_category
	The graph is bidirected.

using	in_edge_iterator = typename base::in_edge_iterator
	Iterate through the in-edges.

using	out_edge_iterator = typename base::out_edge_iterator
	Iterate through the out-edges.

using	edge_parallel_category = typename base::edge_parallel_category

Public Member Functions
Constructors
	network ()
	Default constructor. Initializes a graph with 0 vertices.

	network (size_t n)
	Construct graph with \(n\) vertices.

Topology Modifiers
vertex_descriptor	add_vertex (const VertexProperty &p)
	Add a vertex and its properties to the graph.

std::vector< edge_descriptor >	add_edges (vertex_descriptor parent, std::vector< std::tuple< vertex_descriptor, EdgeProperty > > children)
	Add edges from the parent vertex (source) to the children (target)

Property Lookup
const VertexProperty &	operator[] (vertex_descriptor v) const
	Read only access to the vertex property.

VertexProperty &	operator[] (vertex_descriptor v)
	Read and write access to the vertex property.

const EdgeProperty &	operator[] (const edge_descriptor &edge) const
	Read only access to the edge property.

EdgeProperty &	operator[] (const edge_descriptor &edge)
	Read and write access to the edge property.

Topology Lookup
bool	is_isomorphic (network_common const &other) const
	Detects if there is a 1-to-1 mapping of the vertices in one graph to the vertices of another graph such that adjacency is preserved.

vertex_descriptor	find_root_from (vertex_descriptor u) const
	Finds the root of the network graph starting from a vertex \(u\).

degree_size_type	degree (vertex_descriptor u) const
	Returns the number of in-edges plus out-edges.

degree_size_type	in_degree (vertex_descriptor u) const
	Returns the number of in-edges of vertex \(u\).

degree_size_type	out_degree (vertex_descriptor v) const
	Returns the number of out-edges of vertex \(v\).

bool	has_predecessor (vertex_descriptor u) const
	Evaluates if vertex \(u\) has a predecessor.

vertex_descriptor	predecessor (vertex_descriptor u) const
	The predecessor of vertex \(u\).

bool	has_successors (vertex_descriptor u) const
	Evaluates if vertex \(u\) has successors.

auto	successors (vertex_descriptor u) const
	The successors of vertex \(u\).

std::optional< edge_descriptor >	edge (vertex_descriptor u, vertex_descriptor v) const
	Returns the edge between two vertices of the graph if the edge exists.

vertex_descriptor	source (edge_descriptor e) const
	Returns the source vertex of a directed edge.

vertex_descriptor	target (edge_descriptor e) const
	Returns the target vertex of a directed edge.

Topology Modification
vertex_descriptor	add_vertex ()

void	clear_vertex (vertex_descriptor u)
	Remove all edges to and from vertex \(u\) from the graph.

void	remove_vertex (vertex_descriptor u)
	Remove vertex u from the graph, also removing all edges to and from vertex \(u\).

edge_descriptor	add_edge (vertex_descriptor u, vertex_descriptor v)
	Inserts the edge \((u,v)\) into the graph if it does not exist, and returns an edge descriptor pointing to the new edge.

void	remove_edge (vertex_descriptor u, vertex_descriptor v)
	Remove the edge \((u,v)\) from the graph.

void	remove_edge (edge_descriptor e)
	Remove the edge \(e\) from the graph.

Iterators
auto	in_edges (vertex_descriptor u) const
	Provides a range to iterate over the in-going edges of vertex \(u\).

auto	out_edges (vertex_descriptor u) const
	Provides a range to iterate over the out-going edges of vertex \(u\).

auto	vertices () const
	Provides a range to iterate over the vertices of the graph.

Algorithms
void	depth_first_search (vertex_descriptor start, DFSVisitor &vis)
	Performs a read-and-write depth-first traversal of the vertices starting at vertex \(s\).

void	depth_first_search (vertex_descriptor start, DFSVisitor &vis) const
	Performs a read-only depth-first traversal of the vertices starting at vertex \(s\).

Input/Output
void	to_graphviz (std::ostream &out) const
	Print the graph to the graphviz format.

Static Public Member Functions
static constexpr vertex_descriptor	null_vertex ()
	Null vertex identifier.

Protected Attributes
base	_graph

Member Function Documentation

◆ add_edge()

edge_descriptor quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::add_edge	(	vertex_descriptor	u,
		vertex_descriptor	v
	)

inlineinherited

Inserts the edge \((u,v)\) into the graph if it does not exist, and returns an edge descriptor pointing to the new edge.

Parameters

u	Source vertex
u	Target vertex

◆ clear_vertex()

void quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::clear_vertex ( vertex_descriptor u )

inlineinherited

Remove all edges to and from vertex \(u\) from the graph.

Parameters

u	The vertex

◆ degree()

degree_size_type quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::degree ( vertex_descriptor u ) const

inlineinherited

Returns the number of in-edges plus out-edges.

Parameters

u	The vertex \(u\)

Returns: Returns the number of in-edges plus out-edges.

◆ depth_first_search() [1/2]

void quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::depth_first_search	(	vertex_descriptor	start,
		DFSVisitor &	vis
	)

inlineinherited

Performs a read-and-write depth-first traversal of the vertices starting at vertex \(s\).

Template Parameters

DFSVisitor

Parameters

start	The vertex to start from.
vis	The visitor to apply.

◆ depth_first_search() [2/2]

void quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::depth_first_search	(	vertex_descriptor	start,
		DFSVisitor &	vis
	)		const

inlineinherited

Performs a read-only depth-first traversal of the vertices starting at vertex \(s\).

Template Parameters

DFSVisitor

Parameters

start	The vertex to start from.
vis	The visitor to apply.

◆ edge()

std::optional< edge_descriptor > quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::edge	(	vertex_descriptor	u,
		vertex_descriptor	v
	)		const

inlineinherited

Returns the edge between two vertices of the graph if the edge exists.

Parameters

u	The first vertex
u	The second vertex

Returns: An optional edge descriptor \(e\).

◆ find_root_from()

vertex_descriptor quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::find_root_from ( vertex_descriptor u ) const

inlineinherited

Finds the root of the network graph starting from a vertex \(u\).

Parameters

u	The vertex to start from.

Remarks: This function will be an infinite loop if called on a recurrent network

◆ has_predecessor()

bool quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::has_predecessor ( vertex_descriptor u ) const

inlineinherited

Evaluates if vertex \(u\) has a predecessor.

Parameters

u	The vertex to evaluate

Returns: True if u has a predecessor, false otherwise

◆ has_successors()

bool quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::has_successors ( vertex_descriptor u ) const

inlineinherited

Evaluates if vertex \(u\) has successors.

Parameters

u	The vertex to evaluate

Returns: True if u has successors, false otherwise

◆ in_degree()

degree_size_type quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::in_degree ( vertex_descriptor u ) const

inlineinherited

Returns the number of in-edges of vertex \(u\).

Parameters

u	The vertex \(u\)

Returns: The number of in-edges.

◆ in_edges()

auto quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::in_edges ( vertex_descriptor u ) const

inlineinherited

Provides a range to iterate over the in-going edges of vertex \(u\).

Parameters

u	The vertex \(u\).

Returns: A range

◆ is_isomorphic()

bool quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::is_isomorphic ( network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > > const & other ) const

inlineinherited

Detects if there is a 1-to-1 mapping of the vertices in one graph to the vertices of another graph such that adjacency is preserved.

Parameters

other A network graph.

Returns: true if there exists an isomorphism between the two graphs and false otherwise

◆ null_vertex()

static constexpr vertex_descriptor quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::null_vertex ( )

inlinestaticconstexprinherited

Null vertex identifier.

Returns: A null vertex

◆ out_edges()

auto quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::out_edges ( vertex_descriptor u ) const

inlineinherited

Provides a range to iterate over the out-going edges of vertex \(u\).

Parameters

u	The vertex \(u\).

Returns: A range

◆ predecessor()

vertex_descriptor quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::predecessor ( vertex_descriptor u ) const

inlineinherited

The predecessor of vertex \(u\).

Parameters

u	The vertex

Returns: The vertex that is the predecessor of \(u\).

◆ remove_edge() [1/2]

void quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::remove_edge ( edge_descriptor e )

inlineinherited

Remove the edge \(e\) from the graph.

Parameters

e	The edge to remove

◆ remove_edge() [2/2]

void quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::remove_edge	(	vertex_descriptor	u,
		vertex_descriptor	v
	)

inlineinherited

Remove the edge \((u,v)\) from the graph.

Parameters

u	Source vertex
u	Target vertex

◆ remove_vertex()

void quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::remove_vertex ( vertex_descriptor u )

inlineinherited

Remove vertex u from the graph, also removing all edges to and from vertex \(u\).

Parameters

u	The vertex to remove.

◆ source()

vertex_descriptor quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::source ( edge_descriptor e ) const

inlineinherited

Returns the source vertex of a directed edge.

Parameters

e The edge

Returns: The source vertex of the edge \(e\).

◆ successors()

auto quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::successors ( vertex_descriptor u ) const

inlineinherited

The successors of vertex \(u\).

Parameters

u	The vertex

Returns: A pair of iterators on the vertices that are the successors of \(u\).

◆ target()

vertex_descriptor quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::target ( edge_descriptor e ) const

inlineinherited

Returns the target vertex of a directed edge.

Parameters

e The edge

Returns: The target vertex of the edge \(e\).

◆ vertices()

auto quetzal::coalescence::detail::network_common< VertexProperty, EdgeProperty, network< no_property, EdgeProperty > >::vertices ( ) const

inlineinherited

Provides a range to iterate over the vertices of the graph.

Returns: A range

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

/home/runner/work/quetzal-CoaTL/quetzal-CoaTL/src/include/quetzal/coalescence/graph/network.hpp

Detailed Description

Example

Output

Public Types

Public Member Functions

Static Public Member Functions

Protected Attributes

Member Function Documentation

◆ add_edge()

◆ clear_vertex()

◆ degree()

◆ depth_first_search() [1/2]

◆ depth_first_search() [2/2]

◆ edge()

◆ find_root_from()

◆ has_predecessor()

◆ has_successors()

◆ in_degree()

◆ in_edges()

◆ is_isomorphic()

◆ null_vertex()

◆ out_edges()

◆ predecessor()

◆ remove_edge() [1/2]

◆ remove_edge() [2/2]

◆ remove_vertex()

◆ source()

◆ successors()

◆ target()

◆ vertices()