hgeometry-0.7.0.0: Geometric Algorithms, Data structures, and Data types.

Data.PlanarGraph

Synopsis

# Documentation

newtype Arc s Source #

An Arc is a directed edge in a planar graph. The type s is used to tie this arc to a particular graph.

Constructors

 Arc Fields_unArc :: Int
Instances
 Bounded (Arc s) Source # Instance detailsDefined in Data.PlanarGraph MethodsminBound :: Arc s #maxBound :: Arc s # Enum (Arc s) Source # Instance detailsDefined in Data.PlanarGraph Methodssucc :: Arc s -> Arc s #pred :: Arc s -> Arc s #toEnum :: Int -> Arc s #fromEnum :: Arc s -> Int #enumFrom :: Arc s -> [Arc s] #enumFromThen :: Arc s -> Arc s -> [Arc s] #enumFromTo :: Arc s -> Arc s -> [Arc s] #enumFromThenTo :: Arc s -> Arc s -> Arc s -> [Arc s] # Eq (Arc s) Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: Arc s -> Arc s -> Bool #(/=) :: Arc s -> Arc s -> Bool # Ord (Arc s) Source # Instance detailsDefined in Data.PlanarGraph Methodscompare :: Arc s -> Arc s -> Ordering #(<) :: Arc s -> Arc s -> Bool #(<=) :: Arc s -> Arc s -> Bool #(>) :: Arc s -> Arc s -> Bool #(>=) :: Arc s -> Arc s -> Bool #max :: Arc s -> Arc s -> Arc s #min :: Arc s -> Arc s -> Arc s # Show (Arc s) Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> Arc s -> ShowS #show :: Arc s -> String #showList :: [Arc s] -> ShowS #

data Direction Source #

Constructors

 Negative Positive
Instances
 Source # Instance detailsDefined in Data.PlanarGraph Methods Source # Instance detailsDefined in Data.PlanarGraph MethodsenumFrom :: Direction -> [Direction] # Source # Instance detailsDefined in Data.PlanarGraph Methods Source # Instance detailsDefined in Data.PlanarGraph Methods Source # Instance detailsDefined in Data.PlanarGraph Methods Source # Instance detailsDefined in Data.PlanarGraph MethodsshowList :: [Direction] -> ShowS #

Reverse the direcion

data Dart s Source #

A dart represents a bi-directed edge. I.e. a dart has a direction, however the dart of the oposite direction is always present in the planar graph as well.

Constructors

 Dart Fields_arc :: !(Arc s) _direction :: !Direction
Instances
 Enum (Dart s) Source # Instance detailsDefined in Data.PlanarGraph Methodssucc :: Dart s -> Dart s #pred :: Dart s -> Dart s #toEnum :: Int -> Dart s #fromEnum :: Dart s -> Int #enumFrom :: Dart s -> [Dart s] #enumFromThen :: Dart s -> Dart s -> [Dart s] #enumFromTo :: Dart s -> Dart s -> [Dart s] #enumFromThenTo :: Dart s -> Dart s -> Dart s -> [Dart s] # Eq (Dart s) Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: Dart s -> Dart s -> Bool #(/=) :: Dart s -> Dart s -> Bool # Ord (Dart s) Source # Instance detailsDefined in Data.PlanarGraph Methodscompare :: Dart s -> Dart s -> Ordering #(<) :: Dart s -> Dart s -> Bool #(<=) :: Dart s -> Dart s -> Bool #(>) :: Dart s -> Dart s -> Bool #(>=) :: Dart s -> Dart s -> Bool #max :: Dart s -> Dart s -> Dart s #min :: Dart s -> Dart s -> Dart s # Show (Dart s) Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> Dart s -> ShowS #show :: Dart s -> String #showList :: [Dart s] -> ShowS # HasDataOf (PlanarGraph s w v e f) (Dart s) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s)) Source # HasDataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph Associated Typestype DataOf (PlaneGraph s v e f r) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s)) Source # HasDataOf (PlanarSubdivision s v e f r) (Dart s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s)) Source # type DataOf (PlanarGraph s w v e f) (Dart s) Source # Instance detailsDefined in Data.PlanarGraph type DataOf (PlanarGraph s w v e f) (Dart s) = e type DataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph type DataOf (PlaneGraph s v e f r) (Dart s) = e type DataOf (PlanarSubdivision s v e f r) (Dart s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic type DataOf (PlanarSubdivision s v e f r) (Dart s) = e

arc :: forall s s. Lens (Dart s) (Dart s) (Arc s) (Arc s) Source #

twin :: Dart s -> Dart s Source #

Get the twin of this dart (edge)

>>> twin (dart 0 "+1")
Dart (Arc 0) -1
>>> twin (dart 0 "-1")
Dart (Arc 0) +1


test if a dart is Positive

data World Source #

The world in which the graph lives

Constructors

 Primal Dual
Instances
 Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: World -> World -> Bool #(/=) :: World -> World -> Bool # Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> World -> ShowS #show :: World -> String #showList :: [World] -> ShowS #

type family DualOf (sp :: World) where ... Source #

Equations

 DualOf Primal = Dual DualOf Dual = Primal

newtype VertexId s (w :: World) Source #

A vertex in a planar graph. A vertex is tied to a particular planar graph by the phantom type s, and to a particular world w.

Constructors

 VertexId Fields_unVertexId :: Int
Instances
 Enum (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph Methodssucc :: VertexId s w -> VertexId s w #pred :: VertexId s w -> VertexId s w #toEnum :: Int -> VertexId s w #fromEnum :: VertexId s w -> Int #enumFrom :: VertexId s w -> [VertexId s w] #enumFromThen :: VertexId s w -> VertexId s w -> [VertexId s w] #enumFromTo :: VertexId s w -> VertexId s w -> [VertexId s w] #enumFromThenTo :: VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w] # Eq (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: VertexId s w -> VertexId s w -> Bool #(/=) :: VertexId s w -> VertexId s w -> Bool # Ord (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph Methodscompare :: VertexId s w -> VertexId s w -> Ordering #(<) :: VertexId s w -> VertexId s w -> Bool #(<=) :: VertexId s w -> VertexId s w -> Bool #(>) :: VertexId s w -> VertexId s w -> Bool #(>=) :: VertexId s w -> VertexId s w -> Bool #max :: VertexId s w -> VertexId s w -> VertexId s w #min :: VertexId s w -> VertexId s w -> VertexId s w # Show (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> VertexId s w -> ShowS #show :: VertexId s w -> String #showList :: [VertexId s w] -> ShowS # ToJSON (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph MethodstoJSON :: VertexId s w -> Value #toEncoding :: VertexId s w -> Encoding #toJSONList :: [VertexId s w] -> Value #toEncodingList :: [VertexId s w] -> Encoding # FromJSON (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph MethodsparseJSON :: Value -> Parser (VertexId s w) #parseJSONList :: Value -> Parser [VertexId s w] # HasDataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph Associated Typestype DataOf (PlaneGraph s v e f r) (VertexId' s) :: * Source # MethodsdataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s)) Source # HasDataOf (PlanarSubdivision s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: * Source # MethodsdataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s)) Source # HasDataOf (PlanarGraph s w v e f) (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (VertexId s w) :: * Source # MethodsdataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w)) Source # type DataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph type DataOf (PlaneGraph s v e f r) (VertexId' s) = v type DataOf (PlanarSubdivision s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic type DataOf (PlanarSubdivision s v e f r) (VertexId' s) = v type DataOf (PlanarGraph s w v e f) (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph type DataOf (PlanarGraph s w v e f) (VertexId s w) = v

data PlanarGraph s (w :: World) v e f Source #

A *connected* Planar graph with bidirected edges. I.e. the edges (darts) are directed, however, for every directed edge, the edge in the oposite direction is also in the graph.

The types v, e, and f are the are the types of the data associated with the vertices, edges, and faces, respectively.

The orbits in the embedding are assumed to be in counterclockwise order. Therefore, every dart directly bounds the face to its right.

Instances
 (Eq v, Eq e, Eq f) => Eq (PlanarGraph s w v e f) Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool #(/=) :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool # (Show v, Show e, Show f) => Show (PlanarGraph s w v e f) Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> PlanarGraph s w v e f -> ShowS #show :: PlanarGraph s w v e f -> String #showList :: [PlanarGraph s w v e f] -> ShowS # (ToJSON v, ToJSON e, ToJSON f) => ToJSON (PlanarGraph s w v e f) Source # Instance detailsDefined in Data.PlanarGraph MethodstoJSON :: PlanarGraph s w v e f -> Value #toEncoding :: PlanarGraph s w v e f -> Encoding #toJSONList :: [PlanarGraph s w v e f] -> Value #toEncodingList :: [PlanarGraph s w v e f] -> Encoding # (FromJSON v, FromJSON e, FromJSON f) => FromJSON (PlanarGraph s Primal v e f) Source # Instance detailsDefined in Data.PlanarGraph MethodsparseJSON :: Value -> Parser (PlanarGraph s Primal v e f) #parseJSONList :: Value -> Parser [PlanarGraph s Primal v e f] # HasDataOf (PlanarGraph s w v e f) (Dart s) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s)) Source # HasDataOf (PlanarGraph s w v e f) (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (VertexId s w) :: * Source # MethodsdataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w)) Source # HasDataOf (PlanarGraph s w v e f) (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (FaceId s w) :: * Source # MethodsdataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w)) Source # type DataOf (PlanarGraph s w v e f) (Dart s) Source # Instance detailsDefined in Data.PlanarGraph type DataOf (PlanarGraph s w v e f) (Dart s) = e type DataOf (PlanarGraph s w v e f) (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph type DataOf (PlanarGraph s w v e f) (VertexId s w) = v type DataOf (PlanarGraph s w v e f) (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph type DataOf (PlanarGraph s w v e f) (FaceId s w) = f

vertexData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v' e f) (Vector v) (Vector v') Source #

dartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector (Dart s, e)) (Vector (Dart s, e')) Source #

lens to access the Dart Data

faceData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e f') (Vector f) (Vector f') Source #

rawDartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector e) (Vector e') Source #

edgeData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector (Dart s, e)) (Vector (Dart s, e')) Source #

edgeData is just an alias for dartData

planarGraph :: [[(Dart s, e)]] -> PlanarGraph s Primal () e () Source #

Construct a planar graph, given the darts in cyclic order around each vertex.

running time: $$O(n)$$.

planarGraph' :: Permutation (Dart s) -> PlanarGraph s w () () () Source #

Construct a planar graph

running time: $$O(n)$$.

fromAdjacencyLists :: forall s w h. (Foldable h, Functor h) => [(VertexId s w, h (VertexId s w))] -> PlanarGraph s w () () () Source #

Construct a planar graph from a adjacency matrix. For every vertex, all vertices should be given in counter clockwise order.

pre: No self-loops, and no multi-edges

running time: $$O(n)$$.

toAdjacencyLists :: PlanarGraph s w v e f -> [(VertexId s w, Vector (VertexId s w))] Source #

Produces the adjacencylists for all vertices in the graph. For every vertex, the adjacent vertices are given in counter clockwise order.

Note that in case a vertex u as a self loop, we have that this vertexId occurs twice in the list of neighbours, i.e.: u : [...,u,..,u,...]. Similarly, if there are multiple darts between a pair of edges they occur multiple times.

running time: $$O(n)$$

buildFromJSON :: Vector (VertexId' s :+ v) -> Vector ((VertexId' s, VertexId' s) :+ e) -> Vector (FaceId' s :+ f) -> [(VertexId' s, Vector (VertexId' s))] -> PlanarGraph s Primal v e f Source #

Helper function to build the graph from JSON data

running time: $$O(n)$$

numVertices :: PlanarGraph s w v e f -> Int Source #

Get the number of vertices

>>> numVertices myGraph
4


numDarts :: PlanarGraph s w v e f -> Int Source #

Get the number of Darts

>>> numDarts myGraph
12


numEdges :: PlanarGraph s w v e f -> Int Source #

Get the number of Edges

>>> numEdges myGraph
6


numFaces :: PlanarGraph s w v e f -> Int Source #

Get the number of faces

>>> numFaces myGraph
4


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

Enumerate all darts

darts :: PlanarGraph s w v e f -> Vector (Dart s, e) Source #

Get all darts together with their data

>>> mapM_ print $darts myGraph (Dart (Arc 0) -1,"a-") (Dart (Arc 2) +1,"c+") (Dart (Arc 1) +1,"b+") (Dart (Arc 0) +1,"a+") (Dart (Arc 4) -1,"e-") (Dart (Arc 1) -1,"b-") (Dart (Arc 3) -1,"d-") (Dart (Arc 5) +1,"g+") (Dart (Arc 4) +1,"e+") (Dart (Arc 3) +1,"d+") (Dart (Arc 2) -1,"c-") (Dart (Arc 5) -1,"g-")  edges' :: PlanarGraph s w v e f -> Vector (Dart s) Source # Enumerate all edges. We report only the Positive darts edges :: PlanarGraph s w v e f -> Vector (Dart s, e) Source # Enumerate all edges with their edge data. We report only the Positive darts. >>> mapM_ print$ edges myGraph
(Dart (Arc 2) +1,"c+")
(Dart (Arc 1) +1,"b+")
(Dart (Arc 0) +1,"a+")
(Dart (Arc 5) +1,"g+")
(Dart (Arc 4) +1,"e+")
(Dart (Arc 3) +1,"d+")


vertices' :: PlanarGraph s w v e f -> Vector (VertexId s w) Source #

Enumerate all vertices

>>> vertices' myGraph
[VertexId 0,VertexId 1,VertexId 2,VertexId 3]


vertices :: PlanarGraph s w v e f -> Vector (VertexId s w, v) Source #

Enumerate all vertices, together with their vertex data

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.

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

The tail of a dart, i.e. the vertex this dart is leaving from

running time: $$O(1)$$

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

The vertex this dart is heading in to

running time: $$O(1)$$

endPoints :: Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w) Source #

endPoints d g = (tailOf d g, headOf d g)

running time: $$O(1)$$

incidentEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s) Source #

All edges incident to vertex v, in counterclockwise order around v.

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

incomingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s) Source #

All incoming edges incident to vertex v, in counterclockwise order around v.

outgoingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s) Source #

All outgoing edges incident to vertex v, in counterclockwise order around v.

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

Gets the neighbours of a particular vertex, in counterclockwise order around the vertex.

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

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

Given a dart d that points into some vertex v, report the next dart in the cyclic order around v.

running time: $$O(1)$$

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

Given a dart d that points into some vertex v, report the next dart in the cyclic order around v.

running time: $$O(1)$$

class HasDataOf g i where Source #

Minimal complete definition

dataOf

Associated Types

type DataOf g i Source #

Methods

dataOf :: i -> Lens' g (DataOf g i) Source #

get the data associated with the value i.

running time: $$O(1)$$ to read the data, $$O(n)$$ to write it.

Instances
 HasDataOf (PlanarGraph s w v e f) (Dart s) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s)) Source # HasDataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph Associated Typestype DataOf (PlaneGraph s v e f r) (FaceId' s) :: * Source # MethodsdataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s)) Source # HasDataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph Associated Typestype DataOf (PlaneGraph s v e f r) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s)) Source # HasDataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph Associated Typestype DataOf (PlaneGraph s v e f r) (VertexId' s) :: * Source # MethodsdataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s)) Source # HasDataOf (PlanarSubdivision s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: * Source # MethodsdataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s)) Source # HasDataOf (PlanarSubdivision s v e f r) (Dart s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (Dart s) :: * Source # MethodsdataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s)) Source # HasDataOf (PlanarSubdivision s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: * Source # MethodsdataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s)) Source # HasDataOf (PlanarGraph s w v e f) (VertexId s w) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (VertexId s w) :: * Source # MethodsdataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w)) Source # HasDataOf (PlanarGraph s w v e f) (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (FaceId s w) :: * Source # MethodsdataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w)) Source #

endPointDataOf :: Dart s -> Getter (PlanarGraph s w v e f) (v, v) Source #

Data corresponding to the endpoints of the dart

endPointData :: Dart s -> PlanarGraph s w v e f -> (v, v) Source #

Data corresponding to the endpoints of the dart

running time: $$O(1)$$

dual :: Getter (PlanarGraph s w v e f) (PlanarGraph s (DualOf w) f e v) Source #

newtype FaceId s w Source #

A face

Constructors

 FaceId Fields_unFaceId :: VertexId s (DualOf w)
Instances
 Eq (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: FaceId s w -> FaceId s w -> Bool #(/=) :: FaceId s w -> FaceId s w -> Bool # Ord (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph Methodscompare :: FaceId s w -> FaceId s w -> Ordering #(<) :: FaceId s w -> FaceId s w -> Bool #(<=) :: FaceId s w -> FaceId s w -> Bool #(>) :: FaceId s w -> FaceId s w -> Bool #(>=) :: FaceId s w -> FaceId s w -> Bool #max :: FaceId s w -> FaceId s w -> FaceId s w #min :: FaceId s w -> FaceId s w -> FaceId s w # Show (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> FaceId s w -> ShowS #show :: FaceId s w -> String #showList :: [FaceId s w] -> ShowS # ToJSON (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph MethodstoJSON :: FaceId s w -> Value #toEncoding :: FaceId s w -> Encoding #toJSONList :: [FaceId s w] -> Value #toEncodingList :: [FaceId s w] -> Encoding # FromJSON (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph MethodsparseJSON :: Value -> Parser (FaceId s w) #parseJSONList :: Value -> Parser [FaceId s w] # HasDataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph Associated Typestype DataOf (PlaneGraph s v e f r) (FaceId' s) :: * Source # MethodsdataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s)) Source # HasDataOf (PlanarSubdivision s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: * Source # MethodsdataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s)) Source # HasDataOf (PlanarGraph s w v e f) (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph Associated Typestype DataOf (PlanarGraph s w v e f) (FaceId s w) :: * Source # MethodsdataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w)) Source # type DataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph type DataOf (PlaneGraph s v e f r) (FaceId' s) = f type DataOf (PlanarSubdivision s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic type DataOf (PlanarSubdivision s v e f r) (FaceId' s) = f type DataOf (PlanarGraph s w v e f) (FaceId s w) Source # Instance detailsDefined in Data.PlanarGraph type DataOf (PlanarGraph s w v e f) (FaceId s w) = f

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

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.

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

data EdgeOracle s w a Source #

Edge Oracle:

main idea: store adjacency lists in such a way that we store an edge (u,v) either in u's adjacency list or in v's. This can be done s.t. all adjacency lists have length at most 6.

note: Every edge is stored exactly once (i.e. either at u or at v, but not both)

Instances
 Functor (EdgeOracle s w) Source # Instance detailsDefined in Data.PlanarGraph Methodsfmap :: (a -> b) -> EdgeOracle s w a -> EdgeOracle s w b #(<\$) :: a -> EdgeOracle s w b -> EdgeOracle s w a # Foldable (EdgeOracle s w) Source # Instance detailsDefined in Data.PlanarGraph Methodsfold :: Monoid m => EdgeOracle s w m -> m #foldMap :: Monoid m => (a -> m) -> EdgeOracle s w a -> m #foldr :: (a -> b -> b) -> b -> EdgeOracle s w a -> b #foldr' :: (a -> b -> b) -> b -> EdgeOracle s w a -> b #foldl :: (b -> a -> b) -> b -> EdgeOracle s w a -> b #foldl' :: (b -> a -> b) -> b -> EdgeOracle s w a -> b #foldr1 :: (a -> a -> a) -> EdgeOracle s w a -> a #foldl1 :: (a -> a -> a) -> EdgeOracle s w a -> a #toList :: EdgeOracle s w a -> [a] #null :: EdgeOracle s w a -> Bool #length :: EdgeOracle s w a -> Int #elem :: Eq a => a -> EdgeOracle s w a -> Bool #maximum :: Ord a => EdgeOracle s w a -> a #minimum :: Ord a => EdgeOracle s w a -> a #sum :: Num a => EdgeOracle s w a -> a #product :: Num a => EdgeOracle s w a -> a # Source # Instance detailsDefined in Data.PlanarGraph Methodstraverse :: Applicative f => (a -> f b) -> EdgeOracle s w a -> f (EdgeOracle s w b) #sequenceA :: Applicative f => EdgeOracle s w (f a) -> f (EdgeOracle s w a) #mapM :: Monad m => (a -> m b) -> EdgeOracle s w a -> m (EdgeOracle s w b) #sequence :: Monad m => EdgeOracle s w (m a) -> m (EdgeOracle s w a) # Eq a => Eq (EdgeOracle s w a) Source # Instance detailsDefined in Data.PlanarGraph Methods(==) :: EdgeOracle s w a -> EdgeOracle s w a -> Bool #(/=) :: EdgeOracle s w a -> EdgeOracle s w a -> Bool # Show a => Show (EdgeOracle s w a) Source # Instance detailsDefined in Data.PlanarGraph MethodsshowsPrec :: Int -> EdgeOracle s w a -> ShowS #show :: EdgeOracle s w a -> String #showList :: [EdgeOracle s w a] -> ShowS #

edgeOracle :: PlanarGraph s w v e f -> EdgeOracle s w (Dart s) Source #

Given a planar graph, construct an edge oracle. Given a pair of vertices this allows us to efficiently find the dart representing this edge in the graph.

pre: No self-loops and no multi-edges!!!

running time: $$O(n)$$

buildEdgeOracle :: forall f s w e. Foldable f => [(VertexId s w, f (VertexId s w :+ e))] -> EdgeOracle s w e Source #

Builds an edge oracle that can be used to efficiently test if two vertices are connected by an edge.

running time: $$O(n)$$

findEdge :: VertexId s w -> VertexId s w -> EdgeOracle s w a -> Maybe a Source #

Find the edge data corresponding to edge (u,v) if such an edge exists

running time: $$O(1)$$

hasEdge :: VertexId s w -> VertexId s w -> EdgeOracle s w a -> Bool Source #

Test if u and v are connected by an edge.

running time: $$O(1)$$

findDart :: VertexId s w -> VertexId s w -> EdgeOracle s w (Dart s) -> Maybe (Dart s) Source #

Given a pair of vertices (u,v) returns the dart, oriented from u to v, corresponding to these vertices.

running time: $$O(1)$$

allDarts :: [Dart s] Source #

Enumerates all darts such that allDarts !! i = d = i == fromEnum d