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

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

Converting from/to Adjacency Representation of the plane graph

## Synopsis

- readPlaneGraph :: (FromJSON v, FromJSON e, FromJSON f, FromJSON r) => proxy s -> ByteString -> Either ParseException (PlaneGraph s v e f r)
- writePlaneGraph :: (ToJSON v, ToJSON e, ToJSON f, ToJSON r) => PlaneGraph s v e f r -> ByteString
- toAdjRep :: PlaneGraph s v e f r -> Gr (Vtx v e r) (Face f)
- fromAdjRep :: proxy s -> Gr (Vtx v e r) (Face f) -> PlaneGraph s v e f r
- makeCCW :: (Num r, Ord r) => Gr (Vtx v e r) f -> Gr (Vtx v e r) f

# Documentation

`>>>`

`import Data.PlanarGraph.Dart`

`>>>`

`import Data.PlanarGraph.AdjRep(Face(..))`

`>>>`

let dart i s = Dart (Arc i) (read s) small :: Gr (Vtx Int String Int) (Face String) small = Gr [ Vtx 0 (Point2 0 0) [ (2,"0->2") , (1,"0->1") , (3,"0->3") ] 0 , Vtx 1 (Point2 2 2) [ (0,"1->0") , (2,"1->2") , (3,"1->3") ] 1 , Vtx 2 (Point2 2 0) [ (0,"2->0") , (1,"2->1") ] 2 , Vtx 3 (Point2 (-1) 4) [ (0,"3->0") , (1,"3->1") ] 3 ] [ Face (2,1) "OuterFace" , Face (0,1) "A" , Face (1,0) "B" ] smallG = fromAdjRep (Proxy :: Proxy ()) small :}`:{`

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.

# Reading and Writing the Plane Graph

readPlaneGraph :: (FromJSON v, FromJSON e, FromJSON f, FromJSON r) => proxy s -> ByteString -> Either ParseException (PlaneGraph s v e f r) Source #

Reads a plane graph from a bytestring

writePlaneGraph :: (ToJSON v, ToJSON e, ToJSON f, ToJSON r) => PlaneGraph s v e f r -> ByteString Source #

Writes a plane graph to a bytestring

toAdjRep :: PlaneGraph s v e f r -> Gr (Vtx v e r) (Face f) Source #

Transforms the plane graph into adjacency lists. For every vertex, the adjacent vertices are given in counter clockwise order.

See `toAdjacencyLists`

for notes on how we handle self-loops.

running time: \(O(n)\)

fromAdjRep :: proxy s -> Gr (Vtx v e r) (Face f) -> PlaneGraph s v e f r Source #

Given the AdjacencyList representation of a plane graph, construct the plane graph representing it. All the adjacencylists should be in counter clockwise order.

running time: \(O(n)\)

makeCCW :: (Num r, Ord r) => Gr (Vtx v e r) f -> Gr (Vtx v e r) f Source #

Orders the adjacencylists of a plane graph (with \(n\) vertices) (in Adj repr) so that they are all counter-clockwise around the vertices.

running time: \(O(n \log n)\)

# Orphan instances

(ToJSON v, ToJSON e, ToJSON f, ToJSON r) => ToJSON (PlaneGraph s v e f r) Source # | |

toJSON :: PlaneGraph s v e f r -> Value # toEncoding :: PlaneGraph s v e f r -> Encoding # toJSONList :: [PlaneGraph s v e f r] -> Value # toEncodingList :: [PlaneGraph s v e f r] -> Encoding # | |

(FromJSON v, FromJSON e, FromJSON f, FromJSON r) => FromJSON (PlaneGraph s v e f r) Source # | |

parseJSON :: Value -> Parser (PlaneGraph s v e f r) # parseJSONList :: Value -> Parser [PlaneGraph s v e f r] # |