# Basic Graphs

Graphite provides two types for graphs: `UGraph`

for undirected graphs and
`DGraph`

for directed graphs.

Lets represent some graphs.

## Undirected graphs

```
myGraph :: UGraph Int ()
myGraph = fromEdgesList
[ 1 <-> 4
, 1 <-> 5
, 1 <-> 9
, 2 <-> 4
, 2 <-> 6
, 3 <-> 5
, 3 <-> 8
, 3 <-> 10
, 4 <-> 5
, 4 <-> 10
, 5 <-> 8
, 6 <-> 8
, 6 <-> 9
, 7 <-> 8
]
```

The type `UGraph Int ()`

here means that this is an undirected graph
UGraph,
with vertices of type `Int`

and edges with attributes of type `()`

, that is,
edges with no attributes on them.

The `<->`

operator constructs an *Undirected*
Edge
between two vertices.

The `fromEdgesList`

function constructs an `UGraph`

from a list of `Edge`

s.

## Directed Graphs

```
myGraph :: DGraph Int ()
myGraph = fromArcsList
[ 1 --> 4
, 1 --> 5
, 1 --> 9
, 2 --> 4
, 2 --> 6
, 3 --> 5
, 3 --> 8
, 3 --> 10
, 4 --> 5
, 4 --> 10
, 5 --> 8
, 6 --> 8
, 6 --> 9
, 7 --> 8
]
```

The type `DGraph Int ()`

here means that this is a directed graph
DGraph,
with vertices of type `Int`

and edges with attributes of type `()`

, that is,
edges with no attributes on them.

The `-->`

operator constructs a *Directed* edge (a.k.a. an
Arc)
between to vertices.

The `fromArcsList`

function constructs a `DGraph`

from a list of `Arc`

s.

## Other vertex types

Graphite can use any
Hashable
type as the vertices of a graph, this way we could have a graph of `Int`

s,
`Float`

s, `Bool`

s, `Char`

s, `String`

s, `ByteString`

s, `Text`

and more.

Take for instance this undirected graph with `Float`

vertices (parenthesis for
clarity):

```
myGraph :: UGraph Float ()
myGraph = fromEdgesList [(1.3 <-> 2.5), (3.4 <-> 6.8), (2.5 <-> 4.4)]
```

Or this directed graph with `String`

vertices:

```
myGraph :: DGraph String ()
myGraph = fromArcsList ["Paper" --> "Rock", "Rock" --> "Scissors", "Scissors" -> "Paper"]
```

## Edges with attributes

By using the `<->`

and `-->`

constructors, the resulting `Edge`

s and `Arc`

s have
attributes of type `()`

. If we need edges with some attributes like weights or
labels for example, we could use the `Edge`

and `Arc`

data constructors
directly.

Lets build a graph of cities and the distances in kilometers between them:

```
cities :: UGraph String Int
cities = fromEdgesList
[ Edge "Paper Town" "Springfield" 30
, Edge "Springfield" "Lazy Town" 120
, Edge "Paper Town" "Vice City" 85
, Edge "Vice City" "Atlantis" 145
, Edge "Atlantis" "Springfield" 73
, Edge "Lazy Town" "Vice City" 122
, Edge "Lazy Town" "Paper Town" 24
]
```

If the roads between those cities are one way only, we should use *Arcs* instead
of *Edges* and form a directed graph like so:

```
cities :: DGraph String Int
cities = fromArcsList
[ Arc "Paper Town" "Springfield" 30
, Arc "Springfield" "Lazy Town" 120
, Arc "Paper Town" "Vice City" 85
, Arc "Vice City" "Atlantis" 145
, Arc "Atlantis" "Springfield" 73
, Arc "Lazy Town" "Vice City" 122
, Arc "Lazy Town" "Paper Town" 24
]
```

The edge's attributes can be of any type, so we could for instance label them
by using `String`

:

```
myGraph :: DGraph String String
myGraph = fromArcsList
[ Arc "Paper" "Rock" "Cover"
, Arc "Rock" "Scissors" "Crush"
, Arc "Scissors" "Paper" "Cut"
]
```

# Complex graphs - complex vertices, complex edges

Remember that graphite can use any `Hashable`

data type as vertices, so we could
define our own data types, make them instances of `Hashable`

and use them as
vertices.

Edge attributes on the other hand have no restriction and can be of any type; Though some functions will require the attributes to be instances of the Weighted or Labeled type classes if the nature of the algorithm requires it (like when computing shortest paths).

Lets try this out. First define some data types:

```
{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics (Generic)
import Data.Hashable
-- Data type for vertices
data Element
= Paper
| Rock
| Scissors
deriving (Show, Ord, Eq, Generic)
instance Hashable Element
-- Data type for edge attributes
data Action
= Cover
| Crush
| Cut
deriving (Show, Ord, Eq)
```

Although we could define `Hashable`

instances manually, here we go for the
automatic generation of instances by leveraging `Generic`

.

Now define a graph with vertices of type *Element* and edge attributes of type
*Action*:

```
myGraph :: DGraph Element Action
myGraph = fromArcsList
[ Arc Paper Rock Cover
, Arc Rock Scissors Crush
, Arc Scissors Paper Cut
]
```

## Record vertices

By using the same approach it's possible to define data types with record syntax like so:

```
{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics (Generic)
import Data.Hashable
data City = City
{ name :: String
, major :: String
, population :: Int
} deriving (Show, Ord, Eq, Generic)
instance Hashable City
```

Write a couple instances:

```
lazyTown, springfield, southPark :: City
lazyTown = City "Lazy Town" "Milford Meanswell" 12
springfield = City "Springfield" "Joe Quimby" 30720
southPark = City "South Park, Colorado" "McDaniels" 2540
```

And finally use them in a graph:

```
cities :: UGraph City ()
cities = fromEdgesList
[ lazyTown <-> springfield
, springfield <-> southPark
, southPark <-> lazyTown
]
```

# Working with graph-type independence

When the type of the graph (directed/undirected) is irrelevant, the Graph type class provides a graph-type polymorphic API to work with.

In the graph-type generic interface you work with *tuples* and *triples* to
represent edges, as opposed to the `Edge`

and `Arc`

types of the graph-type
specific interfaces.

**Tuples** represent edges (directed or undirected, depending on the concrete
graph type) with attributes of type *unit* `()`

.

The following are graphs with edges defined as tuples and with attributes of
type `()`

(note how we insert edges described as the vertices they connect to
the `empty`

graph) :

```
someUndirectedGraph :: UGraph Int ()
someUndirectedGraph = insertEdgePairs [(1, 2), (2, 3), (3, 1)] empty
```

```
someDirectedGraph :: DGraph Int ()
someDirectedGraph = insertEdgePairs [(1, 2), (2, 3), (3, 1)] empty
```

**Triples** represent edges (directed or undirected, depending on the concrete
graph type) where the third element is the edge attribute.

The following are graphs with edges defined as triples and with attributes of
type `String`

:

```
someUndirectedGraph :: UGraph Int String
someUndirectedGraph = insertEdgeTriples [(1, 2, "A"), (2, 3, "B"), (3, 1, "C")] empty
```

```
someDirectedGraph :: DGraph Int String
someDirectedGraph = insertEdgeTriples [(1, 2, "A"), (2, 3, "B"), (3, 1, "C")] empty
```