SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::k2_tree< k, t_bv, t_rank > Class Template Reference

A k^2-tree. More...

#include <k2_tree.hpp>

Public Types

typedef k2_tree_ns::idx_type idx_type
typedef k2_tree_ns::size_type size_type

Public Member Functions

 k2_tree ()=default
 k2_tree (std::vector< std::vector< int > > &matrix)
 Constructor.
 k2_tree (std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
 Constructor.
 k2_tree (std::string filename, size_type size=0)
 Constructor.
 k2_tree (k2_tree const &tr)
 k2_tree (k2_tree &&tr)
k2_treeoperator= (k2_tree &&tr)
 Move assignment operator.
k2_treeoperator= (k2_tree &tr)
 Assignment operator.
bool operator== (k2_tree const &tr) const
 Equal operator.
t_bv get_t ()
t_bv get_l ()
bool adj (idx_type i, idx_type j) const
 Indicates wheter node j is adjacent to node i or not.
std::vector< idx_typeneigh (idx_type i) const
 Returns a list of neighbors of node i.
std::vector< idx_typereverse_neigh (idx_type i) const
 Returns a list of reverse neighbors of node i.
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serialize to a stream.
void load (std::istream &in)
 Load from istream.
template<typename archive_t>
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal.
template<typename archive_t>
std::enable_if< cereal::traits::is_output_serializable< k2_tree, archive_t >::value, void >::type CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Load via cereal.

Protected Member Functions

void build_from_matrix (std::vector< std::vector< int > > const &matrix)
void _neigh (size_type n, idx_type row, idx_type col, size_type level, std::vector< idx_type > &acc) const
 Recursive function to retrieve list of neighbors.
void _reverse_neigh (size_type n, idx_type row, idx_type col, size_type level, std::vector< idx_type > &acc) const
 Recursive function to retrieve list of reverse neighbors.
void build_from_edges (std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
 Build a tree from an edges collection.

Detailed Description

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
class sdsl::k2_tree< k, t_bv, t_rank >

A k^2-tree.

A k^2-tree is a compact tree structure to represent a web graph. The structure takes advantage of large empty areas of the adjacency matrix of the graph.

References
[1] Brisaboa, N. R., Ladra, S., & Navarro, G. (2009, August): k2-trees for compact web graph representation. In International Symposium on String Processing and Information Retrieval (pp. 18-30). Springer Berlin Heidelberg.

Definition at line 49 of file k2_tree.hpp.

Member Typedef Documentation

◆ idx_type

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
typedef k2_tree_ns::idx_type sdsl::k2_tree< k, t_bv, t_rank >::idx_type

Definition at line 52 of file k2_tree.hpp.

◆ size_type

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
typedef k2_tree_ns::size_type sdsl::k2_tree< k, t_bv, t_rank >::size_type

Definition at line 53 of file k2_tree.hpp.

Constructor & Destructor Documentation

◆ k2_tree() [1/6]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
sdsl::k2_tree< k, t_bv, t_rank >::k2_tree ( )
default

◆ k2_tree() [2/6]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
sdsl::k2_tree< k, t_bv, t_rank >::k2_tree ( std::vector< std::vector< int > > & matrix)
inline

Constructor.

This constructos takes the graph adjacency matrix. The time complexity for this constructor is linear in the matrix size

Parameters
matrixAdjacency matrix of the graph. It must be a binary square matrix.

Definition at line 274 of file k2_tree.hpp.

◆ k2_tree() [3/6]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
sdsl::k2_tree< k, t_bv, t_rank >::k2_tree ( std::vector< std::tuple< idx_type, idx_type > > & edges,
const size_type size )
inline

Constructor.

This constructos takes a vector of edges describing the graph and the graph size. And takes linear time over the amount of edges to build the k_2 representation.

Parameters
edgesA vector with all the edges of the graph, it can not be empty.
sizeSize of the graph, all the nodes in edges must be within 0 and size ([0, size[).

Definition at line 301 of file k2_tree.hpp.

◆ k2_tree() [4/6]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
sdsl::k2_tree< k, t_bv, t_rank >::k2_tree ( std::string filename,
size_type size = 0 )
inline

Constructor.

This constructos expects a filename prefix. Two serialized int_vectors have to be present at filename.x and filename.y. Each pair x,y describes an edge of the graph, from the node x to the node y.

Parameters
filenameString with the prefix of the files filename.x, filename.y each of them containing a serialized int_vector<>.
sizeSize of the graph, all the nodes in the edges defined by the files must be within 0 and size ([0, size[). If size==0, the size will be taken as the max node in the edges.

Definition at line 322 of file k2_tree.hpp.

◆ k2_tree() [5/6]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
sdsl::k2_tree< k, t_bv, t_rank >::k2_tree ( k2_tree< k, t_bv, t_rank > const & tr)
inline

Definition at line 349 of file k2_tree.hpp.

◆ k2_tree() [6/6]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
sdsl::k2_tree< k, t_bv, t_rank >::k2_tree ( k2_tree< k, t_bv, t_rank > && tr)
inline

Definition at line 354 of file k2_tree.hpp.

Member Function Documentation

◆ _neigh()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
void sdsl::k2_tree< k, t_bv, t_rank >::_neigh ( size_type n,
idx_type row,
idx_type col,
size_type level,
std::vector< idx_type > & acc ) const
inlineprotected

Recursive function to retrieve list of neighbors.

Parameters
nSize of the submatrix in the next recursive step.
rowRow of interest in the current submatrix, this is the row corresponding the node we are looking neighbors for.
colColumn offset of the current submatrix in the global matrix.
levelPosition in k_t:k_l (k_l appended to k_t) of the node or leaf being processed at this step.
accAccumulator to store the neighbors found.

Definition at line 120 of file k2_tree.hpp.

◆ _reverse_neigh()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
void sdsl::k2_tree< k, t_bv, t_rank >::_reverse_neigh ( size_type n,
idx_type row,
idx_type col,
size_type level,
std::vector< idx_type > & acc ) const
inlineprotected

Recursive function to retrieve list of reverse neighbors.

Parameters
nSize of the submatrix in the next recursive step.
rowRow offset of the current submatrix in the global matrix.
colColumn of interest in the current submatrix, this is the column corresponding the node we are looking reverse neighbors for.
levelPosition in k_t:k_l (k_l appended to k_t) of the node or leaf being processed at this step.
accAccumulator to store the neighbors found.

Definition at line 148 of file k2_tree.hpp.

◆ adj()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
bool sdsl::k2_tree< k, t_bv, t_rank >::adj ( idx_type i,
idx_type j ) const
inline

Indicates wheter node j is adjacent to node i or not.

Parameters
iNode i.
jNode j.
Returns
true if there is an edge going from node i to node j, false otherwise.

Definition at line 419 of file k2_tree.hpp.

◆ build_from_edges()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
void sdsl::k2_tree< k, t_bv, t_rank >::build_from_edges ( std::vector< std::tuple< idx_type, idx_type > > & edges,
const size_type size )
inlineprotected

Build a tree from an edges collection.

This method takes a vector of edges describing the graph and the graph size. And takes linear time over the amount of edges to build the k_2 representation.

Parameters
edgesA vector with all the edges of the graph, it can not be empty.
sizeSize of the graph, all the nodes in edges must be within 0 and size ([0, size[).

Definition at line 176 of file k2_tree.hpp.

◆ build_from_matrix()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
void sdsl::k2_tree< k, t_bv, t_rank >::build_from_matrix ( std::vector< std::vector< int > > const & matrix)
inlineprotected

Definition at line 68 of file k2_tree.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
template<typename archive_t>
std::enable_if< cereal::traits::is_output_serializable< k2_tree, archive_t >::value, void >::type sdsl::k2_tree< k, t_bv, t_rank >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Load via cereal.

Definition at line 537 of file k2_tree.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
template<typename archive_t>
void sdsl::k2_tree< k, t_bv, t_rank >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Serialise (save) via cereal.

Definition at line 525 of file k2_tree.hpp.

◆ get_l()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
t_bv sdsl::k2_tree< k, t_bv, t_rank >::get_l ( )
inline

Definition at line 407 of file k2_tree.hpp.

◆ get_t()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
t_bv sdsl::k2_tree< k, t_bv, t_rank >::get_t ( )
inline

Definition at line 402 of file k2_tree.hpp.

◆ load()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
void sdsl::k2_tree< k, t_bv, t_rank >::load ( std::istream & in)
inline

Load from istream.

Serialize the k2_tree from the given istream.

Parameters
istreamStream to load the k2_tree from.

Definition at line 513 of file k2_tree.hpp.

◆ neigh()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
std::vector< idx_type > sdsl::k2_tree< k, t_bv, t_rank >::neigh ( idx_type i) const
inline

Returns a list of neighbors of node i.

Parameters
iNode to get neighbors from.
Returns
A list of neighbors of node i.

Definition at line 457 of file k2_tree.hpp.

◆ operator=() [1/2]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
k2_tree & sdsl::k2_tree< k, t_bv, t_rank >::operator= ( k2_tree< k, t_bv, t_rank > && tr)
inline

Move assignment operator.

Definition at line 360 of file k2_tree.hpp.

◆ operator=() [2/2]

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
k2_tree & sdsl::k2_tree< k, t_bv, t_rank >::operator= ( k2_tree< k, t_bv, t_rank > & tr)
inline

Assignment operator.

Definition at line 375 of file k2_tree.hpp.

◆ operator==()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
bool sdsl::k2_tree< k, t_bv, t_rank >::operator== ( k2_tree< k, t_bv, t_rank > const & tr) const
inline

Equal operator.

Definition at line 386 of file k2_tree.hpp.

◆ reverse_neigh()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
std::vector< idx_type > sdsl::k2_tree< k, t_bv, t_rank >::reverse_neigh ( idx_type i) const
inline

Returns a list of reverse neighbors of node i.

Parameters
iNode to get reverse neighbors from.
Returns
A list of reverse neighbors of node i.

Definition at line 474 of file k2_tree.hpp.

◆ serialize()

template<uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
size_type sdsl::k2_tree< k, t_bv, t_rank >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
std::string name = "" ) const
inline

Serialize to a stream.

Serialize the k2_tree data structure

Parameters
outOutstream to write the k2_tree.
v
string_name
Returns
The number of written bytes.

Definition at line 495 of file k2_tree.hpp.


The documentation for this class was generated from the following file:
  • /builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/k2_tree.hpp