The world in which the graph lives

We can take the dual of a world. For the Primal this gives us the Dual, for the Dual this gives us the Primal.

The Dual of the Dual is the Primal.

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.

Shorthand for vertices in the primal.

The type to reprsent FaceId's

Shorthand for FaceId's in the primal.

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.

Get the embedding, reprsented as a permutation of the darts, of this graph.

Get the dual graph of this graph.

lens to access the Dart Data

edgeData is just an alias for dartData

Helper function to update the data in a planar graph. Takes care to update both the data in the original graph as well as in the dual.

The function that does the actual work for updateData

Reorders the edge data to be in the right order to set edgeData

Traverse the vertices

(^.vertexData) $ traverseVertices (i x -> Just (i,x)) myGraph Just [(VertexId 0,()),(VertexId 1,()),(VertexId 2,()),(VertexId 3,())] >>> traverseVertices (i x -> print (i,x)) myGraph >> pure () (VertexId 0,()) (VertexId 1,()) (VertexId 2,()) (VertexId 3,())

Traverses the darts

>>> traverseDarts (\d x -> print (d,x)) myGraph >> pure ()
(Dart (Arc 0) +1,"a+")
(Dart (Arc 0) -1,"a-")
(Dart (Arc 1) +1,"b+")
(Dart (Arc 1) -1,"b-")
(Dart (Arc 2) +1,"c+")
(Dart (Arc 2) -1,"c-")
(Dart (Arc 3) +1,"d+")
(Dart (Arc 3) -1,"d-")
(Dart (Arc 4) +1,"e+")
(Dart (Arc 4) -1,"e-")
(Dart (Arc 5) +1,"g+")
(Dart (Arc 5) -1,"g-")

Traverses the faces

>>> traverseFaces (\i x -> print (i,x)) myGraph >> pure ()
(FaceId 0,())
(FaceId 1,())
(FaceId 2,())
(FaceId 3,())

Construct a planar graph

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

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

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

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)\)

Get the number of vertices

>>> numVertices myGraph
4

Get the number of Darts

>>> numDarts myGraph
12

Get the number of Edges

>>> numEdges myGraph
6

Get the number of faces

>>> numFaces myGraph
4

Enumerate all vertices

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

Enumerate all vertices, together with their vertex data

Enumerate all darts

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-")

Enumerate all edges. We report only the Positive darts

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+")

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

running time: \(O(1)\)

The vertex this dart is heading in to

running time: \(O(1)\)

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

running time: \(O(1)\)

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

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

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

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

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

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

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

running time: \(O(1)\)

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

running time: \(O(1)\)

Data corresponding to the endpoints of the dart

Data corresponding to the endpoints of the dart

running time: \(O(1)\)

The dual of this graph

>>> :{
 let fromList = V.fromList
     answer = fromList [ fromList [dart 0 "-1"]
                       , fromList [dart 2 "+1",dart 4 "+1",dart 1 "-1",dart 0 "+1"]
                       , fromList [dart 1 "+1",dart 3 "-1",dart 2 "-1"]
                       , fromList [dart 4 "-1",dart 3 "+1",dart 5 "+1",dart 5 "-1"]
                       ]
 in (computeDual myGraph)^.embedding.orbits == answer
:}
True

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

Does the actual work for dualGraph