lal::properties::branchless_path Class Reference

Branchless paths in trees. More...

#include <branchless_path.hpp>

Public Member Functions
void	init (std::size_t n) noexcept
	Initializes this path.
void	add_node (node u) noexcept
	Adds a node to this path.
void	set_h1 (node h) noexcept
	Sets the first vertex of degree different from 2.
void	set_h2 (node h) noexcept
	Sets the second vertex of degree different from 2.
void	set_lowest_lexicographic (node l) noexcept
	Set lowest lexicographic vertex.
node	operator[] (std::size_t i) const noexcept
	Access the i-th node in the path.
node	get_h1 () const noexcept
	Gets the first vertex of degree different from 2.
node	get_h2 () const noexcept
	Gets the second vertex of degree different from 2.
bool	has_lowest_lexicographic () const noexcept
	Does this path have a lowest lexicographic vertex?
node	get_lowest_lexicographic () const noexcept
	Gets the lowest lexicographic vertex.
const std::vector< node > &	get_vertex_sequence () const noexcept
	Gets the vertex sequence of this path as a vector.
std::size_t	get_num_nodes () const noexcept
	Number of vertices in this path.
std::size_t	get_num_edges () const noexcept
	Number of edges in this path.
bool	has_node (node u) const noexcept
	Does this path include node u?
std::size_t	get_position (node u) const noexcept
	Returns the get_position of node u in m_vertex_sequence.
template<class graph_t >
bool	is_antenna (const graph_t &t) const noexcept
	Is the given path an antenna?

Private Attributes
detail::array< char >	m_vertex_set
	A 0-1 array to indicate if a vertex belongs to this path or not.
detail::array< std::size_t >	m_position
	The position in m_vertex_sequence of each vertex.
std::vector< node >	m_vertex_sequence
	The vertex sequence of this branchless path (includes h1 and h2).
node	m_h1
	The first endpoint of this path.
node	m_h2
	The second endpoint of this path.
std::optional< node >	m_lowest_lexicographic
	The internal vertex with lowest index lexicographically.

Detailed Description

Branchless paths in trees.

A branchless path in a tree is a sequence of vertices of degree two, enclosed by (at most) two vertices of degree different from two. The path graph is a branchless path itself. The legs of a spider graph are all branchless paths, which include the center of the spider.

Before adding vertices to this path, it must be initialized via function init.

The vertices in each branchless path are of two categories: internal and endpoints. The endpoints of the path are the only two vertices of degree different from two. The internal vertices are the (possibly 0) vertices of degree 2.

Member Function Documentation

add_node()

void lal::properties::branchless_path::add_node ( node u )

inlinenoexcept

Adds a node to this path.

Parameters

u	Node to be added.

Postcondition

m_vertex_set and m_vertex_sequence are updated.

get_lowest_lexicographic()

node lal::properties::branchless_path::get_lowest_lexicographic ( ) const

inlinenodiscardnoexcept

Gets the lowest lexicographic vertex.

Returns

The lowest vertex in the lexicographic order.

Precondition

This method should only be called when has_lowest_lexicographic returns true.

get_num_edges()

std::size_t lal::properties::branchless_path::get_num_edges ( ) const

inlinenodiscardnoexcept

Number of edges in this path.

The number of edges includes the edges incident to the endpoints.

Returns

The number of edges.

get_num_nodes()

std::size_t lal::properties::branchless_path::get_num_nodes ( ) const

inlinenodiscardnoexcept

Number of vertices in this path.

The number of vertices includes the endpoints.

Returns

The number of vertices.

get_vertex_sequence()

const std::vector< node > & lal::properties::branchless_path::get_vertex_sequence ( ) const

inlinenodiscardnoexcept

Gets the vertex sequence of this path as a vector.

This sequence includes vertices m_h1 and m_h2 (returned by get_h1 and get_h2 and are returned sequentially, that is, in the order they are found in the tree.

Returns

A vector with all nodes in the path.

has_lowest_lexicographic()

bool lal::properties::branchless_path::has_lowest_lexicographic ( ) const

inlinenodiscardnoexcept

Does this path have a lowest lexicographic vertex?

This method only returns true when the vertex sequence has 3 or more vertices.

Returns

True if the path has a lowest lexicographic. False, if otherwise.

init()

void lal::properties::branchless_path::init ( std::size_t n )

inlinenoexcept

Initializes this path.

Parameters

n	Number of nodes of the tree.

Postcondition

Nodes m_lowest_lexicographic, m_h1 and m_h2 have been initialized.

Memory for m_vertex_set has been allocated.

is_antenna()

template<class graph_t >

bool lal::properties::branchless_path::is_antenna ( const graph_t & t ) const

inlinenodiscardnoexcept

Is the given path an antenna?

A branchless path is an antenna if any of its two endpoints is a degree-1 vertex.

Template Parameters

tree_t

The type of tree.

Parameters

t	The tree of which bp is a path.

Returns

True if bp is an antenna. False if it is not.

Member Data Documentation

m_lowest_lexicographic

std::optional<node> lal::properties::branchless_path::m_lowest_lexicographic

private

The internal vertex with lowest index lexicographically.

This vertex may not exist. See has_lowest_lexicographic.

---

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

• lal/properties/branchless_path.hpp