úÎPçIĞc      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abPlanar Graph data structure. Ivan.Miljenovic@gmail.comNoneZ<Specify part of a graph found by traversing it. For nodes,   == c . d .  ; the same  is true for edges except when M is used. In  that case,  may contain a sub-set of  (and if  they aren' t equal,  will be e.). )The values found whilst traversing. See  for  more specific information. All values encountered. The order in which values are  encountered. Did we skip any edges? .Different ways of traversing through a graph. FTo assist in visualising how the traversals differ, sample traversals *will be provided for the following graph:  & ===== ' ( 1 ) & ===== $ | $ a | $ | & ===== ' ( 2 ) & ===== & / | \ . b / | \ c 5 /------------- | -------------\ 6 / | \ 9 ===== d | ===== : ( 3 ) | ( 5 ) 9 ===== ===== ===== 9 | ( 4 ) / \ : | ===== / \ ; | | / \ > e | f | g / \ h = | | / \ > | | | | > | / | | > | / | | A ===== / ===== ===== B ( 6 )-----------/ ( 7 ) ( 8 ) A ===== ===== =====  0Each traversal shall start at the edge labelled a : note that Awhenever an edge is traversed, it immediately also traverses its  inverse. ,In particular, note where the node labelled 4 and its two adjacent edges are found. >The definition of a more compact, serialised form of a planar - graph. The various fields correspond to:   [( node index  , node label  , [( edge index + , node index that this edge points to  , edge label  , inverse edge index  )]  )]  @The list of edges should be in clockwise order around the node. 9Note that there will be twice as many edges lists as the size;  that'%s because each edge is listed twice. Information about a particular  . The  s that make up the face. The  s that make up the face, its  inverse and the   on the other side  of that  . &An abstract representation of a face. /Information about the faces in a planar graph. >An abstract representation of an edge. Note that an explicit C identifier is used for each edge rather than just using the two E nodes that the edge connects. This is required in case more than D one edge connects two nodes as we need to be able to distinguish  them. &An abstract representation of a node. ISpecification of where to place a new edge on a node in clockwise order. 8The new edge should be placed after the specified edge. 9The new edge should be placed before the specified edge. %The new edge can be placed anywhere. )The overall planar graph data structure. 'The number of nodes in the graph (i.e. length . nodes). 'The number of edges in the graph (i.e. length . edges). #Remove all labels from this graph. /Apply a mapping function over the node labels. /Apply a mapping function over the edge labels. !Is this node still in the graph? 6All the nodes in the graph (in some arbitrary order). ?All the nodes and their labels in the graph (in some arbitrary  order). !Is this edge still in the graph? ?All the half-edges (thus also including inverses) in the graph  (in some arbitrary order). :All the half-edges and their labels in the graph (in some  arbitrary order).  A variant of - that returns the pair of nodes that form an C edge rather than its unique identifier (again including inverse  edges). As with , but including the labels. @All the primary edges in the graph returned in arbitrary order. !=All the primary edges and their labels in the graph (in some  arbitrary order). " A variant of  . that returns the pair of nodes that form the  primary edges. #As with " but including the labels. $mergeGraphs pg1 pg2" creates a disjoint union between pg1 and  pg28 (i.e. puts them into the same graph but disconnected). > This is used when they were created independently and thus  probably have clashing Node and Edge values. For best  performance, pg1 should be larger than pg2. >Along with the merged graph, two functions are returned: they 2 respectively convert Node and Edge values from pg2 to those  found in the merged graph. %Please note that these functions are partial and should only be / used for the Node and Edge identifiers from pg2. %=Merge all the provided planar graphs together into one large C graph, and provide translation functions for every graph in the - list (the first pair in this list is just (f,f)). See $. for more information. For best performance, * the graphs should be decreasing in size/order. &"Constructs an empty planar graph. '?Add a node with the provided label to the graph, returning the * updated graph and the node identifier. (As with ' , but uses g as the label. )Add an edge between two nodes f and t. In reality, since all  edges are duplicated (see :), two half-edges are 9 inserted, and the identifiers of both are returned. For functions such as  , the first added half-edge is  assumed to be the primary one. ;If either node does not currently have any edges, then its  corresponding  value is ignored. An  of  G will place the edge before (i.e. anti-clockwise) of the last edge  added to that node. For example, let g% refer to the following graph (where  n14, etc. are both the labels and the variable names):  " ==== ==== # ( n1 ) ( n2 ) " ==== ====      " ==== # ( n3 ) " ==== We can add an edge between n1 and n2 (using  as the  5 since there are currently no edges on either node):  < ((e1,e2),g') = addEdge n1 Anywhere n2 Anywhere "e1" "e2" g )This will result in the following graph:   e2 " ==== <--------------- ==== # ( n1 ) ( n2 ) " ==== ---------------> ====  e1     " ==== # ( n3 ) " ====  If we want to add edges between n2 and n3, we have three ! options for the location on n2:  Use 2: since there is only one other edge, it makes no H difference in terms of the embedding where the second edge goes.  Put the new edge  e2 (going clockwise around n2).  Put the new edge  e2 (going clockwise around n2). Since n2( currently only has one edge, all three  values D will result in the same graph, so we can arbitrarily pick one:  E ((e3,e4),g'') = addEdge n2 (BeforeEdge e2) n3 Anywhere "e3" "e4" g' 5However, with more edges care must be taken on which  - value is used. The resulting graph is:   e2 " ==== <--------------- ==== # ( n1 ) ( n2 ) " ==== ---------------> ==== " e1 | ^ " | | % e3 | | e4 " | | " v | " ==== # ( n3 ) " ==== !The same graph (up to the actual   values; so it won' t satisfy  ==!) would have been obtained with:  F ((e4,e3), g'') = addEdge n3 Anywhere n2 (BeforeEdge e2) "e4" "e3" g' (Note, however, that now   will return e4 rather than  e3. as it is considered to be the primary edge.) *As with )., but the edges are meant to be undirected so  use the same label for both. +As with ), but both labels are set to g. ,"Determines if the graph is empty. -7Delete the node and all adjacent edges from the graph. .0Delete the edge and its inverse from the graph. /AMerges the two nodes adjoined by this edge, and delete all edges D between them. The provided function is to decide what the label ; for the resulting node should be (if the edge goes from f to  t, then the function is fLabel -> tLabel -> newLabel). The    value for the merged node is 6 pg e. ANote that this may result in multiple edges between the new node B and another node if it is adjacent to both nodes being merged. 0>Returns all outgoing edges for the specified node, travelling D clockwise around the node. It assumes the node is indeed in the  graph. 1>Returns all incoming edges for the specified node, travelling D clockwise around the node. It assumes the node is indeed in the  graph. 2*Returns the label for the specified node. 35Apply a function to the label of the specified node. 4%Set the label of the specified node. 5The  s that are connected to this   with an edge (in  clockwise order). 6The   which this   is coming from. 7The   which this   is going to. 8 The previous   going clockwise around the 6. 9 The next   going clockwise around the 6. :The  ' that is an inverse to this one; i.e.: / fromNode pg e == toNode pg $ inverseEdge pg e / toNode pg e == fromNode pg $ inverseEdge pg e ;)Return the label for the specified edge. <5Apply a function to the label of the specified edge. =%Set the label of the specified edge. >The  s that make up the face. ?The adjoining  s. Will have repeats if the  s are  adjacent over more than one  . @<Create the dual of a planar graph. If actual node and edge  labels are required, use A. A>Create the planar graph corresponding to the dual of the face  relationships. The usage of   rather than   is to allow you to use the   for constructing the , label-creation functions if you so wish.  The function eLabel for edge labels takes the   that the  edge comes from, the   belonging to that   that it is  crossing and then the  $ that it is going to. For example:  * .... ....> % ...> =====.... " (#####) ! ===== $ | ^ e2  | |  | | + face1 | | face2  | |  | |  | |  e1 v | ! ===== " (#####) % ...===== <.. ) <... .... , ... ,Here, the edge in the dual graph going from face1 to face2  will have a label of "eLabel face1 e1 face2", and the edge  going from face2 to face1 will have a label of "eLabel  face2 e2 face1". ;The returned functions are a mapping from the faces in the   6 to the nodes in the dual graph, and the edges in the C original graph to the edge in the dual that crosses it (e.g. in  the above diagram, e1& will have a mapping to the edge from  face1 to face2). B;Finds all faces in the planar graph. A face is defined by 9 traversing along the right-hand-side of edges, e.g.:   , o----------------------------->o , ^..............................| , |..............................| , |..............FACE............| , |..............................| , |..............................v , o<-----------------------------o  >(with the inverse edges all being on the outside of the edges  shown). CBReturns all nodes and edges in the same face as the provided edge A (including that edge); assumes the edge is part of the graph. D*Create the serialised form of this graph. E An alias for F% with no specified edge. Also added  are the  and  of the graph. 0This function is mainly intended for use by the  Data.Graph.Planar.Serialisation module. F@Perform a breadth-first traversal serialisation of the provided E graph. If an edge is provided, then it is the first edge and its  63 is the first node; if no edge is provided then an  arbitrary edge is chosen. 0Up to the choice of starting edge, the returned  = should be unique no matter how the graph was constructed. @Note that only one connected component is used: this is because A if there is more than one component then the serialisation is  not2 unique (due to how to choose the ordering of the  components). G>Creates the graph from its serialised form. Assumes that the  graph is valid. H7Pretty-print the graph. Note that this loses a lot of , information, such as edge inverses, etc. I"Pretty-print the graph to stdout. J>A breadth-first traversal on the sample graph would visit the - nodes and edges in the following order:  nodes: 1 2 5 4 3 8 7 6 edges: a c d b h g f e If M was used, then the edge e wouldn't be  traversed; if L was also used, then  instead f wouldn't be traversed. KBA depth-first traversal on the sample graph would visit the nodes ' and edges in the following order:  nodes: 1 2 5 8 7 4 6 3 edges: a c h g d f e b If M was used, then the edge b wouldn't be  traversed; if L was also used then instead  d wouldn't be traversed. LABy default, the traversals do so in a clockwise fashion, just as @ the outgoing edges are defined for each node. This lets you D specify that an anti-clockwise traversal should be done instead. >This is not computationally any more expensive than clockwise  traversals. MAPerform a traversal suitable for a spanning tree. In this case, < edges that reach a node that has already been visited won't be  traversed. This does7 make getting each connected component more expensive. NMerge the results from Q into one traversal (i.e. you  don'%t care about individual components). OBPerform a re-numbering of the identifiers in this graph using the @ specified traversal and optionally starting from a specified  edge. >If there is only one connected component in the graph and the E same edge is specified each time (relative to the location in the $ graph), then the re-numbering is  canonical: that is, it can be E used to compare whether two graphs constructed via separate paths ? (and thus using different identifiers) are indeed the same. PUse a J% traversal to find all the connected E components. The node and edge identifiers for each component are  re-numbered. Q>Traverse through a graph, and return each connected component B found. If an edge is specified, start with that edge and then A for subsequent components (if there are any) arbitrarily pick @ edges to start with; if no edge is provided than start at an  arbitrary edge. R?Determine if this graph is the canonical representative of the ? isomorphic class (defined as such by having a breadth-first  serialisation via F that is <= any other such  serialisation). ;The function specifies all possible starting edges for the D traversal (it is safe to leave the specified edge being returned D by this function). If there are no known unique aspects of this ( graph that could be used to minimise " uniqueness", then use the  ! function (note: you probably do not want to use    if the graph is undirected). :Note that this really only makes sense for graphs of type  PlanarGraph () ()), unless you are sure that the labels won't  affect the comparisons. S&Filter out all those graphs for which R isn't True. (For this function to be correct, no two (Edge, PlanarGraph n e) * pairs should have the same result from F. For ) example, consider the following graph g:    e1  ===== <--------- =====  ( )--------->( )  ===== / =====  | ^ / /| | ^  | | / / | |  | | / / | |  | | / / | |  | | / / | |  | | / / | |  | | / / | |  | | / / | |  | | / / | |  v | |/ / v |  ===== / =====  ( )<---------( )  ===== ---------> =====  e2  Then onlyCanonicalExamples  [(e1,g), (e2,g)] will B return both graphs, even though they represent the same graph. :Note that this really only makes sense for graphs of type  PlanarGraph () ()), unless you are sure that the labels won't  affect the comparisons. hNote that this instance of i only works when directly  applied to a j'; it is supplied solely to assist with  debugging. kThis instance of l& does not produce valid Haskell code;  however, the  ) type is abstract and not designed to be  directly accessed. mNote that this instance of i only works when directly  applied to a j'; it is supplied solely to assist with  debugging. nThis instance of l& does not produce valid Haskell code;  however, the  ) type is abstract and not designed to be  directly accessed. oNote that this instance of i only works when directly  applied to a j'; it is supplied solely to assist with  debugging. pThis instance of l& does not produce valid Haskell code;  however, the  ) type is abstract and not designed to be  directly accessed. a  !"#$%&'() The node f at which the main edge starts. Positioning information at f.  The node t at which the main edge ends. Positioning information at t for $ the inverse edge (i.e. refers to  0 t). The label for the main edge f -> t. The label for the inverse edge t -> f. $The graph at which to add the edge. The main and inverse edge  identifiers, and the updated  graph. *+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSqhkrmnsoptuvwT  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSY 0152  !"#6789:;$%&'()*+,-./34<=QPOJKLMN   >?BC@ARSDGEFHIY  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSqhkrmnsoptuvw/Internal definitions of serialisation classes. Ivan.Miljenovic@gmail.com Safe-InferedT=A class covering the different ways of encoding and decoding # planar graphs from binary data. Y>Print the required header if appropriate; otherwise return an  empty x+. Should end in a newline if appropriate. Z>Attempt to parse a header; if none exists, this should return = an appropriate default (if allowable). Should also parse % trailing newlines if appropriate. [Is each graph on a new line? yzTUVWXYZ[{|}~€‚ƒ„…†‡ˆyzTUVWXYZ[{|}~€‚ƒ„…†‡ˆyzTUVWXYZ[{|}~€‚ƒ„…†‡ˆ!Serialisation for planar graphs. Ivan.Miljenovic@gmail.com Safe-Infered\;Encode a list of planar graphs to file using the specified  encoding. ];Encode a list of planar graphs to file using the specified ; encoding, with the serialisation traversing from the an  optionally specified edge. ^/Read in a file containing encoded graphs. The T ! argument is only used for its type to determine which parser to  use. \]^ TUVWXYZ[\]^ TUVWXYZ[\]^\]^Implementation of PLANAR CODE. Ivan.Miljenovic@gmail.com Safe-Infered_BPLANAR_CODE is the most common encoding for planar graphs, and is C supported by various generation and visualisation tools. It is a 6 binary format and not intended to be human-readable. /The default encoding only supports graphs with <256 nodes, and  takes  2*|E|+|N|+1 bytes per graph.  Please note that PLANAR_CODE is not suitable for graphs with D multiple loops on vertices (multiple edges with distinct endpoints G however are catered for). As such, no guarantees are made about what  happens with multiple loops. _`‰_`_`_`‰Implementation of ASCII CODE. Ivan.Miljenovic@gmail.com Safe-Infereda*ASCII_CODE is a human-readable variant of  *Data.Graph.Planar.Serialisation.PlanarCode. The same caveats E regarding loops apply, but it is only able to represent graphs with  <=26 nodes. abŠabababŠ‹      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeeffghijklmnojpqjrstjuvjpwxjyz{|}~€‚ƒ„…†‡ˆ‰Š‹Œ‘’“”•–—˜™š›planar-graph-1.0.0.0Data.Graph.PlanarData.Graph.Planar.Serialisation*Data.Graph.Planar.Serialisation.PlanarCode)Data.Graph.Planar.Serialisation.AsciiCode(Data.Graph.Planar.Serialisation.InternalGraphTraversalTraversedValuesvisited traversed anyMissing TraversalSerialisedGraphFaceInfo faceNodes edgeCrossingsFaceFaceMapEdgeNodeEdgePos AfterEdge BeforeEdgeAnywhere PlanarGraphordersizeunlabelmapNodesmapEdgeshasNodenodeslabNodeshasEdge halfEdges labHalfEdgeshalfEdgesBetweenlabHalfEdgesBetweenedgeslabEdges edgesBetweenlabEdgesBetween mergeGraphsmergeAllGraphsemptyaddNodeaddUNodeaddEdgeaddEdgeUndirectedaddUEdgeisEmpty deleteNode deleteEdge contractEdge outgoingEdges incomingEdges nodeLabeladjustNodeLabel setNodeLabel neighboursfromNodetoNodeprevEdgenextEdge inverseEdge edgeLabeladjustEdgeLabel setEdgeLabel faceEdgesadjoiningFacesmakeDualtoDualgetFacesgetFace serialiseserialTraversal serialiseBFS deserialiseprettify prettyPrint breadthFirst depthFirstantiClockwiseTraversalspanningTraversalmergeGraphTraversalsrenumberconnectedComponentstraversecanonicalExampleByonlyCanonicalExamplesPlanarEncodingNLabelELabelputSGgetSGputNamegetName sepByNewlineencodePlanarFileencodePlanarFileFromdecodePlanarFile PlanarCode AsciiCodecontainers-0.4.2.1Data.SetfromListbase Data.FoldabletoListghc-prim GHC.TypesTrueGHC.Baseid Data.Monoidmempty $fReadFaceGHC.ReadReadString $fShowFaceGHC.ShowShow $fReadEdge $fShowEdge $fReadNode $fShowNode$fNFDataFaceInfo$fNFDataEdgeInfo$fNFDataNodeInfo$fNFDataPlanarGraph$fReadPlanarGraph$fShowPlanarGraph$fFunctorPlanarGraphblaze-builder-0.3.1.0'Blaze.ByteString.Builder.Internal.TypesBuilderSerialisedEdgeSerialisedNodenodeSer nodeLabelSer nodeEdgesSer withEdgesSer edgeIDSer toNodeSer edgeLabelSerinverseEdgeSer processPC neighbourList applyUntil groupSortBygroupSortCollectByswap$fPlanarEncodingPlanarCode$fPlanarEncodingAsciiCode