Problems.Graphs

Description

Supporting definitions for graph problems.

Synopsis

# Documentation

class Graph g where Source #

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

Expand

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.

Minimal complete definition

Methods

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 #

The sets of vertexes and edges for a graph. I.e., (vertexes g, edges g).

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

Instances details
 Source # Instance detailsDefined in Problems.Graphs Methods Source # Instance detailsDefined in Problems.Graphs Methodssets :: G -> (Set Vertex, Set Edge) Source #adjacent :: Vertex -> Vertex -> G -> Bool Source #toGraph :: (Set Vertex, Set Edge) -> Maybe G Source # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Lists -> (Set Vertex, Set Edge) Source # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Paths -> (Set Vertex, Set Edge) Source #

type Vertex = Int Source #

A vertex in a graph.

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

newtype Edge Source #

An edge in a graph.

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

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

Constructors

 Edge (Vertex, Vertex)

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Edge -> ShowS #show :: Edge -> String #showList :: [Edge] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Edge -> Edge -> Bool #(/=) :: Edge -> Edge -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodscompare :: Edge -> Edge -> Ordering #(<) :: Edge -> Edge -> Bool #(<=) :: Edge -> Edge -> Bool #(>) :: Edge -> Edge -> Bool #(>=) :: Edge -> Edge -> Bool #max :: Edge -> Edge -> Edge #min :: Edge -> Edge -> Edge #

data Var a Source #

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

Expand

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.

Constructors

 Var a [Var a]

#### Instances

Instances details
 Show a => Show (Var a) Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Var a -> ShowS #show :: Var a -> String #showList :: [Var a] -> ShowS # Eq a => Eq (Var a) Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Var a -> Var a -> Bool #(/=) :: Var a -> Var a -> Bool #

newtype Lists Source #

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 ([1, 2, 3, 4, 5], [(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5)])
Lists ...


Constructors

 Lists ([Vertex], [(Vertex, Vertex)])

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep Lists :: Type -> Type # Methodsfrom :: Lists -> Rep Lists x #to :: Rep Lists x -> Lists # Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Lists -> ShowS #show :: Lists -> String #showList :: [Lists] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: Lists -> () # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Lists -> Lists -> Bool #(/=) :: Lists -> Lists -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Lists -> (Set Vertex, Set Edge) Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: Lists -> G Source # Source # Instance detailsDefined in Solutions.P80 MethodstoG :: Lists -> G Source # type Rep Lists Source # Instance detailsDefined in Problems.Graphs type Rep Lists = D1 ('MetaData "Lists" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "Lists" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 ([Vertex], [(Vertex, Vertex)]))))

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 [(1, [2, 4]), (2, [1, 3, 4]), (3, [2, 4]), (4, [1, 2, 3, 5]), (5, [4])]
Adjacency ...


Constructors

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep Adjacency :: Type -> Type # Methodsto :: Rep Adjacency x -> Adjacency # Source # Instance detailsDefined in Problems.Graphs MethodsshowList :: [Adjacency] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: Adjacency -> () # Source # Instance detailsDefined in Problems.Graphs Methods Source # Instance detailsDefined in Problems.Graphs Methods Source # Instance detailsDefined in Problems.P80 Methods Source # Instance detailsDefined in Solutions.P80 Methods type Rep Adjacency Source # Instance detailsDefined in Problems.Graphs type Rep Adjacency = D1 ('MetaData "Adjacency" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "Adjacency" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [(Vertex, [Vertex])])))

newtype Paths Source #

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 [[1, 2, 3, 4, 5], [1, 4], [2, 4]]
Paths ...


### DOT graphs

Expand

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
}

Constructors

 Paths [[Vertex]]

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep Paths :: Type -> Type # Methodsfrom :: Paths -> Rep Paths x #to :: Rep Paths x -> Paths # Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Paths -> ShowS #show :: Paths -> String #showList :: [Paths] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: Paths -> () # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Paths -> Paths -> Bool #(/=) :: Paths -> Paths -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Paths -> (Set Vertex, Set Edge) Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: Paths -> G Source # Source # Instance detailsDefined in Solutions.P80 MethodstoG :: Paths -> G Source # type Rep Paths Source # Instance detailsDefined in Problems.Graphs type Rep Paths = D1 ('MetaData "Paths" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "Paths" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [[Vertex]])))

newtype G Source #

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


Constructors

 G (Map Vertex (Set Vertex))

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep G :: Type -> Type # Methodsfrom :: G -> Rep G x #to :: Rep G x -> G # Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> G -> ShowS #show :: G -> String #showList :: [G] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: G -> () # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: G -> G -> Bool #(/=) :: G -> G -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodssets :: G -> (Set Vertex, Set Edge) Source #adjacent :: Vertex -> Vertex -> G -> Bool Source #toGraph :: (Set Vertex, Set Edge) -> Maybe G Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: G -> G Source # Source # Instance detailsDefined in Solutions.P80 MethodstoG :: G -> G Source # type Rep G Source # Instance detailsDefined in Problems.Graphs type Rep G = D1 ('MetaData "G" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "G" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map Vertex (Set Vertex)))))

Checks whether the given set of vertexes and edges can form a graph.

I.e., the vertexes in edges must be in the set of vertexes.