Maintainer | Ivan.Miljenovic@gmail.com |
---|

Planar graphs are graphs that can be embedded onto a surface (i.e. they can be drawn on that surface without any edges crossing). As such, it is preferable to use a dedicated data structure for them that has information about how to achieve this embedding rather than a standard graph data structure.

The implementation here is loosely based upon that found in
*plantri* by Gunnar Brinkmann and Brendan McKay:
http://cs.anu.edu.au/~bdm/plantri/. The main differences are (if my
understanding of the C code is correct):

- plantri uses arrays; planar-graph uses Maps (thus making it easier to grow/shrink graphs).
- plantri doesn't store the list of edges around a node.
- Each edge stores in plantri has the face it is on, but only after
they are explicitly calculated. In planar-graph,
`getFaces`

instead returns a Map for the faces. - plantri doesn't allow labels.

In particular, all edges - even undirected ones - are stored as two
opposing directed edges. As such, care should be taken when dealing
with edges. Also, the `Node`

, `Edge`

and `Face`

identifiers are all
abstract, and as such cannot be constructed directly.

All returned `CList`

s represent values in a clockwise fashion
(relative to the `Node`

or `Face`

in question).

- data PlanarGraph n e
- data Node
- order :: PlanarGraph n e -> Int
- nodes :: PlanarGraph n e -> [Node]
- labNodes :: PlanarGraph n e -> [(Node, n)]
- outgoingEdges :: PlanarGraph n e -> Node -> CList Edge
- incomingEdges :: PlanarGraph n e -> Node -> CList Edge
- neighbours :: PlanarGraph n e -> Node -> CList Node
- nodeLabel :: PlanarGraph n e -> Node -> n
- data Edge
- size :: PlanarGraph n e -> Int
- edges :: PlanarGraph n e -> [Edge]
- labEdges :: PlanarGraph n e -> [(Edge, e)]
- edgesBetween :: PlanarGraph n e -> [(Node, Node)]
- labEdgesBetween :: PlanarGraph n e -> [((Node, Node), e)]
- fromNode :: PlanarGraph n e -> Edge -> Node
- toNode :: PlanarGraph n e -> Edge -> Node
- prevEdge :: PlanarGraph n e -> Edge -> Edge
- nextEdge :: PlanarGraph n e -> Edge -> Edge
- inverseEdge :: PlanarGraph n e -> Edge -> Edge
- edgeLabel :: PlanarGraph n e -> Edge -> e
- mergeGraphs :: PlanarGraph n e -> PlanarGraph n e -> (PlanarGraph n e, Node -> Node, Edge -> Edge)
- empty :: PlanarGraph n e
- addNode :: n -> PlanarGraph n e -> (Node, PlanarGraph n e)
- addUNode :: Monoid n => PlanarGraph n e -> (Node, PlanarGraph n e)
- data EdgePos
- = Anywhere
- | BeforeEdge Edge
- | AfterEdge Edge

- addEdge :: Node -> EdgePos -> Node -> EdgePos -> e -> e -> PlanarGraph n e -> ((Edge, Edge), PlanarGraph n e)
- addEdgeUndirected :: Node -> EdgePos -> Node -> EdgePos -> e -> PlanarGraph n e -> (Edge, PlanarGraph n e)
- addUEdge :: Monoid e => Node -> EdgePos -> Node -> EdgePos -> PlanarGraph n e -> ((Edge, Edge), PlanarGraph n e)
- isEmpty :: PlanarGraph n e -> Bool
- deleteNode :: Node -> PlanarGraph n e -> PlanarGraph n e
- deleteEdge :: Edge -> PlanarGraph n e -> PlanarGraph n e
- contractEdge :: Edge -> (n -> n -> n) -> PlanarGraph n e -> PlanarGraph n e
- mapNodes :: (n -> n') -> PlanarGraph n e -> PlanarGraph n' e
- adjustNodeLabel :: (n -> n) -> Node -> PlanarGraph n e -> PlanarGraph n e
- setNodeLabel :: n -> Node -> PlanarGraph n e -> PlanarGraph n e
- mapEdges :: (e -> e') -> PlanarGraph n e -> PlanarGraph n e'
- adjustEdgeLabel :: (e -> e) -> Edge -> PlanarGraph n e -> PlanarGraph n e
- setEdgeLabel :: e -> Edge -> PlanarGraph n e -> PlanarGraph n e
- data Face
- type FaceMap = Map Face FaceInfo
- data FaceInfo = FInfo {}
- faceEdges :: FaceInfo -> CList Edge
- adjoiningFaces :: FaceInfo -> CList Face
- getFaces :: PlanarGraph n e -> FaceMap
- getFace :: PlanarGraph n e -> Edge -> ([Node], [Edge])
- makeDual :: PlanarGraph n e -> PlanarGraph () ()
- toDual :: (Face -> n) -> (Face -> Edge -> Face -> e) -> FaceMap -> PlanarGraph n e
- type SerialisedGraph n e = [(Int, n, [(Int, Int, e, Int)])]
- serialise :: PlanarGraph n e -> SerialisedGraph n e
- deserialise :: SerialisedGraph n e -> PlanarGraph n e
- prettify :: (Show n, Show e) => PlanarGraph n e -> String
- prettyPrint :: (Show n, Show e) => PlanarGraph n e -> IO ()

# Documentation

data PlanarGraph n e

The overall planar graph data structure.

Functor (PlanarGraph n) | |

(Eq n, Eq e) => Eq (PlanarGraph n e) | |

(Read n, Read e) => Read (PlanarGraph n e) | |

(Show n, Show e) => Show (PlanarGraph n e) |

# Graph Information

## Information about the nodes

data Node

An abstract representation of a node.

Bounded Node | |

Enum Node | |

Eq Node | |

Ord Node | |

Read Node | Note that this instance of |

Show Node | This instance of |

order :: PlanarGraph n e -> Int

The number of nodes in the graph.

nodes :: PlanarGraph n e -> [Node]

All the nodes in the graph (in some arbitrary order).

labNodes :: PlanarGraph n e -> [(Node, n)]

All the nodes and their labels in the graph (in some arbitrary order).

outgoingEdges :: PlanarGraph n e -> Node -> CList Edge

Returns all outgoing edges for the specified node, travelling clockwise around the node. It assumes the node is indeed in the graph.

incomingEdges :: PlanarGraph n e -> Node -> CList Edge

Returns all incoming edges for the specified node, travelling clockwise around the node. It assumes the node is indeed in the graph.

neighbours :: PlanarGraph n e -> Node -> CList Node

nodeLabel :: PlanarGraph n e -> Node -> n

Returns the label for the specified node.

## Information about the edges

To be able to embed the required order of edges around a particular
`Node`

, we can't rely on just having each node specify which other
nodes are adjacent to it as with non-planar graph types; instead, we
need a unique identifier (to be able to distinguish between multiple
edges between two nodes). Furthermore, each edge has an /inverse
edge/ in the opposite direction.

Due to every edge having an inverse, a `PlanarGraph`

implicitly
*undirected* even though each edge is directed. As such, if you
require a directed planar graph, use appropriate edge labels to denote
whether an edge is the one you want or just its inverse.

data Edge

An abstract representation of an edge. Note that an explicit identifier is used for each edge rather than just using the two nodes that the edge connects. This is required in case more than one edge connects two nodes as we need to be able to distinguish them.

Bounded Edge | |

Enum Edge | |

Eq Edge | |

Ord Edge | |

Read Edge | Note that this instance of |

Show Edge | This instance of |

size :: PlanarGraph n e -> Int

The number of edges in the graph.

edges :: PlanarGraph n e -> [Edge]

All the edges in the graph (in some arbitrary order). Note that inverses are also included.

labEdges :: PlanarGraph n e -> [(Edge, e)]

All the edges and their labels in the graph (in some arbitrary order).

edgesBetween :: PlanarGraph n e -> [(Node, Node)]

A variant of `edges`

that returns the pair of nodes that form an
edge rather than its unique identifier (again including inverse
edges).

labEdgesBetween :: PlanarGraph n e -> [((Node, Node), e)]

As with `edgesBetween`

, but including the labels.

inverseEdge :: PlanarGraph n e -> Edge -> Edge

The `Edge`

that is an inverse to this one; i.e.:

fromNode pg e == toNode pg $ inverseEdge pg e toNode pg e == fromNode pg $ inverseEdge pg e

edgeLabel :: PlanarGraph n e -> Edge -> e

Return the label for the specified edge.

# Graph Manipulation

mergeGraphs :: PlanarGraph n e -> PlanarGraph n e -> (PlanarGraph n e, Node -> Node, Edge -> Edge)

`mergeGraphs pg1 pg2`

creates a disjoint union between `pg1`

and
`pg2`

(i.e. puts them into the same graph but disconnected).
This is used when they were created independently and thus
probably have clashing `Node`

and `Edge`

values. For best
performance, `pg1`

should be larger than `pg2`

.

Along with the merged graph, two functions are returned: they
respectively convert Node and Edge values from `pg2`

to those
found in the merged graph.

## Graph Construction

empty :: PlanarGraph n e

Constructs an empty planar graph.

addNode :: n -> PlanarGraph n e -> (Node, PlanarGraph n e)

Add a node with the provided label to the graph, returning the updated graph and the node identifier.

addUNode :: Monoid n => PlanarGraph n e -> (Node, PlanarGraph n e)

data EdgePos

Specification of where to place a new edge on a node in clockwise order.

Anywhere | The new edge can be placed anywhere. |

BeforeEdge Edge | The new edge should be placed before the specified edge. |

AfterEdge Edge | The new edge should be placed after the specified edge. |

:: Node | The node |

-> EdgePos | Positioning information at |

-> Node | The node |

-> EdgePos | Positioning information at |

-> e | The label for the main edge |

-> e | The label for the inverse edge |

-> PlanarGraph n e | The graph at which to add the edge. |

-> ((Edge, Edge), PlanarGraph n e) | The main and inverse edge identifiers, and the updated graph. |

Add an edge between two nodes `f`

and `t`

. In reality, since all
edges are duplicated (see `inverseEdge`

), two edges are inserted.

If either node does not currently have any edges, then its
corresponding `EdgePos`

value is ignored.

For example, let `g`

refer to the following graph (where
`n1`

, etc. are both the labels and the variable names):

==== ==== ( n1 ) ( n2 ) ==== ==== ==== ( n3 ) ====

We can add an edge between `n1`

and `n2`

(using `Anywhere`

as the
`EdgePos`

since there are currently no edges on either node):

((e1,e2),g') = addEdge n1 Anywhere n2 Anywhere "e1" "e2" g

This will result in the following graph:

e2 ==== <--------------- ==== ( n1 ) ( n2 ) ==== ---------------> ==== e1 ==== ( n3 ) ====

If we want to add edges between `n2`

and `n3`

, we have three
options for the location on `n2`

:

- Use

: since there is only one other edge, it makes no difference in terms of the embedding where the second edge goes.`Anywhere`

- Put the new edge

(going clockwise around`BeforeEdge`

e2`n2`

). - Put the new edge

(going clockwise around`AfterEdge`

e2`n2`

).

Since `n2`

currently only has one edge, all three `EdgePos`

values
will result in the same graph, so we can arbitrarily pick one:

((e3,e4),g'') = addEdge n2 (BeforeEdge e2) n3 Anywhere "e3" "e4" g'

However, with more edges care must be taken on which `EdgePos`

value is used. The resulting graph is:

e2 ==== <--------------- ==== ( n1 ) ( n2 ) ==== ---------------> ==== e1 | ^ | | e3 | | e4 | | v | ==== ( n3 ) ====

The same graph (up to the actual `Edge`

values; so it won't satisfy
`==`

) would have been obtained with:

((e4,e3), g'') = addEdge n3 Anywhere n2 (BeforeEdge e2) "e4" "e3" g'

addEdgeUndirected :: Node -> EdgePos -> Node -> EdgePos -> e -> PlanarGraph n e -> (Edge, PlanarGraph n e)

As with `addEdge`

, but the edges are meant to be undirected so
use the same label for both.

addUEdge :: Monoid e => Node -> EdgePos -> Node -> EdgePos -> PlanarGraph n e -> ((Edge, Edge), PlanarGraph n e)

## Graph Deconstruction

isEmpty :: PlanarGraph n e -> Bool

Determines if the graph is empty.

deleteNode :: Node -> PlanarGraph n e -> PlanarGraph n e

Delete the node and all adjacent edges from the graph.

deleteEdge :: Edge -> PlanarGraph n e -> PlanarGraph n e

Delete the edge and its inverse from the graph.

contractEdge :: Edge -> (n -> n -> n) -> PlanarGraph n e -> PlanarGraph n e

Merges the two nodes adjoined by this edge, and delete all edges
between them. The provided function is to decide what the label
for the resulting node should be (if the edge goes from `f`

to
`t`

, then the function is `fLabel -> tLabel -> newLabel`

). The
`Node`

value for the merged node is

.
`fromEdge`

pg e

Note that this may result in multiple edges between the new node and another node if it is adjacent to both nodes being merged.

## Other

mapNodes :: (n -> n') -> PlanarGraph n e -> PlanarGraph n' e

Apply a mapping function over the node labels.

adjustNodeLabel :: (n -> n) -> Node -> PlanarGraph n e -> PlanarGraph n e

Apply a function to the label of the specified node.

setNodeLabel :: n -> Node -> PlanarGraph n e -> PlanarGraph n e

Set the label of the specified node.

mapEdges :: (e -> e') -> PlanarGraph n e -> PlanarGraph n e'

Apply a mapping function over the edge labels.

adjustEdgeLabel :: (e -> e) -> Edge -> PlanarGraph n e -> PlanarGraph n e

Apply a function to the label of the specified edge.

setEdgeLabel :: e -> Edge -> PlanarGraph n e -> PlanarGraph n e

Set the label of the specified edge.

# Graph duals and faces

The *dual* of a planar graph *G* is another planar graph *H* such
that *H* has an node for every face in *G*, and an edge between two
nodes if the corresponding faces in *G* are adjacent. For example,
the graph (drawn as an undirected graph for simplicity):

o---------o---------o | | | | f1 | f2 | | | | o---------o---------o \ / \ / \ f3 / \ / outer \ / face \ / \ / \ / \ / o

has a dual graph of:

...... ..... ..... ... .. .. ...... .. . . . . . . ===== ===== ..... . . ..( f1 )...( f2 ) .... . . .. ===== ===== .. . . . . . . . . . . . . . ===== ===== . . / \.........( f3 )... . / \ ===== .... . | outer | . . \ face / . . \ / . . . ===== . . . . . . . . . . . . ............. . . . .. . . . . .... ................

A dual graph is a planar *multigraph*: it will still be a planar
graph, but may have loops and multiple edges. However, the dual of a
dual graph will be the original graph (though no guarantees are made
that `g == makeDual (makeDual g)`

due to differing `Node`

and `Edge`

values).

Note that the functions here assume that the graph is *connected*;
in effect multiple connected components will be treated individually
with no notion of relative embeddings.

data Face

An abstract representation of a face.

Bounded Face | |

Enum Face | |

Eq Face | |

Ord Face | |

Read Face | Note that this instance of |

Show Face | This instance of |

adjoiningFaces :: FaceInfo -> CList Face

getFaces :: PlanarGraph n e -> FaceMap

Finds all faces in the planar graph. A face is defined by traversing along the right-hand-side of edges, e.g.:

o----------------------------->o ^..............................| |..............................| |..............FACE............| |..............................| |..............................v o<-----------------------------o

(with the inverse edges all being on the outside of the edges shown).

getFace :: PlanarGraph n e -> Edge -> ([Node], [Edge])

Returns all nodes and edges in the same face as the provided edge (including that edge); assumes the edge is part of the graph.

## Constructing the dual

makeDual :: PlanarGraph n e -> PlanarGraph () ()

Create the dual of a planar graph. If actual node and edge
labels are required, use `toDual`

.

toDual :: (Face -> n) -> (Face -> Edge -> Face -> e) -> FaceMap -> PlanarGraph n e

Create the planar graph corresponding to the dual of the face
relationships. The usage of `FaceMap`

rather than `PlanarGraph`

is to allow you to use the `FaceMap`

for constructing the
label-creation functions if you so wish.

The function `edgeLabel`

for edge labels takes the `Face`

that the
edge comes from, the `Edge`

belonging to that `Face`

that it is
crossing and then the `Face`

that it is going to. For example:

.... ....> ...> =====.... (#####) ===== | ^ e2 | | | | face1 | | face2 | | | | | | e1 v | ===== (#####) ...===== <.. <... .... ...

Here, the edge in the dual graph going from *face1* to *face2*
will have a label of "`edgeLabel face1 e1 face2`

", and the edge
going from *face2* to *face1* will have a label of "```
edgeLabel
face2 e2 face1
```

".

# Alternate representations

## Serialisation

Serialisation support can be found here to aid in converting a
`PlanarGraph`

to alternate formats. Care should be taken when
constructing the `SerialisedGraph`

, and these functions should not be
abused just to edit an existing `PlanarGraph`

.

type SerialisedGraph n e = [(Int, n, [(Int, Int, e, Int)])]

The definition of a more compact, serialised form of a planar graph. The various fields correspond to:

[( node index , node label , [( edge index , node index that this edge points to , edge label , inverse edge index )] )]

The list of edges should be in clockwise order around the node.

serialise :: PlanarGraph n e -> SerialisedGraph n e

deserialise :: SerialisedGraph n e -> PlanarGraph n e

## Pretty-Printing

prettify :: (Show n, Show e) => PlanarGraph n e -> String

Pretty-print the graph. Note that this loses a lot of information, such as edge inverses, etc.

prettyPrint :: (Show n, Show e) => PlanarGraph n e -> IO ()

Pretty-print the graph to stdout.