networkit.graph.
Graph
An undirected graph (with optional weights) and parallel iterator methods.
Graph(n=0, weighted=False, directed=False)
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.
BFSEdgesFrom
(self, node start, callback)Experimental BFS search interface that passes edges that are part of the BFS tree to the callback
BFSfrom
(self, start, callback)Experimental BFS search interface
DFSEdgesFrom
(self, node start, callback)Experimental DFS search interface that passes edges that are part of the DFS tree to the callback
DFSfrom
(self, node start, callback)Experimental DFS search interface
addEdge
(self, u, v, w=1.0)Insert an undirected 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. Caution: It is not checked whether this edge already exists, thus it is possible to create multi-edges.
addNode
(self)Add a new node to the graph and return it.
append
(self, Graph G)Appends another graph to this graph as a new subgraph. Performs node id remapping.
G : Graph
checkConsistency
(self)Check for invalid graph states, such as multi-edges.
compactEdges
(self)Compact the edge storage, this should be called after executing many edge deletions.
copyNodes
(self)Copies all nodes to a new graph
degree
(self, u)Get the number of neighbors of v.
degreeIn
(self, u)degreeOut
(self, u)density
(self)Get the density of the graph.
double
edgeId
(self, node u, node v)edges
(self)Get list of edges as node pairs.
forEdges
(self, callback)Experimental edge iterator interface
forEdgesOf
(self, node u, callback)Experimental incident (outgoing) edge iterator interface
forInEdgesOf
(self, node u, callback)Experimental incident incoming edge iterator interface
forNodePairs
(self, callback)Experimental node pair iterator interface
forNodes
(self, callback)Experimental node iterator interface
forNodesInRandomOrder
(self, callback)Experimental node iterator interface
getCoordinate
(self, v)Get the coordinates of node v. Parameters ———- v : node
Node.
getName
(self)Get the name of the graph.
hasEdge
(self, u, v)Checks if undirected edge {u,`v`} exists in the graph.
hasEdgeIds
(self)Returns true if edges have been indexed
hasNode
(self, u)Checks if the Graph has the node u, i.e. if u hasn’t been deleted and is in the range of valid ids.
increaseWeight
(self, u, v, w)Increase the weight of an edge. If the edge does not exist, it will be inserted.
indexEdges
(self, bool force=False)Assign integer ids to edges.
initCoordinates
(self)isDirected
(self)isIsolated
(self, u)If the node u is isolated
isWeighted
(self)merge
(self, Graph G)G : Graph
neighbors
(self, u)Get list of neighbors of u.
nodes
(self)Get list of all nodes.
numberOfEdges
(self)Get the number of edges in the graph.
numberOfNodes
(self)Get the number of nodes in the graph.
numberOfSelfLoops
(self)Get number of self-loops, i.e. edges {v, v}. Returns ——- count
number of self-loops.
randomEdge
(self, bool uniformDistribution=False)Get a random edge of the graph.
Fast, but not uniformly random if uniformDistribution is not set, slow and uniformly random otherwise.
randomEdges
(self, count numEdges)Returns a list with numEdges random edges. The edges are chosen uniformly at random.
randomNeighbor
(self, u)Get a random neighbor of v and none if degree is zero.
randomNode
(self)Get a random node of the graph.
removeEdge
(self, u, v)Removes the undirected edge {u,`v`}.
removeNode
(self, u)Remove a node v and all incident edges from the graph.
Incoming as well as outgoing edges will be removed.
removeSelfLoops
(self)Removes all self-loops from the graph.
restoreNode
(self, u)Restores a previously deleted node u with its previous id in the graph.
setCoordinate
(self, v, value)Set the coordinates of node v. Parameters ———- v : node
Node.
setName
(self, name)Set name of graph to name.
setWeight
(self, u, v, w)Set the weight of an edge. If the edge does not exist, it will be inserted.
size
(self)Get the size of the graph.
sortEdges
(self)Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.
subgraphFromNodes
(self, nodes)Create a subgraph induced by the set nodes.
The returned graph G’ is isomorphic (structurally identical) to the subgraph in G, but node indices are not preserved.
swapEdge
(self, node s1, node t1, node s2, node t2)Changes the edge (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.
toString
(self)Get a string representation of the graph.
toUndirected
(self)Return an undirected version of this graph.
undirected graph.
toUnweighted
(self)Return an unweighted version of this graph.
graph.
totalEdgeWeight
(self)Get the sum of all edge weights.
transpose
(self)Return the transpose of this (directed) graph.
directed graph.
upperEdgeIdBound
(self)Get an upper bound for the edge ids in the graph
upperNodeIdBound
(self)Get an upper bound for the node ids in the graph
weight
(self, u, v)Get edge weight of edge {u , v}. Returns 0 if edge does not exist.
weightedDegree
(self, v)Returns the weighted degree of v.
For directed graphs this is the sum of weights of all outgoing edges of v.
networkit.graph.
GraphTools
getCompactedGraph
(Graph graph, nodeIdMap)Computes a graph with the same structure but with continuous node ids.
getContinuousNodeIds
(Graph graph)Computes a map of node ids to continuous node ids.
getRandomContinuousNodeIds
(Graph graph)Computes a map of node ids to continuous, randomly permutated node ids.
networkit.graph.
RandomMaximumSpanningForest
Computes a random maximum-weight spanning forest using Kruskal’s algorithm by randomizing the order of edges of the same weight.
getAttribute
(self, bool move=False)Get a boolean attribute that indicates for each edge if it is part of the calculated maximum-weight spanning forest.
This attribute is only calculated and can thus only be request if the supplied graph has edge ids.
getMSF
(self, bool move=False)Gets the calculated maximum-weight spanning forest as graph.
inMSF
(self, node u, node v=_none)Checks if the edge (u, v) or the edge with id u is part of the calculated maximum-weight spanning forest.
networkit.graph.
SpanningForest
Generates a spanning forest for a given graph
generate
(self)networkit.graph.
UnionMaximumSpanningForest
Union maximum-weight spanning forest algorithm, computes the union of all maximum-weight spanning forests using Kruskal’s algorithm.
getAttribute
(self, bool move=False)Get a boolean attribute that indicates for each edge if it is part of any maximum-weight spanning forest.
This attribute is only calculated and can thus only be request if the supplied graph has edge ids.
getUMSF
(self, bool move=False)Gets the union of all maximum-weight spanning forests as graph.
inUMST
(self, node u, node v=_none)Checks if the edge (u, v) or the edge with id u is part of any maximum-weight spanning forest.