#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

Macro Definition Documentation

#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)]

Function Documentation

struct curs etype_begin	(	struct stinger_vb *	v,
		int	etype
	)

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.

Parameters

S	The STINGER data structure
NV	The total number of vertices

Returns: 0 on success; failure otherwise

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

int64_t stinger_eb_type ( const struct stinger_eb * eb_ )

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.

Parameters

G	The STINGER data structure
from	Source vertex ID
to	Destination vertex ID
type	Edge 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

G	The STINGER data structure
from	Source vertex ID
to	Destination vertex ID
type	Edge 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

G	The STINGER data structure
from	Source vertex ID
to	Destination vertex ID
type	Edge type
timestamp	Timestamp 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.

struct stinger_eb* stinger_edgeblocks	(	const struct stinger *	S_,
		int64_t	i_
	)

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.

Parameters

G	The STINGER data structure
from	Source vertex ID
to	Destination vertex ID
type	Edge 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.

void stinger_fragmentation	(	struct stinger *	S,
		uint64_t	NV,
		struct stinger_fragmentation_t *	stats
	)

Calculate statistics on edge block fragmentation in the graph.

Parameters

S	The STINGER data structure
NV	The total number of vertices

Returns: Void

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.

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

S	The 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

S	The 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

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

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

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

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

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

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

S	The 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

G	The STINGER data structure
type	Edge type
from	Source vertex ID
to	Destination 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

G	The STINGER data structure
type	Edge type
from	Source vertex ID
to	Destination vertex ID
weight	Edge weight
timestamp	Edge 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

G	The STINGER data structure
type	Edge type
from	Source vertex ID
to	Destination vertex ID
weight	Edge weight
timestamp	Edge timestamp

Returns: 1

References stinger_incr_edge(), and STINGERASSERTS.

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

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.

Parameters

G	The STINGER data structure
type	Edge type
from	Source vertex ID
to	Destination vertex ID
weight	Edge weight
timestamp	Edge 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

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

struct stinger_eb* stinger_next_eb	(	const struct stinger *	G,
		const struct stinger_eb *	eb_
	)

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.

Parameters

S	The 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

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.

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

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

Parameters

G	The STINGER data structure
type	The 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_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

G	The STINGER data structure
type	Edge type
from	Source vertex ID
to	Destination 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

S A pointer to the Stinger to be saved.

maxVtx The maximum vertex ID + 1.

stingerfile The 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

G	The STINGER data structure
from	Source vertex ID
to	Destination vertex ID
type	Edge type
weight	Edge 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

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

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

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

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

S	The 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

S	The STINGER data structure
i	Logical vertex ID
type	Edge type

Returns: Out-degree of vertex i with 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.

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

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

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

Variable Documentation

struct stinger_eb* ebpool = NULL

Referenced by stinger_incr_edge(), stinger_iterator_consistency_check(), stinger_iterator_next_block_all_types(), stinger_iterator_next_block_by_type(), stinger_iterator_next_block_by_vtx(), stinger_save_to_file(), and stinger_sort_edge_list().

uint64_t ebpool_tail = 0

const int64_t endian_check = 0x1234ABCD

Referenced by main(), snarf_actions(), snarf_graph(), and stinger_save_to_file().

S	A pointer to the Stinger to be saved.
maxVtx	The maximum vertex ID + 1.
stingerfile	The path and name of the output file.

Macros

Functions

Variables

Macro Definition Documentation

Function Documentation

Variable Documentation