Data.PlanarGraph.Mutable

Planar graphs

data PlanarGraph s

Instances

Eq (PlanarGraph s)

Defined in Data.PlanarGraph.Internal

Methods

(==) :: PlanarGraph s -> PlanarGraph s -> Bool

(/=) :: PlanarGraph s -> PlanarGraph s -> Bool

pgFromFaces :: [[VertexId]] -> ST s (PlanarGraph s)

\( O(n \log n) \)

Examples:

pgFromFaces [[0,1,2]]

pgFromFaces [[0,1,2,3]]

pgFromFacesCV :: [CircularVector VertexId] -> ST s (PlanarGraph s)

pgClone :: PlanarGraph s -> ST s (PlanarGraph s)

\( O(n) \)

pgHash :: PlanarGraph s -> ST s Int

Elements

Vertices

data Vertex s

Instances

Eq (Vertex s)

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: Vertex s -> Vertex s -> Bool

(/=) :: Vertex s -> Vertex s -> Bool

Show (Vertex s)

Defined in Data.PlanarGraph.Mutable

Methods

showsPrec :: Int -> Vertex s -> ShowS

show :: Vertex s -> String

showList :: [Vertex s] -> ShowS

Hashable (Vertex s)

Defined in Data.PlanarGraph.Mutable

Methods

hashWithSalt :: Int -> Vertex s -> Int

hash :: Vertex s -> Int

type VertexId = Int

vertexFromId :: VertexId -> PlanarGraph s -> Vertex s

\( O(1) \)

vertexToId :: Vertex s -> VertexId

\( O(1) \)

vertexHalfEdge :: Vertex s -> ST s (HalfEdge s)

\( O(1) \)

vertexIsBoundary :: Vertex s -> ST s Bool

\( O(1) \)

vertexOutgoingHalfEdges :: Vertex s -> ST s (CircularVector (HalfEdge s))

O(k)

vertexWithOutgoingHalfEdges :: Vertex s -> (HalfEdge s -> ST s ()) -> ST s ()

O(k), more efficient than vertexOutgoingHalfEdges.

vertexIncomingHalfEdges :: Vertex s -> ST s (CircularVector (HalfEdge s))

O(k)

vertexWithIncomingHalfEdges :: Vertex s -> (HalfEdge s -> ST s ()) -> ST s ()

O(k)

vertexNeighbours :: Vertex s -> ST s (CircularVector (Vertex s))

O(k)

Edges

data Edge s

Instances

Eq (Edge s)

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: Edge s -> Edge s -> Bool

(/=) :: Edge s -> Edge s -> Bool

type EdgeId = Int

edgeFromId :: EdgeId -> PlanarGraph s -> Edge s

O(1)

edgeToId :: Edge s -> EdgeId

O(1)

edgeFromHalfEdge :: HalfEdge s -> Edge s

O(1)

Half-edges

data HalfEdge s

Instances

Eq (HalfEdge s)

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: HalfEdge s -> HalfEdge s -> Bool

(/=) :: HalfEdge s -> HalfEdge s -> Bool

Show (HalfEdge s)

Defined in Data.PlanarGraph.Mutable

Methods

showsPrec :: Int -> HalfEdge s -> ShowS

show :: HalfEdge s -> String

showList :: [HalfEdge s] -> ShowS

Hashable (HalfEdge s)

Defined in Data.PlanarGraph.Mutable

Methods

hashWithSalt :: Int -> HalfEdge s -> Int

hash :: HalfEdge s -> Int

type HalfEdgeId = Int

halfEdgeFromId :: HalfEdgeId -> PlanarGraph s -> HalfEdge s

O(1)

halfEdgeToId :: HalfEdge s -> HalfEdgeId

O(1)

halfEdgeNext :: HalfEdge s -> ST s (HalfEdge s)

O(1)

halfEdgePrev :: HalfEdge s -> ST s (HalfEdge s)

O(1)

halfEdgeNextOutgoing :: HalfEdge s -> ST s (HalfEdge s)

O(1) Next half-edge with the same vertex.

halfEdgeNextIncoming :: HalfEdge s -> ST s (HalfEdge s)

O(1) Next half-edge with the same vertex.

halfEdgeVertex :: HalfEdge s -> ST s (Vertex s)

O(1)

halfEdgeTwin :: HalfEdge s -> HalfEdge s

O(1)

halfEdgeTailVertex :: HalfEdge s -> ST s (Vertex s)

O(1) Tail vertex. IE. the vertex of the twin edge.

halfEdgeTipVertex :: HalfEdge s -> ST s (Vertex s)

O(1) Synonym of halfEdgeVertex.

halfEdgeFace :: HalfEdge s -> ST s (Face s)

\( O(1) \)

Examples:

pgFromFaces [[0,1,2]]

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; show <$> halfEdgeFace (halfEdgeFromId 0 pg)
"Face 0"

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; show <$> halfEdgeFace (halfEdgeFromId 1 pg)
"Boundary 0"

halfEdgeIsInterior :: HalfEdge s -> ST s Bool

\( O(1) \) Check if a half-edge's face is interior or exterior.

Examples:

pgFromFaces [[0,1,2]]

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 0 pg)
True

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 1 pg)
False

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 2 pg)
True

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 3 pg)
False

Faces

data Face s

Instances

Eq (Face s)

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: Face s -> Face s -> Bool

(/=) :: Face s -> Face s -> Bool

Show (Face s)

Defined in Data.PlanarGraph.Mutable

Methods

showsPrec :: Int -> Face s -> ShowS

show :: Face s -> String

showList :: [Face s] -> ShowS

type FaceId = Int

Numerical face identifier. Negative numbers indicate boundaries, non-negative numbers are internal faces.

faceInvalid :: PlanarGraph s -> Face s

O(1)

faceIsValid :: Face s -> Bool

O(1)

faceIsInvalid :: Face s -> Bool

O(1)

faceFromId :: FaceId -> PlanarGraph s -> Face s

O(1)

faceToId :: Face s -> FaceId

O(1)

faceHalfEdge :: Face s -> ST s (HalfEdge s)

O(1)

faceIsInterior :: Face s -> Bool

O(1)

faceIsBoundary :: Face s -> Bool

O(1)

faceHalfEdges :: Face s -> ST s (CircularVector (HalfEdge s))

O(k) Counterclockwise vector of edges.

faceBoundary :: Face s -> ST s (CircularVector (Vertex s))

O(k)

Mutation

pgConnectVertices :: HalfEdge s -> HalfEdge s -> ST s (Edge s)

O(k) where k is the number of edges in new face.

The two half-edges must be different, must have the same face, and may not be consecutive. The first half-edge will stay in the original face. The second half-edge will be in the newly created face.

Examples:

pgFromFaces [[0,1,2,3]]

do pg <- pgFromFaces [[0,1,2,3]]
   let he0 = halfEdgeFromId 0 pg'
       he4 = halfEdgeFromId 4 pg'
   pgConnectVertices he0 he4

Misc