Common Graph Operations¶

Many common graph operations map to simple operators in graphi. Unless parameters are needed, builtin operations usually suffice. For example, the outdegree of a node is simply its number of outgoing edges, i.e.

out_degree = len(graph[node])

in a directed graph. Since graphi makes heavy use of data views (instead of copies), this has optimal performance.

Pythonic Graph Operations¶

Nodes of a graph¶

Graphs behave like a set with regard to nodes. Note that removing a node also invalidates all its edges and their values.

graph[a] = True
graph.add(a)
graph.discard(a): Safely add or remove a node a from graph.

del graph[a]: Remove a node a from graph.

a in graph: Whether there is a node a in graph.

list(graph)
iter(graph)
for a in graph:: List/iterate/traverse all nodes in graph .

len(graph): The number of nodes in the graph.

Edges and values of a graph¶

Graphs special-case edges: an edge is a secondary key, being the value to nodes and the key to edge values.

Edge[a:b] in graph: Whether there is an edge from node a to node b in graph.

Loop[a] in graph
Edge[a:a] in graph: Whether there is a loop from node a to itself in graph.

list(graph[a])
iter(graph[a])
for b in graph[a]:: List/iterate/loop all nodes for which there is an edge from node a, i.e. its neighbours.

len(graph[a]): The number of outgoing edges of node a, i.e. its outdegree.

Edge values of a graph¶

Graphs behave similar to a dict, tying values to edges. Note that removing a node also invalidates all its edges and their values.

graph[a:b] = w
graph[Edge[a:b]] = w: Add an edge from node a to node b with value w.

Pythonic Graph Types¶

By default, every graph is a weighted, directed graph - edges are oriented from start to end node and have one edge value. However, other graph types can be created with standard language features.

graph[a:b] = True

Add an edge from node a to node b with the primitive value True.

This creates an unweighted graph edge.

graph[a:b] = [w1, w2, w3, ...]

graph[a:b] = w1, w2, w3, ...

Add an edge from node a to node b with multiple values w1, w2, w3, ....

This creates a multigraph edge.

graph[a:b] = graph[b:a] = w

Add edges from node a to node b and from node b to node a with the identical value w.

This creates an undirected graph edge.

Abstract Graph operations¶

The common abstract Graph Operations interface can be mapped to graphi almost directly. Most operations map to container accesses via [item], and an edge is represented as x:y.

Graphi	Abstract Graph Operation
`G.add(x)`	`add_vertex(G, x)`	adds the node `x`
`G.discard(x)`	`remove_vertex(G, x)`	removes the node `x`
`del G[x]`	N/A	…, but raises `NodeError` if there is no node `x`
`G.add(Edge[x:y])`	`add_edge(G, x, y)`	adds an edge from node `x` to node `y`
`G.discard(Edge[x:y])`	`remove_edge(G, x, y)`	removes the edge from node `x` to node `y`
`del G[x:y]`	N/A	…, but raises `EdgeError` if there is no edge from node `x` to node `y`
`Edge[x:y] in G`	`adjacent(G, x, y)`	tests whether there is an edge from node `x` to node `y`
`G[x:y]`	N/A	raises `EdgeError` if there is no edge from node `x` to node `y`
`list(G[x])`	`neighbors(G, x)`	lists all nodes `y` with an edge from node `x` to node `y`
N/A	`get_vertex_value(G, x)`	returns the value associated with node `x`
N/A	`set_vertex_value(G, x, v)`	sets the value associated with node `x` to `v`
`G[x:y]`	`get_edge_value(G, x, y)`	returns the value associated with the edge `x:y`
`G[x:y] = w`	`set_edge_value(G, x, y, v)`	sets the value associated with the edge `x:y` to `v`

Note that there is no concept for associating a value to a node in a graph - for a node x, G[x] is the adjacency list. Instead, use a separate dict to assign external values to nodes, or set values directly on nodes.