An extensible data structure for massive streaming graphs
 All Data Structures Files Functions Variables Typedefs Macros Groups Pages
stinger.h File Reference
#include "stinger-defs.h"
#include "stinger-traversal.h"

Macros

#define STINGER_FORALL_EDGES_OF_VTX_BEGIN(STINGER_, VTX_)   do {
#define STINGER_FORALL_EDGES_OF_VTX_END()   } while (0)
#define STINGER_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN(STINGER_, TYPE_, VTX_)   do {
#define STINGER_FORALL_EDGES_OF_TYPE_OF_VTX_END()   while (0)
#define STINGER_PARALLEL_FORALL_EDGES_OF_VTX_BEGIN(STINGER_, VTX_)   do {
#define STINGER_PARALLEL_FORALL_EDGES_OF_VTX_END()   while (0)
#define STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN(STINGER_, TYPE_, VTX_)   do {
#define STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END()   while (0)
#define STINGER_FORALL_EDGES_BEGIN(STINGER_, TYPE_)   do {
#define STINGER_FORALL_EDGES_END()   while (0)
#define STINGER_PARALLEL_FORALL_EDGES_BEGIN(STINGER_, TYPE_)   do {
#define STINGER_PARALLEL_FORALL_EDGES_END()   while (0)
#define STINGER_READ_ONLY_FORALL_EDGES_OF_VTX_BEGIN(STINGER_, VTX_)   do {
#define STINGER_READ_ONLY_FORALL_EDGES_OF_VTX_END()   } while (0)
#define STINGER_READ_ONLY_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN(STINGER_, TYPE_, VTX_)   do {
#define STINGER_READ_ONLY_FORALL_EDGES_OF_TYPE_OF_VTX_END()   while (0)
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_OF_VTX_BEGIN(STINGER_, VTX_)   do {
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_OF_VTX_END()   while (0)
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN(STINGER_, TYPE_, VTX_)   do {
#define STINGER_READ_ONLY_PARALLEL__FORALL_EDGES_OF_TYPE_OF_VTX_END()   while (0)
#define STINGER_READ_ONLY_FORALL_EDGES_BEGIN(STINGER_, TYPE_)   do {
#define STINGER_READ_ONLY_FORALL_EDGES_END()   while (0)
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_BEGIN(STINGER_, TYPE_)   do {
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_END()   while (0)
#define STINGER_EDGE_SOURCE   /* always read-only */
#define STINGER_EDGE_TYPE   /* always read-only */
#define STINGER_EDGE_DEST   /* do not set < 0 */
#define STINGER_EDGE_WEIGHT
#define STINGER_EDGE_TIME_FIRST
#define STINGER_EDGE_TIME_RECENT
#define STINGER_TRAVERSE_EDGES(STINGER_, FILTER_, CODE_)
#define OF_VERTICES(ARRAY_, COUNT_)
#define OF_VERTEX_TYPE(ARRAY_, COUNT_)
#define OF_EDGE_TYPE(ARRAY_, COUNT_)
#define MODIFIED_BEFORE(TIME_)
#define MODIFIED_AFTER(TIME_)
#define CREATED_BEFORE(TIME_)
#define CREATED_AFTER(TIME_)

Functions

struct stingerstinger_new (void)
 Create a new STINGER data structure.
void stinger_set_initial_edges (struct stinger *, const size_t, const int64_t, const int64_t *, const int64_t *, const int64_t *, const int64_t *, const int64_t *, const int64_t)
 Initializes an empty STINGER with a graph in CSR format.
struct stingerstinger_free (struct stinger *)
 Free memory allocated to a particular STINGER instance.
struct stingerstinger_free_all (struct stinger *)
 Free the STINGER data structure and all edge blocks.
int stinger_save_to_file (struct stinger *, uint64_t, const char *)
 Checkpoint a STINGER data structure to disk. Format (64-bit words):
int stinger_open_from_file (const char *, struct stinger **, uint64_t *)
 Restores a STINGER checkpoint from disk.
int stinger_insert_edge (struct stinger *, int64_t, int64_t, int64_t, int64_t, int64_t)
int stinger_insert_edge_pair (struct stinger *, int64_t, int64_t, int64_t, int64_t, int64_t)
 Insert an undirected edge.
int stinger_incr_edge (struct stinger *, int64_t, int64_t, int64_t, int64_t, int64_t)
 Increments a directed edge.
int stinger_incr_edge_pair (struct stinger *, int64_t, int64_t, int64_t, int64_t, int64_t)
 Increments an undirected edge.
int stinger_remove_edge (struct stinger *, int64_t, int64_t, int64_t)
int stinger_remove_edge_pair (struct stinger *, int64_t, int64_t, int64_t)
 Removes an undirected edge.
void stinger_remove_all_edges_of_type (struct stinger *G, int64_t type)
 Removes all the edges in the graph of a given type.
int64_t stinger_edgeweight (const struct stinger *, int64_t, int64_t, int64_t)
 Get the weight of a given edge.
int stinger_set_edgeweight (struct stinger *, int64_t, int64_t, int64_t, int64_t)
 Set the weight of a given edge.
int64_t stinger_edge_timestamp_first (const struct stinger *, int64_t, int64_t, int64_t)
 Get the first timestamp of a given edge.
int64_t stinger_edge_timestamp_recent (const struct stinger *, int64_t, int64_t, int64_t)
 Get the recent timestamp of a given edge.
int stinger_edge_touch (struct stinger *, int64_t, int64_t, int64_t, int64_t)
 Update the recent timestamp of an edge.
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.
XMTI int64_t stinger_outdegree (const struct stinger *, int64_t)
 Returns the out-degree of a vertex.
int64_t stinger_typed_outdegree (const struct stinger *, int64_t, int64_t)
 Returns the out-degree of a vertex for a given edge type.
XMTI int64_t stinger_indegree (const struct stinger *, int64_t)
 Returns the in-degree of a vertex.
XMTI int64_t stinger_vweight (const struct stinger *, int64_t)
 Returns the vertex weight.
XMTI int64_t stinger_vtype (const struct stinger *, int64_t)
 Returns the vertex type.
int64_t stinger_set_vweight (struct stinger *, int64_t, int64_t)
 Sets the vertex weight.
int64_t stinger_set_vtype (const struct stinger *, int64_t, int64_t)
 Sets the vertex type.
void stinger_gather_successors (const struct stinger *, int64_t, size_t *, int64_t *, int64_t *, int64_t *, int64_t *, int64_t *, size_t max_outlen)
 Copy adjacencies of a vertex into a buffer with optional metadata.
void stinger_gather_typed_successors (const struct stinger *, int64_t, int64_t, size_t *, int64_t *, size_t)
 Copy typed adjacencies of a vertex into a buffer.
int stinger_has_typed_successor (const struct stinger *, int64_t, int64_t, int64_t)
 Determines if a vertex has an edge of a given type.
void stinger_gather_typed_predecessors (const struct stinger *, int64_t, int64_t, size_t *, int64_t *, size_t)
 Copy typed incoming adjacencies of a vertex into a buffer.
int64_t stinger_sort_actions (int64_t nactions, int64_t *, int64_t *, int64_t *, int64_t *)
 Sorts a batch of edge insertions and deletions.
int64_t stinger_total_edges (const struct stinger *)
 Count the total number of edges in STINGER.
size_t stinger_graph_size (const struct stinger *)
 Calculate the total size of the active STINGER graph in memory.
uint32_t stinger_consistency_check (struct stinger *S, uint64_t NV)
 Checks the STINGER metadata for inconsistencies.

Macro Definition Documentation

#define CREATED_AFTER (   TIME_)
#define CREATED_BEFORE (   TIME_)
#define MODIFIED_AFTER (   TIME_)
#define MODIFIED_BEFORE (   TIME_)
#define OF_EDGE_TYPE (   ARRAY_,
  COUNT_ 
)
#define OF_VERTEX_TYPE (   ARRAY_,
  COUNT_ 
)
#define OF_VERTICES (   ARRAY_,
  COUNT_ 
)
#define STINGER_EDGE_DEST   /* do not set < 0 */
#define STINGER_EDGE_SOURCE   /* always read-only */
#define STINGER_EDGE_TIME_FIRST
#define STINGER_EDGE_TIME_RECENT
#define STINGER_EDGE_TYPE   /* always read-only */
#define STINGER_EDGE_WEIGHT
#define STINGER_FORALL_EDGES_BEGIN (   STINGER_,
  TYPE_ 
)    do {
#define STINGER_FORALL_EDGES_END ( )    while (0)
#define STINGER_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN (   STINGER_,
  TYPE_,
  VTX_ 
)    do {
#define STINGER_FORALL_EDGES_OF_TYPE_OF_VTX_END ( )    while (0)
#define STINGER_FORALL_EDGES_OF_VTX_BEGIN (   STINGER_,
  VTX_ 
)    do {
#define STINGER_FORALL_EDGES_OF_VTX_END ( )    } while (0)
#define STINGER_PARALLEL_FORALL_EDGES_BEGIN (   STINGER_,
  TYPE_ 
)    do {
#define STINGER_PARALLEL_FORALL_EDGES_END ( )    while (0)
#define STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN (   STINGER_,
  TYPE_,
  VTX_ 
)    do {
#define STINGER_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_END ( )    while (0)
#define STINGER_PARALLEL_FORALL_EDGES_OF_VTX_BEGIN (   STINGER_,
  VTX_ 
)    do {
#define STINGER_PARALLEL_FORALL_EDGES_OF_VTX_END ( )    while (0)
#define STINGER_READ_ONLY_FORALL_EDGES_BEGIN (   STINGER_,
  TYPE_ 
)    do {
#define STINGER_READ_ONLY_FORALL_EDGES_END ( )    while (0)
#define STINGER_READ_ONLY_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN (   STINGER_,
  TYPE_,
  VTX_ 
)    do {
#define STINGER_READ_ONLY_FORALL_EDGES_OF_TYPE_OF_VTX_END ( )    while (0)
#define STINGER_READ_ONLY_FORALL_EDGES_OF_VTX_BEGIN (   STINGER_,
  VTX_ 
)    do {
#define STINGER_READ_ONLY_FORALL_EDGES_OF_VTX_END ( )    } while (0)
#define STINGER_READ_ONLY_PARALLEL__FORALL_EDGES_OF_TYPE_OF_VTX_END ( )    while (0)
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_BEGIN (   STINGER_,
  TYPE_ 
)    do {
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_END ( )    while (0)
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_OF_TYPE_OF_VTX_BEGIN (   STINGER_,
  TYPE_,
  VTX_ 
)    do {
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_OF_VTX_BEGIN (   STINGER_,
  VTX_ 
)    do {
#define STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_OF_VTX_END ( )    while (0)
#define STINGER_TRAVERSE_EDGES (   STINGER_,
  FILTER_,
  CODE_ 
)

Function Documentation

uint32_t stinger_consistency_check ( struct stinger S,
uint64_t  NV 
)
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.

Parameters
GThe STINGER data structure
fromSource vertex ID
toDestination vertex ID
typeEdge type
Returns
First timestamp of edge; -1 if edge does not exist

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.

Parameters
GThe STINGER data structure
fromSource vertex ID
toDestination vertex ID
typeEdge type
Returns
Recent timestamp of edge; -1 if edge does not exist

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.

Parameters
GThe STINGER data structure
fromSource vertex ID
toDestination vertex ID
typeEdge type
timestampTimestamp to set recent
Returns
1 on success; 0 if failure

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.

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.

Parameters
GThe STINGER data structure
fromSource vertex ID
toDestination vertex ID
typeEdge type
Returns
Edge weight

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.

struct stinger* stinger_free ( struct stinger S)
read

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.

Parameters
SThe STINGER data structure
Returns
NULL on success

References stinger::ETA, and stinger::LVA.

Referenced by stinger_free_all().

struct stinger* stinger_free_all ( struct stinger S)
read

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.

Parameters
SThe STINGER data structure
Returns
NULL on success

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.

Parameters
GThe STINGER data structure
vSource vertex ID
outlenNumber of adjacencies copied
outBuffer to hold adjacencies
weightOPTIONAL Buffer to hold edge weights
timefirstOPTIONAL Buffer to hold first timestamps
timerecentOPTIONAL Buffer to hold recent timestamps
typeOPTIONAL Buffer to hold edge types
max_outlenLength of out[] and any optional buffers provided
Returns
Void

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.

Parameters
GThe STINGER data structure
typeEdge type
vSource vertex ID
outlenNumber of adjacencies copied
outBuffer to hold adjacencies
max_outlenLength of out[] and recent[]
Returns
Void

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.

Parameters
GThe STINGER data structure
typeEdge type
vSource vertex ID
outlenNumber of adjacencies copied
outBuffer to hold adjacencies
max_outlenLength of out[] and recent[]
Returns
Void

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.

Parameters
SThe STINGER data structure
Returns
The number of bytes currently in use by STINGER

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.

Parameters
GThe STINGER data structure
typeEdge type
fromSource vertex ID
toDestination vertex ID
Returns
1 if found; 0 otherwise

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.

Parameters
GThe STINGER data structure
typeEdge type
fromSource vertex ID
toDestination vertex ID
weightEdge weight
timestampEdge timestamp
Returns
1

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.

Parameters
GThe STINGER data structure
typeEdge type
fromSource vertex ID
toDestination vertex ID
weightEdge weight
timestampEdge timestamp
Returns
1

References stinger_incr_edge(), and STINGERASSERTS.

XMTI int64_t stinger_indegree ( const struct stinger S_,
int64_t  i_ 
)

Returns the in-degree of a vertex.

Parameters
S_The STINGER data structure
i_Logical vertex ID
Returns
In-degree of vertex i_

References stinger_vb::inDegree, and stinger::LVA.

Referenced by stinger_max_active_vertex(), and stinger_num_active_vertices().

int stinger_insert_edge ( struct stinger ,
int64_t  ,
int64_t  ,
int64_t  ,
int64_t  ,
int64_t   
)
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.

Parameters
GThe STINGER data structure
typeEdge type
fromSource vertex ID
toDestination vertex ID
weightEdge weight
timestampEdge timestamp
Returns
Number of edges inserted successfully

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.

Parameters
SThe STINGER data structure
Returns
Largest active vertex ID

References stinger_indegree(), STINGER_MAX_LVERTICES, and stinger_outdegree().

struct stinger* stinger_new ( void  )
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.

Returns
Pointer to struct stinger

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().

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.

Parameters
SThe STINGER data structure
Returns
Number of active vertices

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.

Parameters
stingerfileThe path and name of the input file.
SA double pointer to outpute the new Stinger.
maxVtxOutput pointer for the the maximum vertex ID + 1.
Returns
0 on success, -1 on failure.

References bs64(), bs64_n(), STINGER_MAX_LVERTICES, stinger_new(), STINGER_NUMETYPES, stinger_set_initial_edges(), stinger_set_vtype(), stinger_set_vweight(), xcalloc(), and xmalloc().

XMTI int64_t stinger_outdegree ( const struct stinger S_,
int64_t  i_ 
)

Returns the out-degree of a vertex.

Parameters
S_The STINGER data structure
i_Logical vertex ID
Returns
Out-degree of vertex i_

Referenced by stinger_max_active_vertex(), stinger_num_active_vertices(), stinger_to_unsorted_csr(), and stinger_total_edges().

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.

Parameters
GThe STINGER data structure
typeThe edge type of edges to delete
Returns
Void

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 ( struct stinger ,
int64_t  ,
int64_t  ,
int64_t   
)
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.

Parameters
GThe STINGER data structure
typeEdge type
fromSource vertex ID
toDestination vertex ID
Returns
1 on success, 0 if the edge is not found.

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):

  • endianness check
  • max NV (max vertex ID + 1)
  • number of edge types
  • type offsets (length = etypes + 1) offsets of the beginning on each type in the CSR structure
  • offsets (length = etypes * (maxNV+2)) concatenated CSR offsets, one NV+2-array per edge type
  • ind/adj (legnth = type_offsets[etypes] = total number of edges) concatenated CSR adjacency arrays, offsets into this are type_offsets[etype] + offets[etype*(maxNV+2) + sourcevertex]
  • weight (legnth = type_offsets[etypes] = total number of edges) concatenated csr weight arrays, offsets into this are type_offsets[etype] + offets[etype*(maxnv+2) + sourcevertex]
  • time first (legnth = type_offsets[etypes] = total number of edges) concatenated csr timefirst arrays, offsets into this are type_offsets[etype] + offets[etype*(maxnv+2) + sourcevertex]
  • time recent (legnth = type_offsets[etypes] = total number of edges) concatenated csr time recent arrays, offsets into this are type_offsets[etype] + offets[etype*(maxnv+2) + sourcevertex]
    Parameters
    SA pointer to the Stinger to be saved.
    maxVtxThe maximum vertex ID + 1.
    stingerfileThe path and name of the output file.
    Returns
    0 on success, -1 on failure.

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.

Parameters
GThe STINGER data structure
fromSource vertex ID
toDestination vertex ID
typeEdge type
weightEdge weight to set
Returns
1 on success; 0 otherwise

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.

Parameters
GSTINGER data structure
nvNumber of vertices
etypeEdge type
off_inArray of length nv containing the adjacency offset for each vertex
phys_adj_inArray containing the destination vertex of each edge
weight_inArray containing integer weight of each edge
ts_inArray containing recent timestamp of edge edge (or NULL)
first_ts_inArray containing the first timestamp of each edge (or NULL)
single_tsValue for timestamps if either of the above is NULL
Returns
Void

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.

Parameters
S_The STINGER data structure
i_Logical vertex ID
type_Vertex type
Returns
1 on success

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.

Parameters
S_The STINGER data structure
i_Logical vertex ID
weight_Vertex weight
Returns
1 on success

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].

Parameters
nactionsNumber of edge actions
actionsThe packed array of edge insertions and deletions
insoffFor each incident vertex in the batch, the offset into act[] of the first edge insertion
deloffFor each incident vertex in the batch, the offset into act[] of the first edge deletion
actSorted array of edge insertions and deletions
Returns
The number of incident vertices in the batch (the size of insoff[] and deloff[])

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.

Parameters
SThe STINGER data structure
Returns
The number of edges in STINGER

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.

Parameters
SThe STINGER data structure
iLogical vertex ID
typeEdge type
Returns
Out-degree of vertex i with type

References stinger_eb::edges, stinger_eb::etype, stinger_eb::next, and stinger_eb::numEdges.

XMTI int64_t stinger_vtype ( const struct stinger S_,
int64_t  i_ 
)

Returns the vertex type.

Parameters
S_The STINGER data structure
i_Logical vertex ID
Returns
Type of vertex i_

References stinger::LVA, and stinger_vb::vtype.

Referenced by stinger_iterator_check_vtype(), and stinger_save_to_file().

XMTI int64_t stinger_vweight ( const struct stinger S_,
int64_t  i_ 
)

Returns the vertex weight.

Parameters
S_The STINGER data structure
i_Logical vertex ID
Returns
Weight of vertex i_

References stinger::LVA, and stinger_vb::weight.

Referenced by stinger_save_to_file().

 

comments powered by Disqus