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