SDSL 3.0.1
Succinct Data Structure Library
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. More...
 
 k2_tree (std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
 Constructor. More...
 
 k2_tree (std::string filename, size_type size=0)
 Constructor. More...
 
 k2_tree (const k2_tree &tr)
 
 k2_tree (k2_tree &&tr)
 
k2_treeoperator= (k2_tree &&tr)
 Move assignment operator. More...
 
k2_treeoperator= (k2_tree &tr)
 Assignment operator. More...
 
bool operator== (const k2_tree &tr) const
 Equal operator. More...
 
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. More...
 
std::vector< idx_typeneigh (idx_type i) const
 Returns a list of neighbors of node i. More...
 
std::vector< idx_typereverse_neigh (idx_type i) const
 Returns a list of reverse neighbors of node i. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serialize to a stream. More...
 
void load (std::istream &in)
 Load from istream. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal. More...
 
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. More...
 

Protected Member Functions

void build_from_matrix (const std::vector< std::vector< int > > &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. More...
 
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. More...
 
void build_from_edges (std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
 Build a tree from an edges collection. More...
 

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 37 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 40 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 41 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 256 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 280 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 301 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 ( const k2_tree< k, t_bv, t_rank > &  tr)
inline

Definition at line 326 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 336 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 106 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 132 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 388 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 156 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 ( const std::vector< std::vector< int > > &  matrix)
inlineprotected

Definition at line 56 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 500 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 488 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 379 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 377 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 476 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 424 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 339 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 354 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== ( const k2_tree< k, t_bv, t_rank > &  tr) const
inline

Equal operator.

Definition at line 365 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 439 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 458 of file k2_tree.hpp.


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