# Undirected Graphs

Data structures capture relationship between the component values such as succession or relative magnitude. Graphs data structure is a very general representation of binary relations recorded as edges between a collection of vertices. There are many variations and extensions of graphs such as labelled vertices, labelled edges, root verities, multi-edges etc. However, in this article we will look at the most 'basic' graphs where component values are identified as vertices.

Let is therefore construct a 'universal' type-class specification for graphs. The type-class should allow us to: construct and modify the graph by adding and deleting vertices and edges.

The class polymorphic `graph` function combines additions to form graphs from lists? How? That's simple. The `uncurry` takes a function `(a -> b -> c) -> (a, b) -> c`.

## List Representation

Just like with other data types we have talked in this series, let's begin by seeing how graphs can be represented as list. Mathematically, a graph is a set of vertices V and a set of edges E. Edges are represented as an unordered pairs (V, V). Let us there define the data type `VEListsGraph` which will have a list of those same properties:

The first list is the V set and the pair represents the edges. At this point, it is worth imposing some invariants on this data structure so that when e.g. vertex is deleted, we do not have edges leading to or from it:

1. This reads: for all edges `(v1,v2)`, both `v1` and `v2` must be members of vertex set
2. this enforces the symmetry in the graph i.e. if there is an edge coming from `v1` to `v2` then there must also be a vortex from `v2` to `v1`
3. Both `vs` and `es` are strictly ordered.
The `empty` function simply creates an empty graph, no magic here at all. `addVert` is a little more complicated. Here
is insertion into an ordered list. Finally we have `addEdge` which is highly problematic as the insert function to be called 4 times! `delete` can be implemented in a similar way:
Again, to maintain the invariant (1) deleting a vertex involves deleting all edges incident to it. This 'multiple edge' deletion could be quite costly. The list comprehension allows us to do it in linear time (with reasonably low constant).

The `vertices` function which returns a list of all the vertices in the graph is almost free since the vertices are stored as a list. Finally, in order to get all the elements adjecient to a particular vertex `v` we use `adj` function. This one runs in O(n) where n is the number of edges. There is a little bit of filtering going on in this function. `es'` contains a list of all edges which have `v` as their first element. To make this a little bit faster we mentioned at the beginning that the set will be strictly ordered. This means that we can firstly drop the first 'half' of elements which are strictly smaller than the value we are looking for (remember that `v` has `Ord` class type). This can be done through binary search rather than linearly. Then we take all the elements which are equal to the value `v` using `takeWhile`.

For a persistence and dynamic graph data structure, O(1) is unrealistic, but we could bring it down to O(log m) where is is the number of vertices.

We just saw that representing graphs using lists is not a great idea because the operations such as addition, deletion and getting neighbours are quite expensive. One solution around this problem is to use nested adjacency sets. They are a vertex-index table of linked lists of neighbours. Now, we don't have the access to 'tables' as it would defite the point of a purely functional data structure. Instead, we are going to use sets (which we already covered). Those sets will be used for both inner and outer collection. Let us define the data type first: `Graph` is our graph. It is made of a set which contains another adjacency set.
This is when it gets slightly tricky, how can the `adj` function find an `A v vs` element in a graph's adjacency set, when all it has is `v`? The simplest solution is to declare custom `Ord` and `Eq` instances for `Adj a` that ignore the neighbours.