SDSL 3.0.3
Succinct Data Structure Library
|
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_tree & | operator= (k2_tree &&tr) |
Move assignment operator. | |
k2_tree & | operator= (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_type > | neigh (idx_type i) const |
Returns a list of neighbors of node i. | |
std::vector< idx_type > | reverse_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. | |
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.
Definition at line 49 of file k2_tree.hpp.
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.
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.
|
default |
|
inline |
Constructor.
This constructos takes the graph adjacency matrix. The time complexity for this constructor is linear in the matrix size
matrix | Adjacency matrix of the graph. It must be a binary square matrix. |
Definition at line 274 of file k2_tree.hpp.
|
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.
edges | A vector with all the edges of the graph, it can not be empty. |
size | Size 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.
|
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.
filename | String with the prefix of the files filename.x, filename.y each of them containing a serialized int_vector<>. |
size | Size 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.
|
inline |
Definition at line 349 of file k2_tree.hpp.
|
inline |
Definition at line 354 of file k2_tree.hpp.
|
inlineprotected |
Recursive function to retrieve list of neighbors.
n | Size of the submatrix in the next recursive step. |
row | Row of interest in the current submatrix, this is the row corresponding the node we are looking neighbors for. |
col | Column offset of the current submatrix in the global matrix. |
level | Position in k_t:k_l (k_l appended to k_t) of the node or leaf being processed at this step. |
acc | Accumulator to store the neighbors found. |
Definition at line 120 of file k2_tree.hpp.
|
inlineprotected |
Recursive function to retrieve list of reverse neighbors.
n | Size of the submatrix in the next recursive step. |
row | Row offset of the current submatrix in the global matrix. |
col | Column of interest in the current submatrix, this is the column corresponding the node we are looking reverse neighbors for. |
level | Position in k_t:k_l (k_l appended to k_t) of the node or leaf being processed at this step. |
acc | Accumulator to store the neighbors found. |
Definition at line 148 of file k2_tree.hpp.
|
inline |
Indicates wheter node j is adjacent to node i or not.
i | Node i. |
j | Node j. |
Definition at line 419 of file k2_tree.hpp.
|
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.
edges | A vector with all the edges of the graph, it can not be empty. |
size | Size 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.
|
inlineprotected |
Definition at line 68 of file k2_tree.hpp.
|
inline |
Load via cereal.
Definition at line 537 of file k2_tree.hpp.
|
inline |
Serialise (save) via cereal.
Definition at line 525 of file k2_tree.hpp.
|
inline |
Definition at line 407 of file k2_tree.hpp.
|
inline |
Definition at line 402 of file k2_tree.hpp.
|
inline |
Load from istream.
Serialize the k2_tree from the given istream.
istream | Stream to load the k2_tree from. |
Definition at line 513 of file k2_tree.hpp.
|
inline |
Returns a list of neighbors of node i.
i | Node to get neighbors from. |
Definition at line 457 of file k2_tree.hpp.
|
inline |
Move assignment operator.
Definition at line 360 of file k2_tree.hpp.
|
inline |
Assignment operator.
Definition at line 375 of file k2_tree.hpp.
|
inline |
Equal operator.
Definition at line 386 of file k2_tree.hpp.
|
inline |
Returns a list of reverse neighbors of node i.
i | Node to get reverse neighbors from. |
Definition at line 474 of file k2_tree.hpp.
|
inline |
Serialize to a stream.
Serialize the k2_tree data structure
out | Outstream to write the k2_tree. |
v | |
string_name |
Definition at line 495 of file k2_tree.hpp.