velographx Namespace Reference

Namespaces
namespace	graph_access_detail
namespace	incremental_detail
namespace	io
namespace	kernels
namespace	memory
namespace	storage
namespace	storage_detail

Classes
class	AsyncPartitionLoader
class	BasicIncrementalBFS
class	BasicIncrementalComponents
class	BasicIncrementalKCore
class	BasicIncrementalPageRank
class	BasicIncrementalSSSP
class	BasicIncrementalTriangleCount
class	BasicIncrementalWeightedSSSP
class	ConsolidationController
struct	ConsolidationControllerConfig
struct	ConsolidationPolicy
struct	ConsolidationSignal
struct	ConsolidationSnapshot
class	CsrGraph
class	DynamicGraph
struct	EdgeUpdate
struct	ExecutionEstimate
struct	ExecutionPlan
class	FilePrefetchAdvisor
struct	FilePrefetchResult
class	Frontier
struct	FrontierScheduleDecision
class	IncrementalTriangleCount
class	IoUringPrefetchAdvisor
struct	IoUringPrefetchResult
class	MemoryBudget
struct	NumaInfo
class	NumaLocalScheduler
struct	NumaMemoryRegion
struct	NumaNodeInfo
struct	NumaPlacement
struct	NumaVertexPartition
struct	PageRankValidation
class	PartitionCache
struct	PartitionCacheStats
class	PartitionFile
struct	PartitionFileHeader
struct	RuntimeMetrics
class	TemporalGraph
class	ThreadPool
struct	UpdateBatch
struct	VersionedUpdateBatch
class	WeightedDynamicGraph
struct	WeightedEdgeUpdate
struct	WeightedUpdateBatch
class	WorkStealingPool
struct	WorkStealingStats

Concepts
concept	ReadableGraph
concept	MutableGraph

Typedefs
using	IncrementalBFS = BasicIncrementalBFS< DynamicGraph >
using	IncrementalComponents = BasicIncrementalComponents< DynamicGraph >
using	IncrementalKCore = BasicIncrementalKCore< DynamicGraph >
using	IncrementalPageRank = BasicIncrementalPageRank< DynamicGraph >
using	IncrementalSSSP = BasicIncrementalSSSP< DynamicGraph >
using	IncrementalWeightedSSSP = BasicIncrementalWeightedSSSP< WeightedDynamicGraph >
using	VertexId = std::uint32_t
using	PartitionId = std::uint32_t
using	EdgeWeight = std::uint64_t
using	EdgeOffset = std::uint64_t

Enumerations
enum class	FrontierScheduleMode { vertex_balanced , edge_balanced , hybrid }
enum class	ExecutionMode { incremental , full_recompute }
enum class	NumaMode { auto_detect , off , interleave }
enum class	TraversalDirection { push , pull }

Functions
std::vector< std::uint32_t >	bfs_distances (const CsrGraph &graph, VertexId source)
std::vector< VertexId >	connected_components (const CsrGraph &graph)
std::vector< double >	pagerank (const CsrGraph &graph, double damping=0.85, std::size_t max_iterations=100, double tolerance=1e-10)
std::uint64_t	triangle_count (const CsrGraph &graph)
std::uint64_t	common_neighbor_count (const CsrGraph &graph, VertexId u, VertexId v)
double	jaccard_similarity (const CsrGraph &graph, VertexId u, VertexId v)
template<ReadableGraph Graph>
constexpr std::size_t	vertex_count (const Graph &graph)
template<ReadableGraph Graph>
constexpr bool	is_directed (const Graph &graph)
template<MutableGraph Graph>
constexpr std::uint64_t	graph_version (const Graph &graph)
template<ReadableGraph Graph, class Fn >
void	for_each_neighbor (const Graph &graph, VertexId u, Fn &&fn)
template<ReadableGraph Graph, class Fn >
void	for_each_weighted_neighbor (const Graph &graph, VertexId u, Fn &&fn)
template<ReadableGraph Graph, class Fn >
void	for_each_in_neighbor (const Graph &graph, VertexId v, Fn &&fn)
template<ReadableGraph Graph>
std::size_t	neighbor_count (const Graph &graph, VertexId u)
template<ReadableGraph Graph>
bool	has_edge (const Graph &graph, VertexId u, VertexId v)
template<ReadableGraph Graph>
auto	edge_weight (const Graph &graph, VertexId u, VertexId v)
template<class Graph , class Batch >
void	apply_updates (Graph &graph, const Batch &batch)
CsrGraph	load_edge_list (const std::filesystem::path &path, bool directed=false)
FrontierScheduleDecision	choose_frontier_schedule (const std::vector< std::size_t > &degrees, std::size_t workers, double dense_frontier_fraction=0.08, std::size_t high_degree_threshold=64)
ExecutionPlan	choose_execution (const ExecutionEstimate &e)
std::string	explain (const ExecutionPlan &p)
std::vector< std::size_t >	parse_cpu_list (const std::string &text)
NumaInfo	detect_numa ()
std::string	numa_mode_name (NumaMode mode)
NumaPlacement	choose_numa_placement (const NumaInfo &info, NumaMode mode, std::size_t worker_index)
bool	pin_current_thread_to_cpu (std::size_t cpu_id) noexcept
bool	apply_numa_placement (const NumaPlacement &placement) noexcept
std::vector< NumaPlacement >	plan_numa_workers (const NumaInfo &info, NumaMode mode, std::size_t workers)
bool	linux_mbind_region (void *address, std::size_t bytes, NumaMode mode, std::optional< std::size_t > node_id, std::size_t max_node_id) noexcept
NumaMemoryRegion	allocate_numa_memory (std::size_t bytes, const NumaInfo &info, NumaMode mode, std::optional< std::size_t > node_id=std::nullopt) noexcept
void	first_touch_region (NumaMemoryRegion &region, std::size_t stride=4096) noexcept
void	release_numa_memory (NumaMemoryRegion &region) noexcept
std::string	describe_numa_placement (const NumaPlacement &placement)
std::vector< std::pair< std::size_t, std::size_t > >	contiguous_partitions (std::size_t n, std::size_t parts)
std::vector< NumaVertexPartition >	plan_numa_vertex_partitions (std::size_t vertex_count, const NumaInfo &info, NumaMode mode, std::size_t partitions=0)
std::optional< std::size_t >	numa_node_for_vertex (std::size_t vertex, const std::vector< NumaVertexPartition > &partitions) noexcept
TraversalDirection	choose_direction (std::size_t frontier, std::size_t vertices, std::size_t frontier_edges, std::size_t total_edges)
ConsolidationPolicy	scale_aware_consolidation_policy (std::size_t directed_edges, double latency_ratio=1.25) noexcept
ConsolidationSignal	evaluate_consolidation (std::size_t current_storage_bytes, std::size_t canonical_storage_bytes, double current_neighbor_latency, double canonical_neighbor_latency, ConsolidationPolicy policy={}) noexcept
ConsolidationSnapshot	consolidate_to_csr_snapshot (const DynamicGraph &source)
std::size_t	parse_memory_budget_gib (std::size_t gib)

Variables
constexpr EdgeWeight	kMaxFiniteWeightedDistance
constexpr std::uint32_t	kUnreachable = UINT32_MAX

Typedef Documentation

EdgeOffset

using velographx::EdgeOffset = typedef std::uint64_t

Definition at line 6 of file types.hpp.

EdgeWeight

using velographx::EdgeWeight = typedef std::uint64_t

Definition at line 16 of file weighted_dynamic_graph.hpp.

IncrementalBFS

using velographx::IncrementalBFS = typedef BasicIncrementalBFS<DynamicGraph>

Definition at line 383 of file bfs.hpp.

IncrementalComponents

using velographx::IncrementalComponents = typedef BasicIncrementalComponents<DynamicGraph>

Definition at line 157 of file connected_components.hpp.

IncrementalKCore

using velographx::IncrementalKCore = typedef BasicIncrementalKCore<DynamicGraph>

Definition at line 127 of file kcore.hpp.

IncrementalPageRank

using velographx::IncrementalPageRank = typedef BasicIncrementalPageRank<DynamicGraph>

Definition at line 334 of file pagerank.hpp.

IncrementalSSSP

using velographx::IncrementalSSSP = typedef BasicIncrementalSSSP<DynamicGraph>

Definition at line 69 of file sssp.hpp.

IncrementalWeightedSSSP

using velographx::IncrementalWeightedSSSP = typedef BasicIncrementalWeightedSSSP<WeightedDynamicGraph>

Definition at line 136 of file weighted_sssp.hpp.

PartitionId

using velographx::PartitionId = typedef std::uint32_t

Definition at line 16 of file partition_cache.hpp.

VertexId

typedef std::uint32_t velographx::VertexId

Definition at line 6 of file frontier.hpp.

Enumeration Type Documentation

ExecutionMode

enum class velographx::ExecutionMode

strong

Enumerator
incremental
full_recompute

Definition at line 8 of file execution_plan.hpp.

FrontierScheduleMode

enum class velographx::FrontierScheduleMode

strong

Enumerator
vertex_balanced
edge_balanced
hybrid

Definition at line 11 of file degree_frontier_scheduler.hpp.

NumaMode

enum class velographx::NumaMode

strong

Enumerator
auto_detect
off
interleave

Definition at line 12 of file numa.hpp.

TraversalDirection

enum class velographx::TraversalDirection

strong

Enumerator
push
pull

Definition at line 3 of file push_pull.hpp.

Function Documentation

allocate_numa_memory()

NumaMemoryRegion velographx::allocate_numa_memory ( std::size_t  bytes, const NumaInfo &  info, NumaMode  mode, std::optional< std::size_t >  node_id = std::nullopt  )

inlinenoexcept

Definition at line 106 of file numa_policy.hpp.

References linux_mbind_region(), and off.

apply_numa_placement()

bool velographx::apply_numa_placement ( const NumaPlacement &  placement )

inlinenoexcept

Definition at line 68 of file numa_policy.hpp.

References off, and pin_current_thread_to_cpu().

apply_updates()

template<class Graph , class Batch >

void velographx::apply_updates	(	Graph &	graph,
		const Batch &	batch
	)

Definition at line 178 of file graph_access.hpp.

Referenced by velographx::BasicIncrementalBFS< Graph >::apply(), velographx::BasicIncrementalComponents< Graph >::apply(), velographx::BasicIncrementalKCore< Graph >::apply(), velographx::BasicIncrementalSSSP< Graph >::apply(), velographx::BasicIncrementalTriangleCount< Graph >::apply(), velographx::BasicIncrementalPageRank< Graph >::apply(), and velographx::BasicIncrementalWeightedSSSP< Graph >::apply().

bfs_distances()

std::vector< std::uint32_t > velographx::bfs_distances	(	const CsrGraph &	graph,
		VertexId	source
	)

choose_direction()

TraversalDirection velographx::choose_direction ( std::size_t  frontier, std::size_t  vertices, std::size_t  frontier_edges, std::size_t  total_edges  )

inline

Definition at line 3 of file push_pull.hpp.

References choose_direction(), pull, and push.

Referenced by choose_direction().

choose_execution()

ExecutionPlan velographx::choose_execution ( const ExecutionEstimate &  e )

inline

Definition at line 30 of file execution_plan.hpp.

References velographx::ExecutionEstimate::affected_vertices, velographx::ExecutionEstimate::changed_edges, velographx::ExecutionEstimate::frontier_growth, full_recompute, velographx::ExecutionEstimate::historical_incremental_speedup, velographx::ExecutionEstimate::historical_repair_success_rate, incremental, velographx::ExecutionEstimate::observed_affected_edge_fraction, velographx::ExecutionEstimate::total_edges, and velographx::ExecutionEstimate::total_vertices.

choose_frontier_schedule()

FrontierScheduleDecision velographx::choose_frontier_schedule ( const std::vector< std::size_t > &  degrees, std::size_t  workers, double  dense_frontier_fraction = 0.08, std::size_t  high_degree_threshold = 64  )

inline

Definition at line 25 of file degree_frontier_scheduler.hpp.

References velographx::FrontierScheduleDecision::average_degree, edge_balanced, velographx::FrontierScheduleDecision::frontier_edges, velographx::FrontierScheduleDecision::frontier_vertices, hybrid, velographx::FrontierScheduleDecision::mode, velographx::FrontierScheduleDecision::recommended_grain, and vertex_balanced.

choose_numa_placement()

NumaPlacement velographx::choose_numa_placement ( const NumaInfo &  info, NumaMode  mode, std::size_t  worker_index  )

inline

Definition at line 40 of file numa_policy.hpp.

References off, and velographx::NumaInfo::topology.

Referenced by plan_numa_workers().

common_neighbor_count()

std::uint64_t velographx::common_neighbor_count	(	const CsrGraph &	graph,
		VertexId	u,
		VertexId	v
	)

connected_components()

std::vector< VertexId > velographx::connected_components

(

const CsrGraph &

graph

)

consolidate_to_csr_snapshot()

ConsolidationSnapshot velographx::consolidate_to_csr_snapshot ( const DynamicGraph &  source )

inline

Definition at line 132 of file consolidation.hpp.

References velographx::DynamicGraph::bulk_load_edges(), velographx::DynamicGraph::compact_neighbors(), velographx::DynamicGraph::directed(), velographx::DynamicGraph::edge_count_directed(), velographx::DynamicGraph::is_compact(), velographx::DynamicGraph::neighbors(), velographx::DynamicGraph::storage_bytes(), and velographx::DynamicGraph::vertex_count().

contiguous_partitions()

std::vector< std::pair< std::size_t, std::size_t > > velographx::contiguous_partitions ( std::size_t  n, std::size_t  parts  )

inline

Definition at line 13 of file partitioner.hpp.

Referenced by plan_numa_vertex_partitions().

describe_numa_placement()

std::string velographx::describe_numa_placement ( const NumaPlacement &  placement )

inline

Definition at line 144 of file numa_policy.hpp.

References velographx::NumaPlacement::cpu_id, velographx::NumaPlacement::mode, velographx::NumaPlacement::node_id, numa_mode_name(), and velographx::NumaPlacement::worker_index.

detect_numa()

NumaInfo velographx::detect_numa ( )

inline

Definition at line 50 of file numa.hpp.

References velographx::NumaInfo::native_support, velographx::NumaInfo::nodes, parse_cpu_list(), and velographx::NumaInfo::topology.

edge_weight()

template<ReadableGraph Graph>

auto velographx::edge_weight	(	const Graph &	graph,
		VertexId	u,
		VertexId	v
	)

Definition at line 169 of file graph_access.hpp.

Referenced by velographx::BasicIncrementalWeightedSSSP< Graph >::apply().

evaluate_consolidation()

ConsolidationSignal velographx::evaluate_consolidation ( std::size_t  current_storage_bytes, std::size_t  canonical_storage_bytes, double  current_neighbor_latency, double  canonical_neighbor_latency, ConsolidationPolicy  policy = {}  )

inlinenoexcept

Definition at line 43 of file consolidation.hpp.

explain()

std::string velographx::explain ( const ExecutionPlan &  p )

inline

Definition at line 70 of file execution_plan.hpp.

References velographx::ExecutionPlan::confidence, velographx::ExecutionPlan::estimated_work_fraction, velographx::ExecutionPlan::full_cost, incremental, velographx::ExecutionPlan::incremental_cost, velographx::ExecutionPlan::mode, and velographx::ExecutionPlan::reason.

first_touch_region()

void velographx::first_touch_region ( NumaMemoryRegion &  region, std::size_t  stride = 4096  )

inlinenoexcept

Definition at line 127 of file numa_policy.hpp.

References velographx::NumaMemoryRegion::bytes, and velographx::NumaMemoryRegion::data.

for_each_in_neighbor()

template<ReadableGraph Graph, class Fn >

void velographx::for_each_in_neighbor	(	const Graph &	graph,
		VertexId	v,
		Fn &&	fn
	)

Definition at line 124 of file graph_access.hpp.

References for_each_neighbor(), velographx::graph_access_detail::neighbor_target(), and vertex_count().

Referenced by velographx::BasicIncrementalPageRank< Graph >::apply().

for_each_neighbor()

template<ReadableGraph Graph, class Fn >

void velographx::for_each_neighbor	(	const Graph &	graph,
		VertexId	u,
		Fn &&	fn
	)

Definition at line 98 of file graph_access.hpp.

References velographx::graph_access_detail::neighbor_target().

Referenced by velographx::BasicIncrementalComponents< Graph >::apply(), velographx::BasicIncrementalPageRank< Graph >::apply(), velographx::BasicIncrementalTriangleCount< Graph >::common_neighbors(), for_each_in_neighbor(), has_edge(), neighbor_count(), velographx::BasicIncrementalBFS< Graph >::recompute(), velographx::BasicIncrementalSSSP< Graph >::recompute(), and velographx::BasicIncrementalTriangleCount< Graph >::recompute().

for_each_weighted_neighbor()

template<ReadableGraph Graph, class Fn >

void velographx::for_each_weighted_neighbor	(	const Graph &	graph,
		VertexId	u,
		Fn &&	fn
	)

Definition at line 111 of file graph_access.hpp.

References velographx::graph_access_detail::neighbor_target(), and velographx::graph_access_detail::neighbor_weight().

Referenced by velographx::BasicIncrementalWeightedSSSP< Graph >::recompute().

graph_version()

template<MutableGraph Graph>

constexpr std::uint64_t velographx::graph_version ( const Graph &  graph )

constexpr

Definition at line 89 of file graph_access.hpp.

has_edge()

template<ReadableGraph Graph>

bool velographx::has_edge	(	const Graph &	graph,
		VertexId	u,
		VertexId	v
	)

Definition at line 156 of file graph_access.hpp.

References for_each_neighbor().

Referenced by velographx::BasicIncrementalBFS< Graph >::apply(), velographx::BasicIncrementalComponents< Graph >::apply(), velographx::BasicIncrementalTriangleCount< Graph >::apply(), and velographx::BasicIncrementalTriangleCount< Graph >::common_neighbors().

is_directed()

template<ReadableGraph Graph>

constexpr bool velographx::is_directed ( const Graph &  graph )

constexpr

Definition at line 80 of file graph_access.hpp.

Referenced by velographx::BasicIncrementalBFS< Graph >::apply(), velographx::BasicIncrementalPageRank< Graph >::apply(), velographx::BasicIncrementalComponents< Graph >::BasicIncrementalComponents(), velographx::BasicIncrementalKCore< Graph >::BasicIncrementalKCore(), and velographx::BasicIncrementalTriangleCount< Graph >::validate_graph().

jaccard_similarity()

double velographx::jaccard_similarity	(	const CsrGraph &	graph,
		VertexId	u,
		VertexId	v
	)

linux_mbind_region()

bool velographx::linux_mbind_region ( void *  address, std::size_t  bytes, NumaMode  mode, std::optional< std::size_t >  node_id, std::size_t  max_node_id  )

inlinenoexcept

Definition at line 83 of file numa_policy.hpp.

References interleave, and off.

Referenced by allocate_numa_memory().

load_edge_list()

CsrGraph velographx::load_edge_list	(	const std::filesystem::path &	path,
		bool	directed = false
	)

neighbor_count()

template<ReadableGraph Graph>

std::size_t velographx::neighbor_count	(	const Graph &	graph,
		VertexId	u
	)

Definition at line 143 of file graph_access.hpp.

References for_each_neighbor().

Referenced by velographx::BasicIncrementalPageRank< Graph >::apply(), and velographx::BasicIncrementalTriangleCount< Graph >::common_neighbors().

numa_mode_name()

std::string velographx::numa_mode_name ( NumaMode  mode )

inline

Definition at line 79 of file numa.hpp.

References interleave, and off.

Referenced by describe_numa_placement().

numa_node_for_vertex()

std::optional< std::size_t > velographx::numa_node_for_vertex ( std::size_t  vertex, const std::vector< NumaVertexPartition > &  partitions  )

inlinenoexcept

Definition at line 58 of file partitioner.hpp.

Referenced by velographx::NumaLocalScheduler::preferred_queue_for_vertex().

pagerank()

std::vector< double > velographx::pagerank	(	const CsrGraph &	graph,
		double	damping = 0.85,
		std::size_t	max_iterations = 100,
		double	tolerance = 1e-10
	)

parse_cpu_list()

std::vector< std::size_t > velographx::parse_cpu_list ( const std::string &  text )

inline

Definition at line 26 of file numa.hpp.

Referenced by detect_numa().

parse_memory_budget_gib()

std::size_t velographx::parse_memory_budget_gib ( std::size_t  gib )

inline

Definition at line 13 of file memory_budget.hpp.

pin_current_thread_to_cpu()

bool velographx::pin_current_thread_to_cpu ( std::size_t  cpu_id )

inlinenoexcept

Definition at line 55 of file numa_policy.hpp.

Referenced by apply_numa_placement().

plan_numa_vertex_partitions()

std::vector< NumaVertexPartition > velographx::plan_numa_vertex_partitions ( std::size_t  vertex_count, const NumaInfo &  info, NumaMode  mode, std::size_t  partitions = 0  )

inline

Definition at line 34 of file partitioner.hpp.

References contiguous_partitions(), velographx::NumaVertexPartition::local_cpus, velographx::NumaVertexPartition::node_id, off, velographx::NumaVertexPartition::partition_id, velographx::NumaInfo::topology, velographx::NumaVertexPartition::vertex_begin, vertex_count(), and velographx::NumaVertexPartition::vertex_end.

plan_numa_workers()

std::vector< NumaPlacement > velographx::plan_numa_workers ( const NumaInfo &  info, NumaMode  mode, std::size_t  workers  )

inline

Definition at line 73 of file numa_policy.hpp.

References choose_numa_placement().

release_numa_memory()

void velographx::release_numa_memory ( NumaMemoryRegion &  region )

inlinenoexcept

Definition at line 135 of file numa_policy.hpp.

scale_aware_consolidation_policy()

ConsolidationPolicy velographx::scale_aware_consolidation_policy ( std::size_t  directed_edges, double  latency_ratio = 1.25  )

inlinenoexcept

Definition at line 27 of file consolidation.hpp.

triangle_count()

std::uint64_t velographx::triangle_count

(

const CsrGraph &

graph

)

vertex_count()

template<ReadableGraph Graph>

constexpr std::size_t velographx::vertex_count ( const Graph &  graph )

constexpr

Definition at line 71 of file graph_access.hpp.

Referenced by velographx::BasicIncrementalBFS< Graph >::apply(), velographx::BasicIncrementalKCore< Graph >::apply(), velographx::BasicIncrementalPageRank< Graph >::apply(), velographx::BasicIncrementalPageRank< Graph >::apply_validated(), for_each_in_neighbor(), plan_numa_vertex_partitions(), velographx::BasicIncrementalBFS< Graph >::recompute(), velographx::BasicIncrementalKCore< Graph >::recompute(), velographx::BasicIncrementalSSSP< Graph >::recompute(), velographx::BasicIncrementalTriangleCount< Graph >::recompute(), velographx::BasicIncrementalWeightedSSSP< Graph >::recompute(), velographx::BasicIncrementalPageRank< Graph >::recompute(), and velographx::incremental_detail::recompute_dijkstra().

Variable Documentation

kMaxFiniteWeightedDistance

constexpr EdgeWeight velographx::kMaxFiniteWeightedDistance

inlineconstexpr

Initial value:

=
    std::numeric_limits<EdgeWeight>::max() / 4 - 1

Definition at line 17 of file weighted_dynamic_graph.hpp.

Referenced by velographx::WeightedDynamicGraph::apply().

kUnreachable

constexpr std::uint32_t velographx::kUnreachable = UINT32_MAX

inlineconstexpr

Definition at line 7 of file types.hpp.