An adjacency matrix for a given query graph. More...

#include <AdjacencyMatrix.hpp>

Collaboration diagram for m::AdjacencyMatrix:

Data Structures
struct	Proxy
	A proxy to access single entries in the `AdjacencyMatrix`. More...

Public Member Functions
	AdjacencyMatrix ()

	AdjacencyMatrix (std::size_t num_vertices)

	AdjacencyMatrix (const AdjacencyMatrix &)=default

	AdjacencyMatrix (AdjacencyMatrix &&)=default

AdjacencyMatrix &	operator= (AdjacencyMatrix &&)=default

Proxy< true >	operator() (std::size_t i, std::size_t j) const
	Returns the bit at position `(i, j)`.

Proxy< false >	operator() (std::size_t i, std::size_t j)
	Returns the bit at position `(i, j)`.

Proxy< true >	at (std::size_t i, std::size_t j) const

Proxy< false >	at (std::size_t i, std::size_t j)

SmallBitset	reachable (SmallBitset src) const
	Computes the set of nodes reachable from `src`, i.e. the set of nodes reachable from any node in `src`.

SmallBitset	reachable (SmallBitset src, SmallBitset S) const
	Computes the set of nodes in `S` reachable from `src`, i.e. the set of nodes in `S` reachable from any node in `src`.

SmallBitset	neighbors (SmallBitset S) const
	Computes the neighbors of `S`.

bool	is_connected (SmallBitset S) const
	Returns `true` iff the subproblem `S` is connected.

bool	is_connected (SmallBitset left, SmallBitset right) const
	Returns `true` iff there is at least one edge (join) between `left` and `right`.

AdjacencyMatrix	transitive_closure_directed () const
	Computes the transitive closure of this adjacency matrix.

AdjacencyMatrix	transitive_closure_undirected () const
	Computes the transitive closure of this adjacency matrix.

void	for_each_CSG_undirected (SmallBitset super, SmallBitset source, std::function< void(SmallBitset)> callback) const
	Enumerate all connected subgraphs (CSGs) of the graph induced by vertex super set `super`, starting only from nodes in `source`.

void	for_each_CSG_undirected (SmallBitset super, std::function< void(SmallBitset)> callback) const
	Enumerate all connected subgraphs (CSGs) of the graph induced by vertex super set `super`.

void	for_each_CSG_pair_undirected (SmallBitset super, std::function< void(SmallBitset, SmallBitset)> callback) const
	Enumerate all pairs of connected subgraphs (CSGs) that are connected by at least one edge.

AdjacencyMatrix	minimum_spanning_forest (std::function< double(std::size_t, std::size_t)> weight) const
	Computes the minimum spanning forest for this graph.

AdjacencyMatrix	tree_directed_away_from (SmallBitset root)
	Computes an `AdjacencyMatrix` with all edges directed away from `root`.

bool	operator== (const AdjacencyMatrix &other) const
	Compares two `AdjacencyMatrix`s element-wise.

bool	operator!= (const AdjacencyMatrix &other) const

void	print_fixed_length (std::ostream &out, unsigned length) const

void	dump (std::ostream &out) const

void	dump () const

Private Attributes
std::array< SmallBitset, SmallBitset::CAPACITY >	m_
	matrix entries

std::size_t	num_vertices_ = 0
	number of sources of the `QueryGraph` represented by this matrix

Friends
M_LCOV_EXCL_START friend std::ostream &	operator<< (std::ostream &out, const AdjacencyMatrix &M)

std::string	to_string (const AdjacencyMatrix &M)

Detailed Description

An adjacency matrix for a given query graph.

Represents the join graph.

Definition at line 10 of file AdjacencyMatrix.hpp.

Constructor & Destructor Documentation

◆ AdjacencyMatrix() [1/4]

m::AdjacencyMatrix::AdjacencyMatrix ( )

inline

Definition at line 65 of file AdjacencyMatrix.hpp.

◆ AdjacencyMatrix() [2/4]

m::AdjacencyMatrix::AdjacencyMatrix ( std::size_t num_vertices )

inline

Definition at line 66 of file AdjacencyMatrix.hpp.

◆ AdjacencyMatrix() [3/4]

m::AdjacencyMatrix::AdjacencyMatrix ( const AdjacencyMatrix & )

explicitdefault

◆ AdjacencyMatrix() [4/4]

m::AdjacencyMatrix::AdjacencyMatrix ( AdjacencyMatrix && )

default

Member Function Documentation

◆ at() [1/2]

Proxy< false > m::AdjacencyMatrix::at	(	std::size_t	i,
		std::size_t	j
	)

inline

Definition at line 85 of file AdjacencyMatrix.hpp.

◆ at() [2/2]

Proxy< true > m::AdjacencyMatrix::at	(	std::size_t	i,
		std::size_t	j
	)		const

inline

Definition at line 79 of file AdjacencyMatrix.hpp.

◆ dump() [1/2]

void AdjacencyMatrix::dump ( ) const

Definition at line 140 of file AdjacencyMatrix.cpp.

References dump().

Referenced by dump().

◆ dump() [2/2]

M_LCOV_EXCL_START void AdjacencyMatrix::dump ( std::ostream & out ) const

Definition at line 139 of file AdjacencyMatrix.cpp.

◆ for_each_CSG_pair_undirected()

void m::AdjacencyMatrix::for_each_CSG_pair_undirected	(	SmallBitset	super,
		std::function< void(SmallBitset, SmallBitset)>	callback
	)		const

inline

Enumerate all pairs of connected subgraphs (CSGs) that are connected by at least one edge.

Requires that this matrix is symmetric.

Definition at line 190 of file AdjacencyMatrix.hpp.

References m::SmallBitset::hi(), and m::SmallBitset::mask_to_lo().

Referenced by generate_correlated_cardinalities(), generate_uncorrelated_cardinalities(), m::pe::DPccp::operator()(), and m::Optimizer::optimize_join_order().

◆ for_each_CSG_undirected() [1/2]

void m::AdjacencyMatrix::for_each_CSG_undirected	(	SmallBitset	super,
		SmallBitset	source,
		std::function< void(SmallBitset)>	callback
	)		const

inline

Enumerate all connected subgraphs (CSGs) of the graph induced by vertex super set super, starting only from nodes in source.

Definition at line 158 of file AdjacencyMatrix.hpp.

References m::SmallBitset::begin(), m::SmallBitset::end(), m::SmallBitset::is_singleton(), m::least_subset(), M_insist, m::SmallBitset::mask_to_lo(), and m::next_subset().

Referenced by main(), and m::Optimizer::optimize_join_order().

◆ for_each_CSG_undirected() [2/2]

void m::AdjacencyMatrix::for_each_CSG_undirected	(	SmallBitset	super,
		std::function< void(SmallBitset)>	callback
	)		const

inline

Enumerate all connected subgraphs (CSGs) of the graph induced by vertex super set super.

Requires that this matrix is symmetric.

Definition at line 184 of file AdjacencyMatrix.hpp.

◆ is_connected() [1/2]

bool m::AdjacencyMatrix::is_connected	(	SmallBitset	left,
		SmallBitset	right
	)		const

inline

Returns true iff there is at least one edge (join) between left and right.

Definition at line 136 of file AdjacencyMatrix.hpp.

References m::SmallBitset::empty().

◆ is_connected() [2/2]

bool m::AdjacencyMatrix::is_connected ( SmallBitset S ) const

inline

Returns true iff the subproblem S is connected.

S is connected iff any node in S can reach all other nodes of S using only nodes in S. Assumes AdjacencyMatrix is symmetric, i.e. edges are undirected.

Definition at line 133 of file AdjacencyMatrix.hpp.

References m::SmallBitset::begin().

Referenced by m::pe::GOO::for_each_join(), generate_uncorrelated_cardinalities(), IKKBZ::linearize(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), m::pe::hs::expansions::BottomUpComplete::operator()(), DPsize::operator()(), DPsizeOpt::operator()(), DPsizeSub::operator()(), DPsub::operator()(), DPsubOpt::operator()(), LinearizedDP::operator()(), and TDbasic::PlanGen().

◆ minimum_spanning_forest()

AdjacencyMatrix AdjacencyMatrix::minimum_spanning_forest ( std::function< double(std::size_t, std::size_t)> weight ) const

Computes the minimum spanning forest for this graph.

Expects the graph to be undirected, meaning that the AdjacencyMatrix must be symmetric.

Definition at line 64 of file AdjacencyMatrix.cpp.

References m::SmallBitset::All(), m::SmallBitset::begin(), m::SmallBitset::is_singleton(), M_insist, neighbors(), num_vertices_, and m::SmallBitset::Singleton().

Referenced by IKKBZ::linearize().

◆ neighbors()

SmallBitset m::AdjacencyMatrix::neighbors ( SmallBitset S ) const

inline

Computes the neighbors of S.

Nodes from S are not part of the neighborhood.

Definition at line 123 of file AdjacencyMatrix.hpp.

Referenced by m::pe::hs::goo_path_completion(), m::pe::hs::heuristic_search(), IKKBZ::linearize(), m::MinCutAGaT::min_cut_advanced_generate_and_test(), minimum_spanning_forest(), m::pe::hs::heuristics::bottomup_lookahead_cheapest< PlanTable, State >::operator()(), m::pe::hs::heuristics::GOO< PlanTable, State, BottomUp >::operator()(), m::pe::hs::expansions::BottomUpComplete::operator()(), m::pe::GOO::operator()(), and tree_directed_away_from().

◆ operator!=()

bool m::AdjacencyMatrix::operator!= ( const AdjacencyMatrix & other ) const

inline

Definition at line 219 of file AdjacencyMatrix.hpp.

◆ operator()() [1/2]

Proxy< false > m::AdjacencyMatrix::operator()	(	std::size_t	i,
		std::size_t	j
	)

inline

Returns the bit at position (i, j).

Both i and j must be in bounds.

Definition at line 77 of file AdjacencyMatrix.hpp.

◆ operator()() [2/2]

Proxy< true > m::AdjacencyMatrix::operator()	(	std::size_t	i,
		std::size_t	j
	)		const

inline

Returns the bit at position (i, j).

Both i and j must be in bounds.

Definition at line 74 of file AdjacencyMatrix.hpp.

◆ operator=()

AdjacencyMatrix & m::AdjacencyMatrix::operator= ( AdjacencyMatrix && )

default

◆ operator==()

bool m::AdjacencyMatrix::operator== ( const AdjacencyMatrix & other ) const

inline

Compares two AdjacencyMatrixs element-wise.

Definition at line 211 of file AdjacencyMatrix.hpp.

References m_, and num_vertices_.

◆ print_fixed_length()

void m::AdjacencyMatrix::print_fixed_length	(	std::ostream &	out,
		unsigned	length
	)		const

inline

Definition at line 233 of file AdjacencyMatrix.hpp.

References M_insist.

◆ reachable() [1/2]

SmallBitset m::AdjacencyMatrix::reachable ( SmallBitset src ) const

inline

Computes the set of nodes reachable from src, i.e. the set of nodes reachable from any node in src.

Definition at line 92 of file AdjacencyMatrix.hpp.

Referenced by m::MinCutAGaT::min_cut_advanced_generate_and_test().

◆ reachable() [2/2]

SmallBitset m::AdjacencyMatrix::reachable	(	SmallBitset	src,
		SmallBitset	S
	)		const

inline

Computes the set of nodes in S reachable from src, i.e. the set of nodes in S reachable from any node in src.

Definition at line 108 of file AdjacencyMatrix.hpp.

◆ transitive_closure_directed()

AdjacencyMatrix AdjacencyMatrix::transitive_closure_directed ( ) const

Computes the transitive closure of this adjacency matrix.

That is, compute for each pair of vertices *(i, j)* whether j can be reached from i by any finite path. Treats edges as directed and hence does not exploit symmetry.

Definition at line 13 of file AdjacencyMatrix.cpp.

References m_, M_insist, num_vertices_, and m::SmallBitset::Singleton().

◆ transitive_closure_undirected()

AdjacencyMatrix AdjacencyMatrix::transitive_closure_undirected ( ) const

Computes the transitive closure of this adjacency matrix.

That is, compute for each pair of vertices *(i, j)* whether j can be reached from i by any finite path. Expects that this AdjacencyMatrix is symmetric, i.e. that the original graph is undirected.

Definition at line 41 of file AdjacencyMatrix.cpp.

References m_, M_insist, and num_vertices_.

◆ tree_directed_away_from()

AdjacencyMatrix AdjacencyMatrix::tree_directed_away_from ( SmallBitset root )

Computes an AdjacencyMatrix with all edges directed away from root.

Requires that the graph is a tree, i.e. connected and acyclic.

Definition at line 122 of file AdjacencyMatrix.cpp.

References m::SmallBitset::empty(), m::SmallBitset::is_singleton(), m_, M_insist, neighbors(), num_vertices_, and m::X.

Friends And Related Function Documentation

◆ operator<<

M_LCOV_EXCL_START friend std::ostream & operator<<	(	std::ostream &	out,
		const AdjacencyMatrix &	M
	)

friend

Definition at line 222 of file AdjacencyMatrix.hpp.

◆ to_string

std::string to_string ( const AdjacencyMatrix & M )

friend

Definition at line 227 of file AdjacencyMatrix.hpp.

Field Documentation

◆ m_

std::array<SmallBitset, SmallBitset::CAPACITY> m::AdjacencyMatrix::m_

private

matrix entries

Definition at line 61 of file AdjacencyMatrix.hpp.

Referenced by operator==(), transitive_closure_directed(), transitive_closure_undirected(), and tree_directed_away_from().

◆ num_vertices_

std::size_t m::AdjacencyMatrix::num_vertices_ = 0

private

number of sources of the QueryGraph represented by this matrix

Definition at line 62 of file AdjacencyMatrix.hpp.

Referenced by minimum_spanning_forest(), operator==(), transitive_closure_directed(), transitive_closure_undirected(), and tree_directed_away_from().

The documentation for this struct was generated from the following files:

include/mutable/util/AdjacencyMatrix.hpp
src/util/AdjacencyMatrix.cpp

Data Structures

Public Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ AdjacencyMatrix() [1/4]

◆ AdjacencyMatrix() [2/4]

◆ AdjacencyMatrix() [3/4]

◆ AdjacencyMatrix() [4/4]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ dump() [1/2]

◆ dump() [2/2]

◆ for_each_CSG_pair_undirected()

◆ for_each_CSG_undirected() [1/2]

◆ for_each_CSG_undirected() [2/2]

◆ is_connected() [1/2]

◆ is_connected() [2/2]

◆ minimum_spanning_forest()

◆ neighbors()

◆ operator!=()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator=()

◆ operator==()

◆ print_fixed_length()

◆ reachable() [1/2]

◆ reachable() [2/2]

◆ transitive_closure_directed()

◆ transitive_closure_undirected()

◆ tree_directed_away_from()

Friends And Related Function Documentation

◆ operator<<

◆ to_string

Field Documentation

◆ m_

◆ num_vertices_