Copyright | Copyright (C) 2023 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Supporting definitions for graph problems.

## Synopsis

- class Graph g where
- type Vertex = Int
- newtype Edge = Edge (Vertex, Vertex)
- data Var a = Var a [Var a]
- newtype Lists = Lists ([Vertex], [(Vertex, Vertex)])
- newtype Adjacency = Adjacency [(Vertex, [Vertex])]
- newtype Paths = Paths [[Vertex]]
- newtype G = G (Map Vertex (Set Vertex))
- areValidGraphSets :: (Set Vertex, Set Edge) -> Bool

# Documentation

A graph is mathematically defined as a set of vertexes and a set of edges, where an edge is a set of two elements from the set of vertexes. I.e., if \(G = (V, E)\), where \(E \subseteq \{ \{v_1, v_2\} \,|\, v_1 \in V, v_2 \in V\}\), then \(G\) is a graph.

The following is an example of a graph, with vertexes represented as circles and edges represented as lines.

### Notes

This introduction to graphs is substantially different from the one in the original list of Ninety-Nine Haskell Problems. The original introduction would serve as an introduction to graphs in the context of Prolog, but apparently was not updated to be more appropriate for other languages as the problems were ported for Lisp and then Haskell.

This is a rewrite targeted to be more useful towards practicing Haskell. Most of the graph problems themselves remain substantially the same.

vertexes :: g -> Set Vertex Source #

The set of vertexes.

edges :: g -> Set Edge Source #

The set of edges.

sets :: g -> (Set Vertex, Set Edge) Source #

neighbors :: Vertex -> g -> Set Vertex Source #

The neighbors of a vertex in a graph. I.e., the set of vertexes adjacent to the given vertex.

adjacent :: Vertex -> Vertex -> g -> Bool Source #

Whether the given vertexes are adjacent in the graph.

toGraph :: (Set Vertex, Set Edge) -> Maybe g Source #

Build a graph of type `g`

, given a set of vertexes and a set of edges.

If the sets are not consistent with a valid graph, return `Nothing`

.

isValidGraph :: g -> Bool Source #

Whether the graph representation is valid.

If graph representations can only be built using `toGraph`

,
it should be impossible to build an invalid graph representation.
However, we allow graph representations to be built directly,
so for some representations of graphs, it is possible to build an invalid one.

#### Instances

A vertex in a graph.

In general, vertexes can be anything. For these problems, vertexes will be integers.

An edge in a graph.

We will only deal with *undirected* graphs. I.e.,

Edge (u, v) == Edge (v, u)

There are many ways to represent graphs in Haskell. For example, the example graph can be represented by variables including their adjacent vertexes as values:

`>>>`

let v1 = Var () [v2, v4] v2 = Var () [v1, v3, v4] v3 = Var () [v2, v4] v4 = Var () [v1, v2, v3, v5] v5 = Var () [v4] :}`:{`

We will not be using this representation of graphs further.

### Tying the knot

While many languages can repesent cycles in graphs with objects pointing or referencing each other,
most of them cannot do so by *value* if there are any cycles.
This is possible in Haskell thanks to lazy evaluation,
and this technique is called "tying the knot".

However, tying the knot to represent graphs with cycles can be problematic. It is equivalent to and indistinguishable from an infinite multiway tree. This can be resolved by assuming that values with the same label are the same vertex. Unfortunately, this allows for an inconsistent graph representation, and there is no general way to confirm that a graph representation is consistent.

For example, there are no graphs consistent with the following representation:

`>>>`

let v1 = Var 1 [v2] v2 = Var 2 [v3] v3 = Var 3 [v1'] v1' = Var 1 [v3] :}`:{`

On the other hand, the following is a consistent representation of a graph. Unfortunately, it cannot be proven that it is consistent using just the values.

`>>>`

let v1 = Var 1 [v2] v2 = Var 2 [v1] :}`:{`

If there are no cycles in the graph, there is no need to tie the knot, so this is not an issue. In fact, trees are graphs which are often represented this way.

Graphs can also be represented by the lists of its vertexes and edges. This is close to the standard mathematical definition of a graph.

For example, the example graph can be represented as:

`>>>`

Lists ...`Lists ([1, 2, 3, 4, 5], [(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5)])`

#### Instances

Generic Lists Source # | |

Show Lists Source # | |

NFData Lists Source # | |

Defined in Problems.Graphs | |

Eq Lists Source # | |

Graph Lists Source # | |

Defined in Problems.Graphs vertexes :: Lists -> Set Vertex Source # edges :: Lists -> Set Edge Source # sets :: Lists -> (Set Vertex, Set Edge) Source # neighbors :: Vertex -> Lists -> Set Vertex Source # adjacent :: Vertex -> Vertex -> Lists -> Bool Source # toGraph :: (Set Vertex, Set Edge) -> Maybe Lists Source # isValidGraph :: Lists -> Bool Source # | |

ConvertibleGraph Lists Source # | |

ConvertibleGraph Lists Source # | |

type Rep Lists Source # | |

Defined in Problems.Graphs |

A common approach to representing graphs are with *adjacency lists*.
As the name implies, for each vertex it lists its adjacent vertexes

For example, the example graph can be represented as:

`>>>`

Adjacency ...`Adjacency [(1, [2, 4]), (2, [1, 3, 4]), (3, [2, 4]), (4, [1, 2, 3, 5]), (5, [4])]`

#### Instances

Generic Adjacency Source # | |

Show Adjacency Source # | |

NFData Adjacency Source # | |

Defined in Problems.Graphs | |

Eq Adjacency Source # | |

Graph Adjacency Source # | |

Defined in Problems.Graphs vertexes :: Adjacency -> Set Vertex Source # edges :: Adjacency -> Set Edge Source # sets :: Adjacency -> (Set Vertex, Set Edge) Source # neighbors :: Vertex -> Adjacency -> Set Vertex Source # adjacent :: Vertex -> Vertex -> Adjacency -> Bool Source # toGraph :: (Set Vertex, Set Edge) -> Maybe Adjacency Source # isValidGraph :: Adjacency -> Bool Source # | |

ConvertibleGraph Adjacency Source # | |

ConvertibleGraph Adjacency Source # | |

type Rep Adjacency Source # | |

Defined in Problems.Graphs |

The previous approaches can be verbose and error-prone for humans to use.

An easier way for humans is to use paths of vertexes to represent both the vertexes and edges.
Within a path is implicitly an edge between consecutive vertexes.
E.g., a path `[a, b, c, ...]`

means there are vertexes `a`

, `b`

, `c`

, ... and edges `(a, b)`

, `(b, c)`

, ...
There will be as many paths as required to represent all edges in the graph.

For example, the example graph can be represented as:

`>>>`

Paths ...`Paths [[1, 2, 3, 4, 5], [1, 4], [2, 4]]`

### DOT graphs

This is similar to the approach used by DOT graphs, which are commonly used to generate visualizations of graphs. E.g., the example graph can be written in DOT as:

graph { 1 -- 2 -- 3 -- 4 -- 5 1 -- 4 2 -- 4 }

#### Instances

Generic Paths Source # | |

Show Paths Source # | |

NFData Paths Source # | |

Defined in Problems.Graphs | |

Eq Paths Source # | |

Graph Paths Source # | |

Defined in Problems.Graphs vertexes :: Paths -> Set Vertex Source # edges :: Paths -> Set Edge Source # sets :: Paths -> (Set Vertex, Set Edge) Source # neighbors :: Vertex -> Paths -> Set Vertex Source # adjacent :: Vertex -> Vertex -> Paths -> Bool Source # toGraph :: (Set Vertex, Set Edge) -> Maybe Paths Source # isValidGraph :: Paths -> Bool Source # | |

ConvertibleGraph Paths Source # | |

ConvertibleGraph Paths Source # | |

type Rep Paths Source # | |

Defined in Problems.Graphs |

Represents a graph with a map where a vertex is a key and the set of its neighbors is the value.

This is basically an indexed version of adjacency lists. This representation may be the easiest for graph functions to use, and we will use it as the default representation of graphs.

For example, the example graph can be represented as:

`>>>`

G $ Map.map Set.fromList $ Map.fromList [ (1, [2, 4]) , (2, [1, 3, 4]) , (3, [2, 4]) , (4, [1, 2, 3, 5]) , (5, [4]) ] :} G ...`:{`