Copyright | (C) Frank Staals |
---|---|

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

Data type for representing connected planar graphs. This module contains everything that has to do with the dual graph (i.e. computing it/ operations on faces etc.)

## Synopsis

- faces' :: PlanarGraph s w v e f -> Vector (FaceId s w)
- faces :: PlanarGraph s w v e f -> Vector (FaceId s w, f)
- leftFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w
- rightFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w
- nextEdge :: Dart s -> PlanarGraph s w v e f -> Dart s
- prevEdge :: Dart s -> PlanarGraph s w v e f -> Dart s
- boundaryDart :: FaceId s w -> PlanarGraph s w v e f -> Dart s
- boundary :: FaceId s w -> PlanarGraph s w v e f -> Vector (Dart s)
- boundary' :: Dart s -> PlanarGraph s w v e f -> Vector (Dart s)
- boundaryVertices :: FaceId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)

# Documentation

`>>>`

let dart i s = Dart (Arc i) (read s) (aA:aB:aC:aD:aE:aG:_) = take 6 [Arc 0..] myGraph :: PlanarGraph () Primal () String () myGraph = planarGraph [ [ (Dart aA Negative, "a-") , (Dart aC Positive, "c+") , (Dart aB Positive, "b+") , (Dart aA Positive, "a+") ] , [ (Dart aE Negative, "e-") , (Dart aB Negative, "b-") , (Dart aD Negative, "d-") , (Dart aG Positive, "g+") ] , [ (Dart aE Positive, "e+") , (Dart aD Positive, "d+") , (Dart aC Negative, "c-") ] , [ (Dart aG Negative, "g-") ] ] :}`:{`

This represents the following graph. Note that the graph is undirected, the arrows are just to indicate what the Positive direction of the darts is.

faces' :: PlanarGraph s w v e f -> Vector (FaceId s w) Source #

Enumerate all faces in the planar graph

leftFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w Source #

The face to the left of the dart

`>>>`

FaceId 1`leftFace (dart 1 "+1") myGraph`

`>>>`

FaceId 2`leftFace (dart 1 "-1") myGraph`

`>>>`

FaceId 2`leftFace (dart 2 "+1") myGraph`

`>>>`

FaceId 0`leftFace (dart 0 "+1") myGraph`

running time: \(O(1)\).

rightFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w Source #

The face to the right of the dart

`>>>`

FaceId 2`rightFace (dart 1 "+1") myGraph`

`>>>`

FaceId 1`rightFace (dart 1 "-1") myGraph`

`>>>`

FaceId 1`rightFace (dart 2 "+1") myGraph`

`>>>`

FaceId 1`rightFace (dart 0 "+1") myGraph`

running time: \(O(1)\).

nextEdge :: Dart s -> PlanarGraph s w v e f -> Dart s Source #

Get the next edge along the face

running time: \(O(1)\).

prevEdge :: Dart s -> PlanarGraph s w v e f -> Dart s Source #

Get the previous edge along the face

running time: \(O(1)\).

boundaryDart :: FaceId s w -> PlanarGraph s w v e f -> Dart s Source #

Gets a dart bounding this face. I.e. a dart d such that the face lies to the right of the dart.

boundary :: FaceId s w -> PlanarGraph s w v e f -> Vector (Dart s) Source #

The darts bounding this face, for internal faces in clockwise order, for the outer face in counter clockwise order.

running time: \(O(k)\), where \(k\) is the output size.

boundary' :: Dart s -> PlanarGraph s w v e f -> Vector (Dart s) Source #

Generates the darts incident to a face, starting with the given dart.

\(O(k)\), where \(k\) is the number of darts reported

boundaryVertices :: FaceId s w -> PlanarGraph s w v e f -> Vector (VertexId s w) Source #

The vertices bounding this face, for internal faces in clockwise order, for the outer face in counter clockwise order.

running time: \(O(k)\), where \(k\) is the output size.