Data.PlaneGraph.IO

Converting from/to Adjacency Representation of the plane graph

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)

Reads a plane graph from a bytestring

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

Writes a plane graph to a bytestring

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

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

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

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)

Methods

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)

Methods

parseJSON :: Value -> Parser (PlaneGraph s v e f r)

parseJSONList :: Value -> Parser [PlaneGraph s v e f r]