Defined in File Graph.hpp
A graph (with optional weights) and parallel iterator methods.
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
Reserves memory in the node’s edge containers for undirected graphs.
This function is thread-safe if called from different threads on different nodes.
u – the node memory should be reserved for
size – the amount of memory to reserve
Reserves memory in the node’s edge containers for directed graphs.
This function is thread-safe if called from different threads on different nodes.
u – the node memory should be reserved for
inSize – the amount of memory to reserve for in edges
outSize – the amount of memory to reserve for out edges
Reserves memory in the node’s edge containers for directed graphs.
This function is thread-safe if called from different threads on different nodes.
u – the node memory should be reserved for
outSize – the amount of memory to reserve for out edges
Reserves memory in the node’s edge containers for directed graphs.
This function is thread-safe if called from different threads on different nodes.
u – the node memory should be reserved for
inSize – the amount of memory to reserve for in edges
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.
GRAPH INFORMATION Try to save some memory by shrinking internal data structures of the graph. Only run this once you finished editing the graph. Otherwise it will cause unnecessary reallocation of memory.
DEPRECATED: this function will no longer be supported in later releases. Compacts the adjacency arrays by re-using no longer needed slots from deleted edges.
Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.
Sorts the adjacency arrays by a custom criterion.
lambda – Lambda function used to sort the edges. It takes two WeightedEdge e1 and e2 as input parameters, returns true if e1 < e2, false otherwise.
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.
Remove a node v and all incident edges from the graph.
Incoming as well as outgoing edges will be removed.
u – Node.
Removes out-going edges from node @u. If the graph is weighted and/or has edge ids, weights and/or edge ids will also be removed.
node – u Node.
Removes in-going edges to node @u. If the graph is weighted and/or has edge ids, weights and/or edge ids will also be removed.
node – u Node.
Check if node v exists in the graph.
v – Node.
true if v exists, false otherwise.
Restores a previously deleted node v with its previous id in the graph.
v – Node.
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.
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.
checkMultiEdge – If true, this enables a check for a possible multi-edge.
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.)
Insert an edge between the nodes u and v. Unline the addEdge function, this function does not not add any information to 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.
ew – Optional edge weight.
index – Optional edge index.
checkMultiEdge – If true, this enables a check for a possible multi-edge.
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.)
Insert an in edge between the nodes u and v in a directed graph. 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.
ew – Optional edge weight.
index – Optional edge index.
checkMultiEdge – If true, this enables a check for a possible multi-edge.
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.)
Insert an out edge between the nodes u and v in a directed graph. 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.
ew – Optional edge weight.
index – Optional edge index.
checkMultiEdge – If true, this enables a check for a possible multi-edge.
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.)
If set to true, the ingoing and outgoing adjacency vectors will automatically be updated to maintain a sorting (if it existed before) by performing up to n-1 swaps. If the user plans to remove multiple edges, better set it to false and call sortEdges() afterwards to avoid redundant swaps. Default = true.
If set to true, the EdgeIDs will automatically be adjusted, so that no gaps in between IDs exist. If the user plans to remove multiple edges, better set it to false and call indexEdges(force=true) afterwards to avoid redundant re-indexing. Default = true.
Returns true if edges are currently being sorted when removeEdge() is called.
Removes the undirected edge {u,v}.
u – Endpoint of edge.
v – Endpoint of edge.
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.
Removes all multi-edges in the graph.
Changes the edges {s1, t1} into {s1, t2} and the edge {s2, t2} into {s2, t1}.
If there are edge weights or edge ids, they are preserved. Note that no check is performed if the swap is actually possible, i.e. does not generate duplicate edges.
s1 – The first source
t1 – The first target
s2 – The second source
t2 – The second target
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.
Check for invalid graph states, such as multi-edges.
False if the graph is in invalid state.
Trigger a time step - increments counter.
This method is deprecated and will not be supported in future releases.
Get time step counter.
This method is deprecated and will not be supported in future releases.
Time step counter.
Return edge weight of edge {u,v}. Returns 0 if edge does not exist. BEWARE: Running time is \Theta(deg(u))!
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
Set the weight to the i-th incoming 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.
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 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 +inf if no such neighbor exists.
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.
Get an iterable range over the in-neighbors of .
u – Node.
Iterator range over pairs of in-neighbors of u.
Get an iterable range over the in-neighbors of u including the edge weights.
u – Node.
Iterator range over pairs of in-neighbors of u and corresponding edge weights.
Returns the index of node v in the array of outgoing edges of node u.
u – Node
v – Node
index of node v in the array of outgoing edges of node u.
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 (incoming) neighbor of u.
u – Node.
i – index; should be in [0, degreeIn(u))
i-th (incoming) neighbor of u, or none 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 +inf 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 and the corresponding edge weight, or defaultEdgeWeight if unweighted.
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 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.
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 in parallel over all nodes of the graph and call handler (lambda closure). Using schedule(guided) to remedy load-imbalances due to e.g. unequal degree distribution.
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 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.
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.
Wrapper class to iterate over a range of the neighbors of a node within a for loop.
Public Functions
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