Defined in File DHBGraph.hpp
( ) parallel iterator methods.
For a detailed description of DHB, refer to the paper: [A Fast Data Structure for Dynamic Graphs Based on Hash-Indexed Adjacency Blocks (2022): https://drops.dagstuhl.de/storage/00lipics/lipics-vol233-sea2022/LIPIcs.SEA.2022.11/LIPIcs.SEA.2022.11.pdf)
Note
The DHB graph wrapper is still experimental. We tried to align our interface with the Graph class, though it may not yet be an “ad-hoc
replacement” class working with your client code as it did with GraphTODO:
[ ] Review the passing by value semantics for all lambdas passed to a method such as f(L handle). Instead, we might want to pass all lambdas by rvalue-reference as in f(L&& handle).
Public Types
Public Functions
Create a graph of n nodes. The graph has assignable edge weights if weighted is set to true. If weighted is set to false each edge has edge weight 1.0 and any other weight assignment will be ignored.
n – Number of nodes.
weighted – If set to true, the graph has edge weights.
directed – If set to true, the graph will be directed.
Generate a weighted graph from a list of edges. (Useful for small graphs in unit tests that you do not want to read from a file.)
edges – [in] list of weighted edges
Create a graph as copy of other.
other – The graph to copy.
Default destructor
EDGE IDS Initially assign integer edge identifiers.
force – Force re-indexing of edges even if they have already been indexed
Checks if edges have been indexed
bool if edges have been indexed
Get the Edge (u,v) of the given id. (inverse to edgeId)
Note
Time complexity of this function is O(n).
Get an upper bound for the edge ids in the graph.
An upper bound for the edge ids.
Sort edges according to accending neighbors for all vertices.
Default graph class: Sorts the adjacency arrays by a custom criterion. DHB: Sorts the neighbors by a custom criterion.
lambda – Lambda function used to sort the edges. Default graph class: It takes two WeightedEdge e1 and e2 as input parameters, returns true if e1 < e2, false otherwise. DHB: It takes node a_vertex, edgeweight a_weight, edgeid a_id, node b_vertex, edgeweight b_weight, edgeid b_id, as input parameters, and compares them according to lambda. TODO: Maybe we need to think of a nicer way for the interface in lambda.
Set edge count of the graph to edges.
edges – the edge count of a graph
Set upper bound of edge count.
newBound – New upper edge id bound.
Set the number of self-loops.
loops – New number of self-loops.
Add numberOfNewNodes new nodes.
numberOfNewNodes – Number of new nodes.
The index of the last node added.
Removing a vertex is not supported in dhb. This will not remove the node but all neighbors of the given node v TODO: In the future, we might want to make removeNode to use the concurrent version of forNeighbors. But in that case, we need to make this function thread safe. Incoming as well as outgoing edges will be removed.
u – Node.
Check if node v exists in the graph.
v – Node.
true if v exists, false otherwise.
NODE PROPERTIES Returns the number of outgoing neighbors of v.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
v – Node.
The number of outgoing neighbors.
Get the number of incoming neighbors of v.
Note
If the graph is not directed, the outgoing degree is returned.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
v – Node.
The number of incoming neighbors.
Get the number of outgoing neighbors of v.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
v – Node.
The number of outgoing neighbors.
Check whether v is isolated, i.e. degree is 0.
v – Node. If graph is directed, the function runs in O(n) since it needs to iterate over all edges.
true if the node is isolated (= degree is 0)
Returns the weighted degree of u.
u – Node.
countSelfLoopsTwice – If set to true, self-loops will be counted twice.
Weighted degree of u.
Returns the weighted in-degree of u.
u – Node.
countSelfLoopsTwice – If set to true, self-loops will be counted twice.
Weighted in-degree of v.
Insert an edge between the nodes u and v. If the graph is weighted you can optionally set a weight for this edge. The default weight is 1.0. Note: Multi-edges are not supported and will NOT be handled consistently by the graph data structure. It is possible to check for multi-edges by enabling parameter “checkForMultiEdges”. If already present, the new edge is not inserted. Enabling this check increases the complexity of the function to O(max(deg(u), deg(v))).
u – Endpoint of edge.
v – Endpoint of edge.
weight – Optional edge weight.
do_update – (Optional) If set to true, the function will update existing edges with new data; if false, it will only insert new edges.
true if edge has been added, false otherwise (in case checkMultiEdge is set to true and the new edge would have been a multi-edge.)
Adds a collection of weighted edges to the DHBGraph.
This function takes a vector of WeightedEdge objects and attempts to add them to the DHBGraph instance. It processes the edges in parallel. Depending on the value of do_update, the function either updates existing edges with new data or inserts new edges. After adding the edges, edge ids of the new edges will not be updated. Please call indexEdges(true) to index all the edges if needed.
weighted_edges – [in] A vector of WeightedEdge objects to be added to the graph. This parameter is an rvalue reference.
do_update – [in] A boolean flag indicating whether existing edges should be updated. If true, the function will update existing edges; if false, it will only insert new edges.
Converts a vector of Edge objects to WeightedEdge and adds them to the DHBGraph.
edges – [in] A vector of Edge objects to be converted and added to the graph. This parameter is an rvalue reference.
do_update – [in] A boolean flag indicating whether existing edges should be updated. If true, the function will update existing edges; if false, it will only insert new edges.
Removes the undirected edge {u,v}.
u – Endpoint of edge.
v – Endpoint of edge. DHB: Does not support maintaining compact edges or maintain sorted edges.
Removes all the edges in the graph.
Removes edges adjacent to a node according to a specific criterion.
u – The node whose adjacent edges shall be removed.
condition – A function that takes a node as an input and returns a bool. If true the edge (u, v) is removed.
edgesIn – Whether in-going or out-going edges shall be removed.
std::pair<count, count> The number of removed edges (first) and the number of removed self-loops (second).
Removes all self-loops in the graph.
Swaps edge target of edge (source_a, target_a) with edge target of edge {source_b, target_b} such that (source_a, target_b) and (source_b, target_a).
Edge weights or edge ids are preserved.
A std::runtime_error() is thrown if:
edge (source_a, target_a) does not exist
edge (source_b, target_b) does not exist
edge (source_a, target_b) does already exist
edge (source_b, target_a) does already exist
Checks if undirected edge {u,v} exists in the graph.
u – Endpoint of edge.
v – Endpoint of edge.
true if the edge exists, false otherwise.
Returns true if this graph supports edge weights other than 1.0.
true if this graph supports edge weights other than 1.0.
Return true if this graph supports directed edges.
true if this graph supports directed edges.
Return true if graph contains no nodes.
true if graph contains no nodes.
Return the number of nodes in the graph.
The number of nodes.
Return the number of edges in the graph.
The number of edges.
Return the number of loops {v,v} in the graph.
Note
This involves calculation, so store result if needed multiple times.
The number of loops.
Get an upper bound for the node ids in the graph.
An upper bound for the node ids.
Retrieve the weight of an edge.
BEWARE: Running time is \Theta(1) for DHB implementation.
u – Endpoint of edge.
v – Endpoint of edge.
Edge weight of edge {u,v} or 0 if edge does not exist.
Set the weight of an edge. If the edge does not exist, it will be inserted.
u – [in] endpoint of edge
v – [in] endpoint of edge
weight – [in] edge weight
Set the weight to the i-th neighbour of u.
u – [in] endpoint of edge
i – [in] index of the nexight
weight – [in] edge weight
Increase the weight of an edge. If the edge does not exist, it will be inserted.
u – [in] endpoint of edge
v – [in] endpoint of edge
weight – [in] edge weight
Returns the sum of all edge weights.
The sum of all edge weights.
Get an iterable range over the nodes of the graph.
Iterator range over the nodes of the graph.
Get an iterable range over the edges of the graph.
Iterator range over the edges of the graph.
Get an iterable range over the edges of the graph and their weights.
Iterator range over the edges of the graph and their weights.
Get an iterable range over the neighbors of .
u – Node.
Iterator range over the neighbors of u.
Get an iterable range over the neighbors of u including the edge weights.
u – Node.
Iterator range over pairs of neighbors of u and corresponding edge weights.
Default Graph class: Returns the index of node v in the array of outgoing edges of node u. DHB: Returns the index of node v in the neighbors of outgoing edges of node u.
u – Node
v – Node
index of node v in the array of outgoing edges of node u. TODO: We might want to support concurrency for this function in the future.
Return the i-th (outgoing) neighbor of u.
u – Node.
i – index; should be in [0, degreeOut(u))
i-th (outgoing) neighbor of u, or none if no such neighbor exists.
Return the i-th (outgoing) neighbor of u.
Note
DHB does not support Unsafe functions. This function is logically the same as using getIthNeighbor(node, index).
u – Node.
i – index; should be in [0, degreeOut(u))
i-th (outgoing) neighbor of u, or nullNodeId if no such neighbor exists.
Return the weight to the i-th (outgoing) neighbor of u.
u – Node.
i – index; should be in [0, degreeOut(u))
edge weight to the i-th (outgoing) neighbor of u, or 0.0 if no such neighbor exists.
Return the weight to the i-th (outgoing) neighbor of u.
Note
DHB does not support Unsafe functions. This function is logically the same as using getIthNeighborWeight(node, index).
u – Node.
i – index; should be in [0, degreeOut(u))
edge weight to the i-th (outgoing) neighbor of u, or 0.0 if no such neighbor exists.
Get i-th (outgoing) neighbor of u and the corresponding edge weight.
u – Node.
i – index; should be in [0, degreeOut(u))
pair: (i-th (outgoing) neighbor of u, corresponding edge weight). Edge weight is defaultEdgeWeight if unweighted. Finally, if neighbor i of vertex u does not exist: returns (index none, 0.0).
Get i-th (outgoing) neighbor of u and the corresponding edge weight.
Note
DHB does not support Unsafe functions. This function is logically the same as using getIthNeighborWithWeight(node, index).
u – Node.
i – index; should be in [0, degreeOut(u))
pair: i-th (outgoing) neighbor of u and the corresponding edge weight, or defaultEdgeWeight if unweighted.
Get i-th (outgoing) neighbor of u and the corresponding edge id.
u – Node.
i – index; should be in [0, degreeOut(u))
pair: i-th (outgoing) neighbor of u and the corresponding edge id, or none if no such neighbor exists.
Iterate over all nodes of the graph and call handle (lambda closure).
handle – Takes parameter (node).
Iterate randomly over all nodes of the graph and call handle (lambda closure).
handle – Takes parameter (node).
Iterate over all nodes of the graph and call handle (lambda closure) as long as condition remains true. This allows for breaking from a node loop. TODO: Check if there’s a way to use omp parallel for in the loop without introducing atomic variable. TODO: We may want to have explict parallel in the function name.
condition – Returning false breaks the loop.
handle – Takes parameter (node).
Iterate randomly over all nodes of the graph and call handle (lambda closure).
handle – Takes parameter (node).
Iterate over all undirected pairs of nodes and call handle (lambda closure).
handle – Takes parameters (node, node).
Iterate over all undirected pairs of nodes in parallel and call handle (lambda closure).
handle – Takes parameters (node, node).
Iterate over all edges of the const graph and call handle (lambda closure).
handle – Takes parameters (node, node), (node, node, edgweight), (node, node, edgeid) or (node, node, edgeweight, edgeid).
Iterate in parallel over all edges of the const graph and call handle (lambda closure).
handle – Takes parameters (node, node) or (node, node, edgweight), (node, node, edgeid) or (node, node, edgeweight, edgeid).
Iterate over all neighbors of a node and call handle (lamdba closure).
Note
For directed graphs only outgoing edges from u are considered. A node is its own neighbor if there is a self-loop.
u – Node.
handle – Takes parameter (node) or (node, edgeweight) which is a neighbor of u.
Iterate over all neighbors of a node and call handle (lamdba closure) concurrently.
Note
For directed graphs only outgoing edges from u are considered. A node is its own neighbor if there is a self-loop.
u – Node.
handle – Takes parameter (node) or (node, edgeweight) which is a neighbor of u.
Iterate over all incident edges of a node and call handle (lamdba closure).
Note
For undirected graphs all edges incident to u are also outgoing edges.
u – Node.
handle – Takes parameters (node, node), (node, node, edgeweight), (node, node, edgeid) or (node, node, edgeweight, edgeid) where the first node is u and the second is a neighbor of u.
Iterate over all incident edges of a node and call handle (lamdba closure).
Note
For undirected graphs all edges incident to u are also outgoing edges.
u – Node.
handle – Takes parameters (node, node), (node, node, edgeweight), (node, node, edgeid) or (node, node, edgeweight, edgeid) where the first node is u and the second is a neighbor of u.
Iterate over all neighbors of a node and call handler (lamdba closure). For directed graphs only incoming edges from u are considered.
Parallel version of forInNeighborsOf
Iterate over all incoming edges of a node and call handler (lamdba closure).
Handle takes parameters (u, v) or (u, v, w) where w is the edge weight.
Note
For undirected graphs all edges incident to u are also incoming edges.
Parallel version of forInEdgesOf
Class to iterate over the in/out neighbors of a node.
Public Types
Public Functions
WARNING: This contructor is required for Python and should not be used as the iterator is not initialized.
Wrapper class to iterate over a range of the neighbors of a node within a for loop.
Public Functions
Class to iterate over the in/out neighbors of a node including the edge weights. Values are std::pair<node, edgeweight>.
Public Types
Public Functions
WARNING: This contructor is required for Python and should not be used as the iterator is not initialized.
Wrapper class to iterate over a range of the neighbors of a node including the edge weights within a for loop. Values are std::pair<node, edgeweight>.
Public Functions