All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Friends | List of all members
NetworKit::Graph Class Referencefinal

A graph (with optional weights) and parallel iterator methods. More...

#include <Graph.h>

Public Member Functions

 Graph (count n=0, bool weighted=false, bool directed=false)
 Create a graph of n nodes. More...
 
 Graph (const Graph &G, bool weighted, bool directed)
 
 Graph (std::initializer_list< WeightedEdge > edges)
 Generate a weighted graph from a list of edges. More...
 
 Graph (const Graph &other)=default
 Create a graph as copy of other. More...
 
 Graph (Graph &&other)=default
 Default move constructor. More...
 
 ~Graph ()=default
 Default destructor. More...
 
Graphoperator= (Graph &&other)=default
 Default move assignment operator. More...
 
Graphoperator= (const Graph &other)=default
 Default copy assignment operator. More...
 
void indexEdges (bool force=false)
 EDGE IDS. More...
 
bool hasEdgeIds () const
 Checks if edges have been indexed. More...
 
edgeid edgeId (node u, node v) const
 Get the id of the given edge. More...
 
index upperEdgeIdBound () const
 Get an upper bound for the edge ids in the graph. More...
 
count getId () const
 GRAPH INFORMATION. More...
 
std::string typ () const
 Return the type of the graph. More...
 
void shrinkToFit ()
 Try to save some memory by shrinking internal data structures of the graph. More...
 
void compactEdges ()
 Compacts the adjacency arrays by re-using no longer neede slots from deleted edges. More...
 
void sortEdges ()
 Sorts the adjacency arrays by node id. More...
 
void setName (std::string name)
 Set name of graph to name. More...
 
std::string getName () const
 
std::string toString () const
 Returns a string representation of the graph. More...
 
Graph copyNodes () const
 COPYING. More...
 
node addNode ()
 Add a new node to the graph and return it. More...
 
node addNode (float x, float y)
 DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes. More...
 
void removeNode (node v)
 Remove a node v and all incident edges from the graph. More...
 
bool hasNode (node v) const
 Check if node v exists in the graph. More...
 
void restoreNode (node v)
 Restores a previously deleted node v with its previous id in the graph. More...
 
void append (const Graph &G)
 Appends another graph to this graph as a new subgraph. More...
 
void merge (const Graph &G)
 Modifies this graph to be the union of it and another graph. More...
 
Graph subgraphFromNodes (const std::unordered_set< node > &nodes) const
 
count degree (node v) const
 NODE PROPERTIES. More...
 
count degreeIn (node v) const
 Get the number of incoming neighbors of v. More...
 
count degreeOut (node v) const
 Get the number of outgoing neighbors of v. More...
 
bool isIsolated (node v) const
 Check whether v is isolated, i.e. More...
 
edgeweight weightedDegree (node v) const
 Returns the weighted degree of v. More...
 
edgeweight volume (node v) const
 Returns the volume of the v, which is the weighted degree with self-loops counted twice. More...
 
node randomNode () const
 Returns a random node of the graph. More...
 
node randomNeighbor (node u) const
 Returns a random neighbor of u and none if degree is zero. More...
 
void addEdge (node u, node v, edgeweight ew=defaultEdgeWeight)
 Insert an edge between the nodes u and v. More...
 
void removeEdge (node u, node v)
 Removes the undirected edge {u,v}. More...
 
void removeSelfLoops ()
 Removes all self-loops in the graph. More...
 
void swapEdge (NetworKit::node s1, NetworKit::node t1, NetworKit::node s2, NetworKit::node t2)
 Changes the edges {s1, t1} into {s1, t2} and the edge {s2, t2} into {s2, t1}. More...
 
bool hasEdge (node u, node v) const
 Checks if undirected edge {u,v} exists in the graph. More...
 
std::pair< node, noderandomEdge (bool uniformDistribution=false) const
 Returns a random edge. More...
 
std::vector< std::pair< node,
node > > 
randomEdges (count nr) const
 Returns a vector with nr random edges. More...
 
bool isWeighted () const
 Returns true if this graph supports edge weights other than 1.0. More...
 
bool isDirected () const
 Return true if this graph supports directed edges. More...
 
bool isEmpty () const
 Return true if graph contains no nodes. More...
 
count numberOfNodes () const
 Return the number of nodes in the graph. More...
 
count numberOfEdges () const
 Return the number of edges in the graph. More...
 
std::pair< count, count > const size () const
 
double density () const
 
count numberOfSelfLoops () const
 Return the number of loops {v,v} in the graph. More...
 
index upperNodeIdBound () const
 Get an upper bound for the node ids in the graph. More...
 
bool checkConsistency () const
 Check for invalid graph states, such as multi-edges. More...
 
void timeStep ()
 Trigger a time step - increments counter. More...
 
count time ()
 Get time step counter. More...
 
void setCoordinate (node v, Point< float > value)
 DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes. More...
 
Point< float > & getCoordinate (node v)
 DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes. More...
 
float minCoordinate (count dim)
 DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes. More...
 
float maxCoordinate (count dim)
 DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes. More...
 
void initCoordinates ()
 DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes. More...
 
edgeweight weight (node u, node v) const
 Return edge weight of edge {u,v}. More...
 
void setWeight (node u, node v, edgeweight ew)
 Set the weight of an edge. More...
 
void increaseWeight (node u, node v, edgeweight ew)
 Increase the weight of an edge. More...
 
edgeweight totalEdgeWeight () const
 Returns the sum of all edge weights. More...
 
std::vector< nodenodes () const
 Get list of all nodes. More...
 
std::vector< std::pair< node,
node > > 
edges () const
 Get list of edges as node pairs. More...
 
std::vector< nodeneighbors (node u) const
 Get list of neighbors of u. More...
 
template<bool graphIsDirected>
node getIthNeighbor (node u, index i) const
 Get i-th (outgoing) neighbor of u. More...
 
Graph toUndirected () const
 Return an undirected version of this graph. More...
 
Graph toUnweighted () const
 Return an unweighted version of this graph. More...
 
Graph transpose () const
 Return the transpose of this graph. More...
 
template<typename L >
void forNodes (L handle) const
 Iterate over all nodes of the graph and call handle (lambda closure). More...
 
template<typename L >
void parallelForNodes (L handle) const
 Iterate randomly over all nodes of the graph and call handle (lambda closure). More...
 
template<typename C , typename L >
void forNodesWhile (C condition, L handle) const
 Iterate over all nodes of the graph and call handle (lambda closure) as long as condition remains true. More...
 
template<typename L >
void forNodesInRandomOrder (L handle) const
 Iterate randomly over all nodes of the graph and call handle (lambda closure). More...
 
template<typename L >
void balancedParallelForNodes (L handle) const
 Iterate in parallel over all nodes of the graph and call handler (lambda closure). More...
 
template<typename L >
void forNodePairs (L handle) const
 Iterate over all undirected pairs of nodes and call handle (lambda closure). More...
 
template<typename L >
void parallelForNodePairs (L handle) const
 Iterate over all undirected pairs of nodes in parallel and call handle (lambda closure). More...
 
template<typename L >
void forEdges (L handle) const
 Iterate over all edges of the const graph and call handle (lambda closure). More...
 
template<typename L >
void parallelForEdges (L handle) const
 Iterate in parallel over all edges of the const graph and call handle (lambda closure). More...
 
template<typename L >
void forNeighborsOf (node u, L handle) const
 Iterate over all neighbors of a node and call handle (lamdba closure). More...
 
template<typename L >
void forEdgesOf (node u, L handle) const
 Iterate over all incident edges of a node and call handle (lamdba closure). More...
 
template<typename L >
void forInNeighborsOf (node u, L handle) const
 Iterate over all neighbors of a node and call handler (lamdba closure). More...
 
template<typename L >
void forInEdgesOf (node u, L handle) const
 Iterate over all incoming edges of a node and call handler (lamdba closure). More...
 
template<typename L >
double parallelSumForNodes (L handle) const
 Iterate in parallel over all nodes and sum (reduce +) the values returned by the handler. More...
 
template<typename L >
double parallelSumForEdges (L handle) const
 Iterate in parallel over all edges and sum (reduce +) the values returned by the handler. More...
 
template<typename L >
void BFSfrom (node r, L handle) const
 Iterate over nodes in breadth-first search order starting from r until connected component of r has been visited. More...
 
template<typename L >
void BFSfrom (const std::vector< node > &startNodes, L handle) const
 
template<typename L >
void BFSEdgesFrom (node r, L handle) const
 
template<typename L >
void DFSfrom (node r, L handle) const
 Iterate over nodes in depth-first search order starting from r until connected component of r has been visited. More...
 
template<typename L >
void DFSEdgesFrom (node r, L handle) const
 

Friends

class ParallelPartitionCoarsening
 
class GraphBuilder
 

Detailed Description

A graph (with optional weights) and parallel iterator methods.

Constructor & Destructor Documentation

NetworKit::Graph::Graph ( count  n = 0,
bool  weighted = false,
bool  directed = false 
)

Create a graph of n nodes.

CONSTRUCTORS.

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.

Parameters
nNumber of nodes.
weightedIf set to true, the graph has edge weights.
directedIf set to true, the graph will be directed.
NetworKit::Graph::Graph ( const Graph G,
bool  weighted,
bool  directed 
)
NetworKit::Graph::Graph ( std::initializer_list< WeightedEdge edges)

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

Parameters
[in]edgeslist of weighted edges
NetworKit::Graph::Graph ( const Graph other)
default

Create a graph as copy of other.

Parameters
otherThe graph to copy.
NetworKit::Graph::Graph ( Graph &&  other)
default

Default move constructor.

NetworKit::Graph::~Graph ( )
default

Default destructor.

Member Function Documentation

void NetworKit::Graph::addEdge ( node  u,
node  v,
edgeweight  ew = defaultEdgeWeight 
)

Insert an edge between the nodes u and v.

EDGE MODIFIERS.

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.

Parameters
uEndpoint of edge.
vEndpoint of edge.
weightOptional edge weight.
node NetworKit::Graph::addNode ( )

Add a new node to the graph and return it.

NODE MODIFIERS.

Returns
The new node.
node NetworKit::Graph::addNode ( float  x,
float  y 
)

DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes.

Add a new node to the graph with coordinates x and and return it.

void NetworKit::Graph::append ( const Graph G)

Appends another graph to this graph as a new subgraph.

Performs node id remapping.

Parameters
G[description]
template<typename L >
void NetworKit::Graph::balancedParallelForNodes ( handle) const

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.

Parameters
handleTakes parameter (node).
template<typename L >
void NetworKit::Graph::BFSEdgesFrom ( node  r,
handle 
) const
template<typename L >
void NetworKit::Graph::BFSfrom ( node  r,
handle 
) const

Iterate over nodes in breadth-first search order starting from r until connected component of r has been visited.

Parameters
rNode.
handleTakes parameter (node).
template<typename L >
void NetworKit::Graph::BFSfrom ( const std::vector< node > &  startNodes,
handle 
) const
bool NetworKit::Graph::checkConsistency ( ) const

Check for invalid graph states, such as multi-edges.

Returns
False if the graph is in invalid state.
void NetworKit::Graph::compactEdges ( )

Compacts the adjacency arrays by re-using no longer neede slots from deleted edges.

Graph NetworKit::Graph::copyNodes ( ) const

COPYING.

count NetworKit::Graph::degree ( node  v) const
inline

NODE PROPERTIES.

Returns the number of outgoing neighbors of v.

Parameters
vNode.
Returns
The number of outgoing neighbors.
count NetworKit::Graph::degreeIn ( node  v) const
inline

Get the number of incoming neighbors of v.

Parameters
vNode.
Returns
The number of incoming neighbors.
Note
If the graph is not directed, the outgoing degree is returned.
count NetworKit::Graph::degreeOut ( node  v) const
inline

Get the number of outgoing neighbors of v.

Parameters
vNode.
Returns
The number of outgoing neighbors.
double NetworKit::Graph::density ( ) const
inline
Returns
the density of the graph
template<typename L >
void NetworKit::Graph::DFSEdgesFrom ( node  r,
handle 
) const
template<typename L >
void NetworKit::Graph::DFSfrom ( node  r,
handle 
) const

Iterate over nodes in depth-first search order starting from r until connected component of r has been visited.

Parameters
rNode.
handleTakes parameter (node).
edgeid NetworKit::Graph::edgeId ( node  u,
node  v 
) const

Get the id of the given edge.

std::vector< std::pair< node, node > > NetworKit::Graph::edges ( ) const

Get list of edges as node pairs.

Returns
List of edges as node pairs.
template<typename L >
void NetworKit::Graph::forEdges ( handle) const

Iterate over all edges of the const graph and call handle (lambda closure).

Parameters
handleTakes parameters (node, node), (node, node, edgweight), (node, node, edgeid) or (node, node, edgeweight, edgeid).
template<typename L >
void NetworKit::Graph::forEdgesOf ( node  u,
handle 
) const

Iterate over all incident edges of a node and call handle (lamdba closure).

Parameters
uNode.
handleTakes 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.
Note
For undirected graphs all edges incident to u are also outgoing edges.
template<typename L >
void NetworKit::Graph::forInEdgesOf ( node  u,
handle 
) const

Iterate over all incoming edges of a node and call handler (lamdba closure).

Note
For undirected graphs all edges incident to u are also incoming edges.

Handle takes parameters (u, v) or (u, v, w) where w is the edge weight.

template<typename L >
void NetworKit::Graph::forInNeighborsOf ( node  u,
handle 
) const

Iterate over all neighbors of a node and call handler (lamdba closure).

For directed graphs only incoming edges from u are considered.

template<typename L >
void NetworKit::Graph::forNeighborsOf ( node  u,
handle 
) const

Iterate over all neighbors of a node and call handle (lamdba closure).

Parameters
uNode.
handleTakes parameter (node) or (node, edgeweight) which is a neighbor of u.
Note
For directed graphs only outgoing edges from u are considered. A node is its own neighbor if there is a self-loop.
template<typename L >
void NetworKit::Graph::forNodePairs ( handle) const

Iterate over all undirected pairs of nodes and call handle (lambda closure).

Parameters
handleTakes parameters (node, node).
template<typename L >
void NetworKit::Graph::forNodes ( handle) const

Iterate over all nodes of the graph and call handle (lambda closure).

Parameters
handleTakes parameter (node).
template<typename L >
void NetworKit::Graph::forNodesInRandomOrder ( handle) const

Iterate randomly over all nodes of the graph and call handle (lambda closure).

Parameters
handleTakes parameter (node).
template<typename C , typename L >
void NetworKit::Graph::forNodesWhile ( condition,
handle 
) const

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.

Parameters
conditionReturning false breaks the loop.
handleTakes parameter (node).
Point<float>& NetworKit::Graph::getCoordinate ( node  v)
inline

DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes.

Get the coordinate of v.

Parameters
vNode.
Returns
The coordinate of v.
count NetworKit::Graph::getId ( ) const
inline

GRAPH INFORMATION.

Get the ID of this graph. The ID is a unique unsigned integer given to every graph on construction.

template<bool graphIsDirected>
node NetworKit::Graph::getIthNeighbor ( node  u,
index  i 
) const
inline

Get i-th (outgoing) neighbor of u.

WARNING: This function is deprecated or only temporary.

Parameters
uNode.
iindex; should be in [0, degreeOut(u))
Returns
i -th (outgoing) neighbor of u, or none if no such neighbor exists.
std::string NetworKit::Graph::getName ( ) const
inline
bool NetworKit::Graph::hasEdge ( node  u,
node  v 
) const

Checks if undirected edge {u,v} exists in the graph.

Parameters
uEndpoint of edge.
vEndpoint of edge.
Returns
true if the edge exists, false otherwise.
bool NetworKit::Graph::hasEdgeIds ( ) const
inline

Checks if edges have been indexed.

Returns
bool if edges have been indexed
bool NetworKit::Graph::hasNode ( node  v) const
inline

Check if node v exists in the graph.

Parameters
vNode.
Returns
true if v exists, false otherwise.
void NetworKit::Graph::increaseWeight ( node  u,
node  v,
edgeweight  ew 
)

Increase the weight of an edge.

If the edge does not exist, it will be inserted.

Parameters
[in]uendpoint of edge
[in]vendpoint of edge
[in]weightedge weight
void NetworKit::Graph::indexEdges ( bool  force = false)

EDGE IDS.

Initially assign integer edge identifiers.

Parameters
forceForce re-indexing of edges even if they have already been indexed
void NetworKit::Graph::initCoordinates ( )
inline

DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes.

Initializes the coordinates for the nodes in graph.

Note
This has to be called once and before you set coordinates. Call this method again if new nodes have been added.
bool NetworKit::Graph::isDirected ( ) const
inline

Return true if this graph supports directed edges.

Returns
true if this graph supports directed edges.
bool NetworKit::Graph::isEmpty ( ) const
inline

Return true if graph contains no nodes.

Returns
true if graph contains no nodes.
bool NetworKit::Graph::isIsolated ( node  v) const
inline

Check whether v is isolated, i.e.

degree is 0.

Parameters
vNode.
Returns
true if the node is isolated (= degree is 0)
bool NetworKit::Graph::isWeighted ( ) const
inline

Returns true if this graph supports edge weights other than 1.0.

Returns
true if this graph supports edge weights other than 1.0.
float NetworKit::Graph::maxCoordinate ( count  dim)
inline

DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes.

Get maximum coordinate of all coordinates with respect to dimension dim.

Parameters
dimThe dimension to search for maximum.
Returns
The maximum coordinate in dimension dim.
void NetworKit::Graph::merge ( const Graph G)

Modifies this graph to be the union of it and another graph.

Nodes with the same ids are identified with each other.

Parameters
G[description]
float NetworKit::Graph::minCoordinate ( count  dim)
inline

DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes.

Get minimum coordinate of all coordinates with respect to dimension dim.

Parameters
dimThe dimension to search for minimum.
Returns
The minimum coordinate in dimension dim.
std::vector< node > NetworKit::Graph::neighbors ( node  u) const

Get list of neighbors of u.

Parameters
uNode.
Returns
List of neighbors of u.
std::vector< node > NetworKit::Graph::nodes ( ) const

Get list of all nodes.

Collections.

Returns
List of all nodes.
count NetworKit::Graph::numberOfEdges ( ) const
inline

Return the number of edges in the graph.

Returns
The number of edges.
count NetworKit::Graph::numberOfNodes ( ) const
inline

Return the number of nodes in the graph.

Returns
The number of nodes.
count NetworKit::Graph::numberOfSelfLoops ( ) const

Return the number of loops {v,v} in the graph.

GLOBAL PROPERTIES.

Returns
The number of loops.
Note
This involves calculation, so store result if needed multiple times.
Graph& NetworKit::Graph::operator= ( Graph &&  other)
default

Default move assignment operator.

Graph& NetworKit::Graph::operator= ( const Graph other)
default

Default copy assignment operator.

template<typename L >
void NetworKit::Graph::parallelForEdges ( handle) const

Iterate in parallel over all edges of the const graph and call handle (lambda closure).

Parameters
handleTakes parameters (node, node) or (node, node, edgweight), (node, node, edgeid) or (node, node, edgeweight, edgeid).
template<typename L >
void NetworKit::Graph::parallelForNodePairs ( handle) const

Iterate over all undirected pairs of nodes in parallel and call handle (lambda closure).

Parameters
handleTakes parameters (node, node).
template<typename L >
void NetworKit::Graph::parallelForNodes ( handle) const

Iterate randomly over all nodes of the graph and call handle (lambda closure).

Parameters
handleTakes parameter (node).
template<typename L >
double NetworKit::Graph::parallelSumForEdges ( handle) const

Iterate in parallel over all edges and sum (reduce +) the values returned by the handler.

template<typename L >
double NetworKit::Graph::parallelSumForNodes ( handle) const

Iterate in parallel over all nodes and sum (reduce +) the values returned by the handler.

std::pair< node, node > NetworKit::Graph::randomEdge ( bool  uniformDistribution = false) const

Returns a random edge.

By default a random node u is chosen and then some random neighbor v. So the probability of choosing (u, v) highly depends on the degree of u. Setting uniformDistribution to true, will give you a real uniform distributed edge, but will be very slow. So only use uniformDistribution for single calls outside of any loops.

std::vector< std::pair< node, node > > NetworKit::Graph::randomEdges ( count  nr) const

Returns a vector with nr random edges.

The edges are chosen uniform random.

node NetworKit::Graph::randomNeighbor ( node  u) const

Returns a random neighbor of u and none if degree is zero.

Parameters
uNode.
Returns
A random neighbor of u.
node NetworKit::Graph::randomNode ( ) const

Returns a random node of the graph.

Returns
A random node.
void NetworKit::Graph::removeEdge ( node  u,
node  v 
)

Removes the undirected edge {u,v}.

Parameters
uEndpoint of edge.
vEndpoint of edge.
void NetworKit::Graph::removeNode ( node  v)

Remove a node v and all incident edges from the graph.

Incoming as well as outgoing edges will be removed.

Parameters
uNode.
void NetworKit::Graph::removeSelfLoops ( )

Removes all self-loops in the graph.

void NetworKit::Graph::restoreNode ( node  v)

Restores a previously deleted node v with its previous id in the graph.

Parameters
vNode.
void NetworKit::Graph::setCoordinate ( node  v,
Point< float >  value 
)
inline

DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes.

Sets the coordinate of v to value.

Parameters
vNode.
valueThe coordinate of v.
void NetworKit::Graph::setName ( std::string  name)
inline

Set name of graph to name.

Parameters
nameThe name.
void NetworKit::Graph::setWeight ( node  u,
node  v,
edgeweight  ew 
)

Set the weight of an edge.

If the edge does not exist, it will be inserted.

Parameters
[in]uendpoint of edge
[in]vendpoint of edge
[in]weightedge weight
void NetworKit::Graph::shrinkToFit ( )

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.

std::pair<count, count> const NetworKit::Graph::size ( ) const
inline
Returns
a pair (n, m) where n is the number of nodes and m is the number of edges
void NetworKit::Graph::sortEdges ( )

Sorts the adjacency arrays by node id.

While the running time is linear this temporarily duplicates the memory.

Graph NetworKit::Graph::subgraphFromNodes ( const std::unordered_set< node > &  nodes) const
void NetworKit::Graph::swapEdge ( NetworKit::node  s1,
NetworKit::node  t1,
NetworKit::node  s2,
NetworKit::node  t2 
)

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.

Parameters
s1The first source
t1The first target
s2The second source
t2The second target
count NetworKit::Graph::time ( )
inline

Get time step counter.

Returns
Time step counter.
void NetworKit::Graph::timeStep ( )
inline

Trigger a time step - increments counter.

std::string NetworKit::Graph::toString ( ) const

Returns a string representation of the graph.

Returns
A string representation.
edgeweight NetworKit::Graph::totalEdgeWeight ( ) const

Returns the sum of all edge weights.

SUMS.

Returns
The sum of all edge weights.
Graph NetworKit::Graph::toUndirected ( ) const

Return an undirected version of this graph.

Returns
undirected graph.
Graph NetworKit::Graph::toUnweighted ( ) const

Return an unweighted version of this graph.

Returns
unweighted graph.
Graph NetworKit::Graph::transpose ( ) const

Return the transpose of this graph.

The graph must be directed.

Returns
transpose of the graph.
std::string NetworKit::Graph::typ ( ) const

Return the type of the graph.

GRAPH INFORMATION.

Graph: not weighted, undirected WeightedGraph: weighted, undirected DirectedGraph: not weighted, directed WeightedDirectedGraph: weighted, directed

index NetworKit::Graph::upperEdgeIdBound ( ) const
inline

Get an upper bound for the edge ids in the graph.

Returns
An upper bound for the edge ids.
index NetworKit::Graph::upperNodeIdBound ( ) const
inline

Get an upper bound for the node ids in the graph.

Returns
An upper bound for the node ids.
edgeweight NetworKit::Graph::volume ( node  v) const

Returns the volume of the v, which is the weighted degree with self-loops counted twice.

Parameters
vNode.
Returns
The volume of the v.
edgeweight NetworKit::Graph::weight ( node  u,
node  v 
) const

Return edge weight of edge {u,v}.

EDGE ATTRIBUTES.

Returns 0 if edge does not exist. BEWARE: Running time is (deg(u))!

Parameters
uEndpoint of edge.
vEndpoint of edge.
Returns
Edge weight of edge {u,v} or 0 if edge does not exist.
edgeweight NetworKit::Graph::weightedDegree ( node  v) const

Returns the weighted degree of v.

NODE PROPERTIES.

Parameters
vNode.
Returns
Weighted degree of v.
Note
For directed graphs this is the sum of weights of all outgoing edges of v.

Friends And Related Function Documentation

friend class GraphBuilder
friend
friend class ParallelPartitionCoarsening
friend

The documentation for this class was generated from the following files: