Data.PlanarGraph.Dual

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

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)

Enumerate all faces in the planar graph

faces :: PlanarGraph s w v e f -> Vector (FaceId s w, f)

All faces with their face data.

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

The face to the left of the dart

>>> leftFace (dart 1 "+1") myGraph
FaceId 1
>>> leftFace (dart 1 "-1") myGraph
FaceId 2
>>> leftFace (dart 2 "+1") myGraph
FaceId 2
>>> leftFace (dart 0 "+1") myGraph
FaceId 0

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

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

The face to the right of the dart

>>> rightFace (dart 1 "+1") myGraph
FaceId 2
>>> rightFace (dart 1 "-1") myGraph
FaceId 1
>>> rightFace (dart 2 "+1") myGraph
FaceId 1
>>> rightFace (dart 0 "+1") myGraph
FaceId 1

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

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

Get the next edge along the face

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

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

Get the previous edge along the face

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

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

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)

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)

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)

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.