Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Data.PlanarGraph.Dual

Description

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.

myGraph

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

Enumerate all faces in the planar graph

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

All faces with their face data.

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

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 Source #

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