An extensible data structure for massive streaming graphs
|
#include <dirent.h>
#include "stinger.h"
#include "stinger-atomics.h"
#include "stinger-utils.h"
#include "xmalloc.h"
#include "x86-full-empty.h"
Macros | |
#define | tdeg(X, Y) offsets[((X) * (maxVtx+2)) + (Y+2)] |
#define | tdeg(X, Y) offsets[((X) * (maxVtx+2)) + (Y+1)] |
Functions | |
int64_t | stinger_outdegree (const struct stinger *S_, int64_t i_) |
Returns the out-degree of a vertex. | |
int64_t | stinger_typed_outdegree (const struct stinger *S, int64_t i, int64_t type) |
Returns the out-degree of a vertex for a given edge type. | |
uint64_t | stinger_max_active_vertex (const struct stinger *S) |
Calculate the largest active vertex ID. | |
uint64_t | stinger_num_active_vertices (const struct stinger *S) |
Calculate the number of active vertices. | |
int64_t | stinger_indegree (const struct stinger *S_, int64_t i_) |
Returns the in-degree of a vertex. | |
int64_t | stinger_vweight (const struct stinger *S_, int64_t i_) |
Returns the vertex weight. | |
int64_t | stinger_set_vweight (struct stinger *S_, int64_t i_, int64_t weight_) |
Sets the vertex weight. | |
int64_t | stinger_vtype (const struct stinger *S_, int64_t i_) |
Returns the vertex type. | |
int64_t | stinger_set_vtype (const struct stinger *S_, int64_t i_, int64_t type_) |
Sets the vertex type. | |
struct stinger_eb * | stinger_edgeblocks (const struct stinger *S_, int64_t i_) |
struct stinger_eb * | stinger_next_eb (const struct stinger *G, const struct stinger_eb *eb_) |
int64_t | stinger_eb_type (const struct stinger_eb *eb_) |
int | stinger_eb_high (const struct stinger_eb *eb_) |
int | stinger_eb_is_blank (const struct stinger_eb *eb_, int k_) |
int64_t | stinger_eb_adjvtx (const struct stinger_eb *eb_, int k_) |
int64_t | stinger_eb_weight (const struct stinger_eb *eb_, int k_) |
int64_t | stinger_eb_ts (const struct stinger_eb *eb_, int k_) |
int64_t | stinger_eb_first_ts (const struct stinger_eb *eb_, int k_) |
int64_t | stinger_total_edges (const struct stinger *S) |
Count the total number of edges in STINGER. | |
size_t | stinger_graph_size (const struct stinger *S) |
Calculate the total size of the active STINGER graph in memory. | |
void | stinger_print_eb (struct stinger_eb *eb) |
uint32_t | stinger_consistency_check (struct stinger *S, uint64_t NV) |
Checks the STINGER metadata for inconsistencies. | |
void | stinger_fragmentation (struct stinger *S, uint64_t NV, struct stinger_fragmentation_t *stats) |
Calculate statistics on edge block fragmentation in the graph. | |
void | stinger_init (void) |
struct stinger * | stinger_new (void) |
Create a new STINGER data structure. | |
struct stinger * | stinger_free (struct stinger *S) |
Free memory allocated to a particular STINGER instance. | |
struct stinger * | stinger_free_all (struct stinger *S) |
Free the STINGER data structure and all edge blocks. | |
void | new_ebs (eb_index_t *out, size_t neb, int64_t etype, int64_t from) |
void | push_ebs (struct stinger *G, size_t neb, eb_index_t *restrict eb) |
struct curs | etype_begin (struct stinger_vb *v, int etype) |
void | update_edge_data (struct stinger *S, struct stinger_eb *eb, uint64_t index, int64_t neighbor, int64_t weight, int64_t ts) |
int | stinger_incr_edge (struct stinger *G, int64_t type, int64_t from, int64_t to, int64_t weight, int64_t timestamp) |
Increments a directed edge. | |
int | stinger_insert_edge_pair (struct stinger *G, int64_t type, int64_t from, int64_t to, int64_t weight, int64_t timestamp) |
Insert an undirected edge. | |
int | stinger_incr_edge_pair (struct stinger *G, int64_t type, int64_t from, int64_t to, int64_t weight, int64_t timestamp) |
Increments an undirected edge. | |
int | stinger_remove_edge_pair (struct stinger *G, int64_t type, int64_t from, int64_t to) |
Removes an undirected edge. | |
void | stinger_set_initial_edges (struct stinger *G, const size_t nv, const int64_t etype, const int64_t *off_in, const int64_t *phys_adj_in, const int64_t *weight_in, const int64_t *ts_in, const int64_t *first_ts_in, const int64_t single_ts) |
Initializes an empty STINGER with a graph in CSR format. | |
void | stinger_gather_typed_predecessors (const struct stinger *G, int64_t type, int64_t v, size_t *outlen, int64_t *out, size_t max_outlen) |
Copy typed incoming adjacencies of a vertex into a buffer. | |
void | stinger_gather_successors (const struct stinger *G, int64_t v, size_t *outlen, int64_t *out, int64_t *weight, int64_t *timefirst, int64_t *timerecent, int64_t *type, size_t max_outlen) |
Copy adjacencies of a vertex into a buffer with optional metadata. | |
void | stinger_gather_typed_successors (const struct stinger *G, int64_t type, int64_t v, size_t *outlen, int64_t *out, size_t max_outlen) |
Copy typed adjacencies of a vertex into a buffer. | |
int | stinger_has_typed_successor (const struct stinger *G, int64_t type, int64_t from, int64_t to) |
Determines if a vertex has an edge of a given type. | |
int64_t | stinger_edgeweight (const struct stinger *G, int64_t from, int64_t to, int64_t type) |
Get the weight of a given edge. | |
int | stinger_set_edgeweight (struct stinger *G, int64_t from, int64_t to, int64_t type, int64_t weight) |
Set the weight of a given edge. | |
int64_t | stinger_edge_timestamp_first (const struct stinger *G, int64_t from, int64_t to, int64_t type) |
Get the first timestamp of a given edge. | |
int64_t | stinger_edge_timestamp_recent (const struct stinger *G, int64_t from, int64_t to, int64_t type) |
Get the recent timestamp of a given edge. | |
int | stinger_edge_touch (struct stinger *G, int64_t from, int64_t to, int64_t type, int64_t timestamp) |
Update the recent timestamp of an edge. | |
int64_t | stinger_sort_actions (int64_t nactions, int64_t *actions, int64_t *insoff, int64_t *deloff, int64_t *act) |
Sorts a batch of edge insertions and deletions. | |
void | stinger_remove_all_edges_of_type (struct stinger *G, int64_t type) |
Removes all the edges in the graph of a given type. | |
int | stinger_save_to_file (struct stinger *S, uint64_t maxVtx, const char *stingerfile) |
Checkpoint a STINGER data structure to disk. Format (64-bit words): | |
int | stinger_open_from_file (const char *stingerfile, struct stinger **S, uint64_t *maxVtx) |
Restores a STINGER checkpoint from disk. |
Variables | |
uint64_t | ebpool_tail = 0 |
struct stinger_eb * | ebpool = NULL |
const int64_t | endian_check = 0x1234ABCD |
#define tdeg | ( | X, | |
Y | |||
) | offsets[((X) * (maxVtx+2)) + (Y+2)] |
Referenced by stinger_save_to_file().
#define tdeg | ( | X, | |
Y | |||
) | offsets[((X) * (maxVtx+2)) + (Y+1)] |
|
read |
References curs::eb, stinger_eb::etype, curs::loc, stinger_eb::next, and readff().
Referenced by stinger_incr_edge().
void new_ebs | ( | eb_index_t * | out, |
size_t | neb, | ||
int64_t | etype, | ||
int64_t | from | ||
) |
References stinger_eb::etype, stinger_eb::largeStamp, MTASTREAMS, stinger_eb::smallStamp, stinger_eb::vertexID, and xzero().
void push_ebs | ( | struct stinger * | G, |
size_t | neb, | ||
eb_index_t *restrict | eb | ||
) |
References stinger_eb::etype, and STINGER_NUMETYPES.
Referenced by stinger_incr_edge(), and stinger_set_initial_edges().
uint32_t stinger_consistency_check | ( | struct stinger * | S, |
uint64_t | NV | ||
) |
Checks the STINGER metadata for inconsistencies.
S | The STINGER data structure |
NV | The total number of vertices |
References stinger_eb::high, stinger_vb::inDegree, stinger_eb::largeStamp, stinger::LVA, stinger_eb::next, stinger_eb::numEdges, stinger_vb::outDegree, stinger_eb::smallStamp, stinger_eb_adjvtx(), stinger_eb_first_ts(), stinger_eb_is_blank(), stinger_eb_ts(), stinger_eb_weight(), stinger_edgeblocks(), STINGER_EDGEBLOCKSIZE, stinger_to_sorted_csr(), and stinger_eb::vertexID.
int64_t stinger_eb_adjvtx | ( | const struct stinger_eb * | eb_, |
int | k_ | ||
) |
References stinger_eb::edges, and stinger_edge::neighbor.
Referenced by stinger_consistency_check(), and stinger_save_to_file().
int64_t stinger_eb_first_ts | ( | const struct stinger_eb * | eb_, |
int | k_ | ||
) |
References stinger_eb::edges, and stinger_edge::timeFirst.
Referenced by stinger_consistency_check(), and stinger_save_to_file().
int stinger_eb_high | ( | const struct stinger_eb * | eb_ | ) |
References stinger_eb::high.
Referenced by stinger_save_to_file().
int stinger_eb_is_blank | ( | const struct stinger_eb * | eb_, |
int | k_ | ||
) |
References stinger_eb::edges, and stinger_edge::neighbor.
Referenced by stinger_consistency_check(), stinger_fragmentation(), stinger_iterator_next(), stinger_save_to_file(), and stinger_sort_edge_list().
int64_t stinger_eb_ts | ( | const struct stinger_eb * | eb_, |
int | k_ | ||
) |
References stinger_eb::edges, and stinger_edge::timeRecent.
Referenced by stinger_consistency_check(), and stinger_save_to_file().
|
inline |
References stinger_eb::etype.
int64_t stinger_eb_weight | ( | const struct stinger_eb * | eb_, |
int | k_ | ||
) |
References stinger_eb::edges, and stinger_edge::weight.
Referenced by stinger_consistency_check(), and stinger_save_to_file().
int64_t stinger_edge_timestamp_first | ( | const struct stinger * | G, |
int64_t | from, | ||
int64_t | to, | ||
int64_t | type | ||
) |
Get the first timestamp of a given edge.
Finds a specified edge of a given type by source and destination vertex ID and returns the first timestamp. Remember, edges may have different timestamps in different directions.
G | The STINGER data structure |
from | Source vertex ID |
to | Destination vertex ID |
type | Edge type |
References STINGER_EDGE_DEST, STINGER_EDGE_TIME_FIRST, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END, and STINGERASSERTS.
int64_t stinger_edge_timestamp_recent | ( | const struct stinger * | G, |
int64_t | from, | ||
int64_t | to, | ||
int64_t | type | ||
) |
Get the recent timestamp of a given edge.
Finds a specified edge of a given type by source and destination vertex ID and returns the recent timestamp. Remember, edges may have different timestamps in different directions.
G | The STINGER data structure |
from | Source vertex ID |
to | Destination vertex ID |
type | Edge type |
References STINGER_EDGE_DEST, STINGER_EDGE_TIME_RECENT, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END, and STINGERASSERTS.
int stinger_edge_touch | ( | struct stinger * | G, |
int64_t | from, | ||
int64_t | to, | ||
int64_t | type, | ||
int64_t | timestamp | ||
) |
Update the recent timestamp of an edge.
Finds a specified edge of a given type by source and destination vertex ID and updates the recent timestamp to the specified value.
G | The STINGER data structure |
from | Source vertex ID |
to | Destination vertex ID |
type | Edge type |
timestamp | Timestamp to set recent |
References STINGER_EDGE_DEST, STINGER_EDGE_TIME_RECENT, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END, and STINGERASSERTS.
|
read |
References stinger_vb::edges, and stinger::LVA.
Referenced by stinger_consistency_check(), and stinger_fragmentation().
int64_t stinger_edgeweight | ( | const struct stinger * | G, |
int64_t | from, | ||
int64_t | to, | ||
int64_t | type | ||
) |
Get the weight of a given edge.
Finds a specified edge of a given type by source and destination vertex ID and returns the current edge weight. Remember, edges may have different weights in different directions.
G | The STINGER data structure |
from | Source vertex ID |
to | Destination vertex ID |
type | Edge type |
References STINGER_EDGE_DEST, STINGER_EDGE_WEIGHT, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END, and STINGERASSERTS.
void stinger_fragmentation | ( | struct stinger * | S, |
uint64_t | NV, | ||
struct stinger_fragmentation_t * | stats | ||
) |
Calculate statistics on edge block fragmentation in the graph.
S | The STINGER data structure |
NV | The total number of vertices |
References stinger_fragmentation_t::edge_blocks_in_use, stinger::ETA, stinger_fragmentation_t::fill_percent, stinger_eb::high, stinger_etype_array::high, stinger_eb::next, stinger_fragmentation_t::num_edges, stinger_fragmentation_t::num_empty_edges, stinger_fragmentation_t::num_fragmented_blocks, stinger_eb::numEdges, stinger_eb_is_blank(), stinger_edgeblocks(), and STINGER_EDGEBLOCKSIZE.
Free memory allocated to a particular STINGER instance.
Frees the ETA pointers for each edge type, the LVA, and the struct stinger itself. Does not actually free any edge blocks, as there may be other active STINGER instances.
S | The STINGER data structure |
References stinger::ETA, and stinger::LVA.
Referenced by stinger_free_all().
Free the STINGER data structure and all edge blocks.
Free memory allocated to the specified STINGER data structure. Also frees the STINGER edge block pool, effectively ending all STINGER operations globally. Only call this function if you are done using STINGER entirely.
S | The STINGER data structure |
References stinger_free().
void stinger_gather_successors | ( | const struct stinger * | G, |
int64_t | v, | ||
size_t * | outlen, | ||
int64_t * | out, | ||
int64_t * | weight, | ||
int64_t * | timefirst, | ||
int64_t * | timerecent, | ||
int64_t * | type, | ||
size_t | max_outlen | ||
) |
Copy adjacencies of a vertex into a buffer with optional metadata.
Adjacencies of the specified vertex are copied into the user-provided buffer(s) up to the length of the buffer(s) specified by max_outlen. All buffers should be at least max_outlen or NULL.
G | The STINGER data structure |
v | Source vertex ID |
outlen | Number of adjacencies copied |
out | Buffer to hold adjacencies |
weight | OPTIONAL Buffer to hold edge weights |
timefirst | OPTIONAL Buffer to hold first timestamps |
timerecent | OPTIONAL Buffer to hold recent timestamps |
type | OPTIONAL Buffer to hold edge types |
max_outlen | Length of out[] and any optional buffers provided |
References STINGER_EDGE_DEST, STINGER_EDGE_TIME_FIRST, STINGER_EDGE_TIME_RECENT, STINGER_EDGE_TYPE, STINGER_EDGE_WEIGHT, STINGER_PARALLEL_FORALL_EDGES_OF_VTX_BEGIN, and STINGER_PARALLEL_FORALL_EDGES_OF_VTX_END.
Referenced by stinger_to_unsorted_csr().
void stinger_gather_typed_predecessors | ( | const struct stinger * | G, |
int64_t | type, | ||
int64_t | v, | ||
size_t * | outlen, | ||
int64_t * | out, | ||
size_t | max_outlen | ||
) |
Copy typed incoming adjacencies of a vertex into a buffer.
For a given edge type, adjacencies of the specified vertex are copied into the user-provided buffer up to the length of the buffer. These are the incoming edges for which a vertex is a destination. Note that this operation may be very expensive on most platforms.
G | The STINGER data structure |
type | Edge type |
v | Source vertex ID |
outlen | Number of adjacencies copied |
out | Buffer to hold adjacencies |
max_outlen | Length of out[] and recent[] |
References STINGER_EDGE_DEST, STINGER_EDGE_SOURCE, STINGER_PARALLEL_FORALL_EDGES_BEGIN, and STINGER_PARALLEL_FORALL_EDGES_END.
void stinger_gather_typed_successors | ( | const struct stinger * | G, |
int64_t | type, | ||
int64_t | v, | ||
size_t * | outlen, | ||
int64_t * | out, | ||
size_t | max_outlen | ||
) |
Copy typed adjacencies of a vertex into a buffer.
For a given edge type, adjacencies of the specified vertex are copied into the user-provided buffer up to the length of the buffer.
G | The STINGER data structure |
type | Edge type |
v | Source vertex ID |
outlen | Number of adjacencies copied |
out | Buffer to hold adjacencies |
max_outlen | Length of out[] and recent[] |
References STINGER_EDGE_DEST, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, and STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END.
size_t stinger_graph_size | ( | const struct stinger * | S | ) |
Calculate the total size of the active STINGER graph in memory.
S | The STINGER data structure |
References stinger::ETA, stinger_etype_array::high, and stinger::LVASize.
int stinger_has_typed_successor | ( | const struct stinger * | G, |
int64_t | type, | ||
int64_t | from, | ||
int64_t | to | ||
) |
Determines if a vertex has an edge of a given type.
Searches the adjacencies of a specified vertex for an edge of the given type.
G | The STINGER data structure |
type | Edge type |
from | Source vertex ID |
to | Destination vertex ID |
References STINGER_EDGE_DEST, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END, and STINGERASSERTS.
int stinger_incr_edge | ( | struct stinger * | G, |
int64_t | type, | ||
int64_t | from, | ||
int64_t | to, | ||
int64_t | weight, | ||
int64_t | timestamp | ||
) |
Increments a directed edge.
Increments the weight of a typed, directed edge. Recent timestamp is updated.
G | The STINGER data structure |
type | Edge type |
from | Source vertex ID |
to | Destination vertex ID |
weight | Edge weight |
timestamp | Edge timestamp |
References curs::eb, ebpool, stinger_eb::edges, stinger_eb::etype, etype_begin(), stinger_eb::high, curs::loc, stinger_edge::neighbor, stinger_eb::next, push_ebs(), readfe(), readff(), STINGER_EDGEBLOCKSIZE, STINGERASSERTS, stinger_edge::timeFirst, update_edge_data(), stinger_edge::weight, writeef(), and writexf().
Referenced by stinger_incr_edge_pair().
int stinger_incr_edge_pair | ( | struct stinger * | G, |
int64_t | type, | ||
int64_t | from, | ||
int64_t | to, | ||
int64_t | weight, | ||
int64_t | timestamp | ||
) |
Increments an undirected edge.
Increments the weight of a typed, undirected edge. Recent timestamp is updated.
G | The STINGER data structure |
type | Edge type |
from | Source vertex ID |
to | Destination vertex ID |
weight | Edge weight |
timestamp | Edge timestamp |
References stinger_incr_edge(), and STINGERASSERTS.
int64_t stinger_indegree | ( | const struct stinger * | S_, |
int64_t | i_ | ||
) |
Returns the in-degree of a vertex.
S_ | The STINGER data structure |
i_ | Logical vertex ID |
References stinger_vb::inDegree, and stinger::LVA.
Referenced by stinger_max_active_vertex(), and stinger_num_active_vertices().
void stinger_init | ( | void | ) |
Referenced by stinger_new().
int stinger_insert_edge_pair | ( | struct stinger * | G, |
int64_t | type, | ||
int64_t | from, | ||
int64_t | to, | ||
int64_t | weight, | ||
int64_t | timestamp | ||
) |
Insert an undirected edge.
Inserts a typed, undirected edge. First timestamp is set, if the edge is new. Recent timestamp is updated. Weight is set to specified value regardless.
G | The STINGER data structure |
type | Edge type |
from | Source vertex ID |
to | Destination vertex ID |
weight | Edge weight |
timestamp | Edge timestamp |
References stinger_insert_edge(), and STINGERASSERTS.
uint64_t stinger_max_active_vertex | ( | const struct stinger * | S | ) |
Calculate the largest active vertex ID.
Finds the largest vertex ID whose in-degree and/or out-degree is greater than zero.
NOTE: If you are using this to obtain a value of "nv" for additional STINGER calls, you must add one to the result.
S | The STINGER data structure |
References stinger_indegree(), STINGER_MAX_LVERTICES, and stinger_outdegree().
|
read |
Create a new STINGER data structure.
Allocates memory for a STINGER data structure. If this is the first STINGER to be allocated, it also initializes the edge block pool. Edge blocks are allocated and assigned for each value less than STINGER_NUMETYPES.
References EBPOOL_SIZE, stinger::ETA, stinger_etype_array::high, stinger_etype_array::length, stinger::LVA, stinger::LVASize, MTASTREAMS, readff(), stinger_init(), STINGER_MAX_LVERTICES, STINGER_NUMETYPES, xcalloc(), and xmalloc().
Referenced by edge_list_to_stinger(), and stinger_open_from_file().
|
read |
References stinger_eb::next, and readff().
uint64_t stinger_num_active_vertices | ( | const struct stinger * | S | ) |
Calculate the number of active vertices.
Counts the number of vertices whose in-degree is greater than zero and out-degree is greater than zero.
S | The STINGER data structure |
References stinger_indegree(), STINGER_MAX_LVERTICES, and stinger_outdegree().
int stinger_open_from_file | ( | const char * | stingerfile, |
struct stinger ** | S, | ||
uint64_t * | maxVtx | ||
) |
Restores a STINGER checkpoint from disk.
stingerfile | The path and name of the input file. |
S | A double pointer to outpute the new Stinger. |
maxVtx | Output pointer for the the maximum vertex ID + 1. |
References bs64(), bs64_n(), STINGER_MAX_LVERTICES, stinger_new(), STINGER_NUMETYPES, stinger_set_initial_edges(), stinger_set_vtype(), stinger_set_vweight(), xcalloc(), and xmalloc().
int64_t stinger_outdegree | ( | const struct stinger * | S_, |
int64_t | i_ | ||
) |
Returns the out-degree of a vertex.
S_ | The STINGER data structure |
i_ | Logical vertex ID |
Referenced by stinger_max_active_vertex(), stinger_num_active_vertices(), stinger_to_unsorted_csr(), and stinger_total_edges().
void stinger_print_eb | ( | struct stinger_eb * | eb | ) |
References stinger_eb::edges, stinger_eb::etype, stinger_eb::high, stinger_eb::largeStamp, stinger_edge::neighbor, stinger_eb::next, stinger_eb::numEdges, stinger_eb::smallStamp, STINGER_EDGEBLOCKSIZE, stinger_edge::timeFirst, stinger_edge::timeRecent, stinger_eb::vertexID, and stinger_edge::weight.
void stinger_remove_all_edges_of_type | ( | struct stinger * | G, |
int64_t | type | ||
) |
Removes all the edges in the graph of a given type.
Traverses all edge blocks of a particular type in parallel and erases all edges of the specified type. Blocks are available immediately for reuse.
G | The STINGER data structure |
type | The edge type of edges to delete |
References stinger_etype_array::blocks, stinger_eb::edges, stinger::ETA, stinger_eb::high, stinger_etype_array::high, stinger_vb::inDegree, stinger_eb::largeStamp, stinger::LVA, stinger_edge::neighbor, stinger_eb::numEdges, stinger_vb::outDegree, stinger_eb::smallStamp, and stinger_eb::vertexID.
int stinger_remove_edge_pair | ( | struct stinger * | G, |
int64_t | type, | ||
int64_t | from, | ||
int64_t | to | ||
) |
Removes an undirected edge.
Remove a typed, undirected edge. Note: Do not call this function concurrently with the same source vertex, even for different edge types.
G | The STINGER data structure |
type | Edge type |
from | Source vertex ID |
to | Destination vertex ID |
References stinger_remove_edge(), and STINGERASSERTS.
int stinger_save_to_file | ( | struct stinger * | S, |
uint64_t | maxVtx, | ||
const char * | stingerfile | ||
) |
Checkpoint a STINGER data structure to disk. Format (64-bit words):
S | A pointer to the Stinger to be saved. |
maxVtx | The maximum vertex ID + 1. |
stingerfile | The path and name of the output file. |
References stinger_etype_array::blocks, ebpool, endian_check, stinger::ETA, stinger_etype_array::high, stinger_eb::numEdges, prefix_sum(), stinger_eb_adjvtx(), stinger_eb_first_ts(), stinger_eb_high(), stinger_eb_is_blank(), stinger_eb_ts(), stinger_eb_weight(), STINGER_NUMETYPES, stinger_vtype(), stinger_vweight(), tdeg, stinger_eb::vertexID, xcalloc(), and xmalloc().
int stinger_set_edgeweight | ( | struct stinger * | G, |
int64_t | from, | ||
int64_t | to, | ||
int64_t | type, | ||
int64_t | weight | ||
) |
Set the weight of a given edge.
Finds a specified edge of a given type by source and destination vertex ID and sets the current edge weight. Remember, edges may have different weights in different directions.
G | The STINGER data structure |
from | Source vertex ID |
to | Destination vertex ID |
type | Edge type |
weight | Edge weight to set |
References STINGER_EDGE_DEST, STINGER_EDGE_WEIGHT, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN, STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END, and STINGERASSERTS.
void stinger_set_initial_edges | ( | struct stinger * | G, |
const size_t | nv, | ||
const int64_t | etype, | ||
const int64_t * | off_in, | ||
const int64_t * | phys_adj_in, | ||
const int64_t * | weight_in, | ||
const int64_t * | ts_in, | ||
const int64_t * | first_ts_in, | ||
const int64_t | single_ts | ||
) |
Initializes an empty STINGER with a graph in CSR format.
Takes an edge list in CSR format, with weight and timestamps, and initializes an empty STINGER based on the input graph. All edges being ingested must be of a single edge type.
G | STINGER data structure |
nv | Number of vertices |
etype | Edge type |
off_in | Array of length nv containing the adjacency offset for each vertex |
phys_adj_in | Array containing the destination vertex of each edge |
weight_in | Array containing integer weight of each edge |
ts_in | Array containing recent timestamp of edge edge (or NULL) |
first_ts_in | Array containing the first timestamp of each edge (or NULL) |
single_ts | Value for timestamps if either of the above is NULL |
References stinger_eb::edges, MTASTREAMS, stinger_eb::next, stinger_vb::outDegree, push_ebs(), STINGER_EDGEBLOCKSIZE, and xcalloc().
Referenced by edge_list_to_stinger(), and stinger_open_from_file().
int64_t stinger_set_vtype | ( | const struct stinger * | S_, |
int64_t | i_, | ||
int64_t | type_ | ||
) |
Sets the vertex type.
S_ | The STINGER data structure |
i_ | Logical vertex ID |
type_ | Vertex type |
References stinger::LVA, and stinger_vb::vtype.
Referenced by stinger_open_from_file().
int64_t stinger_set_vweight | ( | struct stinger * | S_, |
int64_t | i_, | ||
int64_t | weight_ | ||
) |
Sets the vertex weight.
S_ | The STINGER data structure |
i_ | Logical vertex ID |
weight_ | Vertex weight |
References stinger::LVA, and stinger_vb::weight.
Referenced by stinger_open_from_file().
int64_t stinger_sort_actions | ( | int64_t | nactions, |
int64_t * | actions, | ||
int64_t * | insoff, | ||
int64_t * | deloff, | ||
int64_t * | act | ||
) |
Sorts a batch of edge insertions and deletions.
Takes an array of edge insertions and deletions and sorts them. The array is packed with <source, destination> pairs, such that actions[2*i] = source vertex ID and actions[2*i+1] = destination vertex ID. Bit-wise complement the source and destination vertex IDs to indicate a deletion. This function will create an undirected actions list (i.e. create the reverse edge action).
The output is similarly packed, sorted by source vertex ID first, then by destination vertex ID such that deletions are contiguous before insertions. For vertex i, deletions incident on i start at deloff[i] and end at insoff[i]. Insertions incident on i start at insoff[i] and end at deloff[i+1].
nactions | Number of edge actions |
actions | The packed array of edge insertions and deletions |
insoff | For each incident vertex in the batch, the offset into act[] of the first edge insertion |
deloff | For each incident vertex in the batch, the offset into act[] of the first edge deletion |
act | Sorted array of edge insertions and deletions |
References bucket_sort_pairs(), i2cmp(), prefix_sum(), and xmalloc().
int64_t stinger_total_edges | ( | const struct stinger * | S | ) |
Count the total number of edges in STINGER.
S | The STINGER data structure |
References STINGER_MAX_LVERTICES, and stinger_outdegree().
int64_t stinger_typed_outdegree | ( | const struct stinger * | S, |
int64_t | i, | ||
int64_t | type | ||
) |
Returns the out-degree of a vertex for a given edge type.
S | The STINGER data structure |
i | Logical vertex ID |
type | Edge type |
References stinger_eb::edges, stinger_eb::etype, stinger_eb::next, and stinger_eb::numEdges.
int64_t stinger_vtype | ( | const struct stinger * | S_, |
int64_t | i_ | ||
) |
Returns the vertex type.
S_ | The STINGER data structure |
i_ | Logical vertex ID |
References stinger::LVA, and stinger_vb::vtype.
Referenced by stinger_iterator_check_vtype(), and stinger_save_to_file().
int64_t stinger_vweight | ( | const struct stinger * | S_, |
int64_t | i_ | ||
) |
Returns the vertex weight.
S_ | The STINGER data structure |
i_ | Logical vertex ID |
References stinger::LVA, and stinger_vb::weight.
Referenced by stinger_save_to_file().
void update_edge_data | ( | struct stinger * | S, |
struct stinger_eb * | eb, | ||
uint64_t | index, | ||
int64_t | neighbor, | ||
int64_t | weight, | ||
int64_t | ts | ||
) |
References stinger_edge::neighbor, readfe(), readff(), stinger_edge::timeFirst, stinger_edge::timeRecent, stinger_edge::weight, writeef(), and writexf().
Referenced by stinger_incr_edge().
struct stinger_eb* ebpool = NULL |
uint64_t ebpool_tail = 0 |
const int64_t endian_check = 0x1234ABCD |
Referenced by main(), snarf_actions(), snarf_graph(), and stinger_save_to_file().
comments powered by Disqus