Announcing planar-graph

I’ve been working on a new planar graph library on and off for just over the past year.

I realise that this might not be exactly a much-sought-after library, but I’ve been using this as a test-bed for various ideas I’ve been having for a “normal” graph library. I’m going to discuss various aspects of the design of this library and some ideas I’ve had for an extensible graph library.

What is a graph?

The standard definition of a graph is as follows:

a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V (i.e., an edge is related with two vertices, and the relation is represented as unordered pair of the vertices with respect to the particular edge).

However, this definition is rather limiting: by assuming that an edge is comprised of a two-element subset of the vertices, we make it harder for us to consider it computationally: in practice we don’t have a data-structure that represents a two-element set. In practice, we instead tend to use something like (Node,Node). However, this isn’t ideal:

• Using this representation implicitly makes graphs directed rather than undirected, unless you do a lot more bookkeeping by checking both elements of the tuple. In practice this may not be too much of a problem, as people want directed graphs, but this doesn’t make it perfect.

• The directionality of an edge is now part of its definition rather than being a property of the edge: that is, whether the edge is meant to be directed or not should be a value that can be determined from the edge; currently all edges are directed and undirected graphs are simulated with two inverse edges.

• Multiple edges become difficult to handle: if you want to delete an edge between node n1 and node n2 and there are three edges there, how do you know which one to delete? In practice, the answer seems to be “all of them”.

A more preferable definition was stated by W. T. Tutte in a 1961 paper:

A graph G consists of a set E(G) of edges and a (disjoint) set V(G) of vertices, together with a relation of incidence which associates with each edge two vertices, not necessarily distinct, called its ends. An edge is a loop if its ends coincide and a link otherwise.

Note that no indication is given of E being a set of two-sets: instead, a mapping exists between every e ∈ E to the two endpoints of that edge.

Planar graphs

A planar graph is a graph that can be drawn on a specified surface (usually a plane or a sphere) such that no edges intersect/cross except at their endpoints.

When considering a planar graph programmatically, we also want to take into account their embedding (i.e. where all the edges adjacent to a node are in relation to each other). As such, just using an approach of identifying edges solely by their end points fails completely if there are multiple edges. As such, using a unique identifier for each edge is preferable.

But the difficulty of endpoint identification (i.e. distinguishing between (n1,n2)) remains. As such, several implementations of planar graphs use two identifiers for each edge. More about this later.

Library implementation

As I said earlier, I’ve been using the development of this library as a way to experiment with various approaches to how to design a graph library, all of which I intend to use in a non-planar graph library.

Abstract node identifiers

Most existing graph libraries (e.g. Data.Graph and fgl) use a type alias on Int values to represent vertices/nodes. Furthermore, when considering how to create a graph, it requires that you:

1. Explicitly come up with new node identifier for each new node;

2. Make sure you don’t re-use an existing identifier.

Whilst this isn’t a big problem if considering a bulk creation of a graph (i.e. you have some arbitrary [a] representing the nodes and edges represented as [(a,a)], in which case a zip-based solution can be used to assign node identifiers, etc. though it would be a tad messy), it isn’t ideal for adding new nodes on after the fact and it is also open to abuse.

As such, planar-graph does not permit users to create node identifiers: the constructor isn’t exported, it isn’t an instance of Enum or Bounded, etc. Instead, you provide the label for the new node you want to add and the function returns the updated graph and the identifier for the new node. When the node identifiers are changed for some reason (e.g. merging two graphs), a function is returned that allows you to update the values of any node identifiers you’ve been storing elsewhere.

Show and Read instances are available and leak some of the internals out, but you have to really be persistent to try and abuse them to create your own identifier values: you need to explicitly call read on the String to get it to parse as the result isn’t valid Haskell code (as the instances exist solely for debugging).

Half-edges

As intimated earlier, each edge is actually represented by two half-edges: an edge from n1 to n2 is “stored” twice: one half-edge n1 -> n2 and its inverse n2 -> n1 (this also includes loops). Each half-edge has its unique identifier (which is abstract, just as with nodes) and mapping function exists that lets you determine a half-edge’s inverse.

Most graph implementations are something like a newtyped version of:

type Graph = Map Node [Node]

where each node has information on its adjacent nodes. Or, if we consider a graph with labels, we have:

type LabelledGraph n e = Map Node (n, [(Node,e)])

Instead, the definition of planar-graph looks more like (just considering the labelled version):

type PlanarGraph n e = ( Map Node (n, [Edge])
                       , Map Edge (Node, e, Node, Edge)
                       )

where a mapping exists between a half-edge identifier and the corresponding node that it comes from, the label of that half-edge, the node that it is going to and its inverse half-edge. This definition matches the mathematical ones stated earlier much more closely.

Now, this half-edge usage might be a requirement for a planar graph data structure, but it is also viable for non-planar graphs. First of all, if we wished to allow multiple edges between two nodes, then the traditional representation must be altered slightly:

type LabelledGraph' n e = Map Node (n, [(Node,[e])])

Each edge representation now keeps a list of edge labels, one per edge between the two nodes. Extra bookkeeping is required about what to do when that list becomes empty (and in fact previous fgl versions had an implementation where this list wasn’t considered at all and thus multiple edges would silently fail).

Also, consider how fgl-style graphs are implemented:

type FGLGraph n e = Map Node ([(Node,e)], n, [(Node,e)])

Here, each node stores not only the outgoing edges but also the incoming edges for efficiency reasons (otherwise we’d need to traverse all edges in the graph to determine what the incoming edges are). This also leads to possible data corruption issues as each edge label is stored twice.

However, with our half-edge implementation, neither of these points need any change: each multiple edge has its own unique identifier, and to obtain the incoming edges we just determine the inverse of all the outgoing edges (though technically this point isn’t quite valid when considering directed graphs, as planar-graph treats them differently; see the next section).

Distinguishing between structure and content

Most graph implementations conflate the structure of the graph (i.e. which nodes and edges there are) with the information that graph is representing. One example is the question of graph orientation: in fgl, a graph can be considered to be undirected if each edge is represented twice; however, it is quite possible that such a graph is not undirected but just happens to have each directed edge having an inverse (e.g. some kind of flow algorithm).

Whilst it is not fully formalised as yet, in planar-graph the orientation of a graph is dictated by its half-edge labels: in my use case that prompted the development of this library, I had a need for mixed-orientation of a graph: one half-edge pairing might have had a fixed direction on one half-edge whilst its inverse had a label of “InverseEdge“; other pairings might both have some kind of partial edge label.

But the actual edge identifiers didn’t change: I could apply a mapping function to transform all edge labels to () and thus make the graph “undirected”, but I didn’t need to change the actual structure of the graph to do so.

I believe this is a much more useful way of considering graphs, where the information that the graph represents can be found in the node and edge labels, not the identifiers.

Serialisation and encoding

I needed to be able to encode my planar graphs using various binary encodings (e.g. PLANAR_CODE, described in Appendix A here). Now, I could have written custom encoding functions from a PlanarGraph to a ByteString for every possible encoding; however, since they all follow the same basic underlying structure, I decide to utilise an intermediary list-based representation.

However, I then realised that this representation could also be used for Show and Read instances for the graphs as well as pretty-printing functions. The definition of the representation is:

[( node index
 , node label
 , [( edge index
    , node index that this edge points to
    , edge label
    , inverse edge index
   )]
)]

For Show, Read, etc. this is basically a raw dump of the graph (which means it is technically open to abuse as the internals of the abstract identifiers are accessible this way, but I had to draw the line somewhere); the deserialise function that is utilised by Read also ended up being useful for an internal function rather than manually trying to construct a graph!

For encoding/decoding of binary representations, a re-numbering of the identifiers according to a breadth-first traversal is first undertaken (as many require that the identifiers be 0 ... n-1 and for decoding the order of edges for each node is important) and then the same structure is used. A class is then used to convert the graph into this representation and then convert it to the encoding of your choice.

However, not all of the encodings require that the graph be planar: whilst a breadth-first traversal doesn’t make as much sense for non-planar graphs, the same framework could be used for other graph types.

Plans for the new graph library

I haven’t even started to prototype this, as some of the ideas I’m listing below I only started to mentally flesh out over the past few days. However, I think that it should work and will provide a useful approach to dealing with graphs in Haskell.

The root of my idea is that we often have different properties that we want graphs to hold: should it be a directed graph? What should the identifier types be? Is there any way to automatically determine all nodes with a certain label (e.g. for graph colouring)? What kind should the graph have?

The current methods of dealing with such a thing is to have a graph implementation, and just live with it. This “solution” clearly has problems, not least of which is that if you try to do anything else you have to re-implement everything yourself.

However, consider this: we have a method of generalising monads via monad transformers: why not do the same thing with graphs?

Now, I’m not the first person to think of this; Edward Kmett has already released a library that has this kind of characteristic (though his classes differ from how I’m planning on structure/distinguish them by having them more implementation-based than property-based IMO).

What my plans entail is this:

• Define a GraphTransformer class. Not only will graph transformers be instances of this class, but so will the actual graph types (with identities for the different lift/unlift functions):

  class (Graph (SubGraph gt)) => GraphTransformer gt where
      type SubGraph gt :: *
  
      .....
  

• The Graph class then requires that the instance type also be an instance of GraphTransformer, and has default definitions of all methods using the lift/unlift functions. These default definitions will resolve down to f = f definitions for actual graph types, but for transformers will just apply the function down the stack.

  This class only defines “getters”: e.g. determine the size of the graph, get all its nodes or edges, etc.

• Other classes are defined as sub-classes of Graph, again using lift/unlift functions from GraphTransformer for default definitions of the methods.

• Most classes (except for where it’s necessary, e.g. a class defining mapping functions) will assume that the graph is of kind *.

• Most transformers will assume that the underlying graph is of kind * -> * -> * (i.e. that you can specify node and edge labels) so that you can make the transformer an instance of any class that requires kind * -> * -> *, but it should be possible to make transformers that take in a graph of kind *.

• Because of the default definitions using lift/unlift functions, most class instances for the graph transformers will be of the form instance Graph (MyTransformer ExistingGraph a b); this means that if you want to newtype your graph transformer stack, writing the instances will be trivial (albeit rather repetitive and boring).

  As such, if a transformer only effects one small aspect of graph manipulation (e.g. a transformer that keeps a Map of node labels to node IDs so you can more efficiently look up all nodes that have a particular label), then you only need to provide explicit definitions for those classes and methods (in this case, adding and deleting nodes and looking up node identifiers based upon labels rather than filtering on the entire list of nodes).

  However, this does mean that any kind of unique operation you can think of (e.g. in the example above the ability to find all identifiers for nodes that have a particular label), you will need to create a new class and make appropriate instances for underlying types (if possible) and existing transformers (so that if you put extra transformers on the stack you can still use the improved definitions for this transformer).

• Usage of the serialisation and encoding functionality for all graphs. This will provide Show/Read instances for graphs, pretty-printing, easy Binary instances (using the serialised form) and any available encodings specified.

  The actual method of this may change from what I’ve described above, as whilst a breadth-first traversal of a planar graph is unique up to the first edge chosen, for non-planar graphs this isn’t the case. However, for encodings that don’t assume a planar graph this shouldn’t be a problem.

• Whilst the provided underlying graph types might use abstract node identifiers, it will not be required for instances of Graph to do so (and a transformer will be provided to let you specify your own type, that under-the-hood maps to the generated abstract identifiers). However, I can’t see a way around having edges using some kind of abstract edge identifier, as it isn’t as common to attach a unique label to each edge.

Generally, transformers will utilise the node and edge labels of the underlying graph stack to store extra metadata (e.g. directionality of the edges); this is why the transformers will typically require that the underlying type is of kind * -> * -> *. However, the question then arises: should users be aware of these underlying type transformations? For example, should this information leak out with a Show instance?

My current thinking is that it shouldn’t: the output from Show, prettyPrint, etc. should be as if there were no transformers being used. The main counter-example I can think of is to have some kind of indicator whether each listed half-edge is the “real” one or not, especially when using a transformer that makes it a directed edge (though in this case it can be solved by only listing the “primary” half-edges and not their inverses; this again works for most graph types but not planar ones, as all half-edges need to be listed for the graph to be re-created due to the embedding of edge orders).

Assuming this all works (I plan on starting playing with it next week), I think this approach will do quite well. As you’re writing your code, if you use a newtype/type alias for your graph type, you can just add or remove a transformer from your stack without affecting usage (in most cases: some transformers might change which classes a stack can be used in; e.g. a transformer that lets you specify node identifiers will require using a different class for adding nodes than one that generates and returns identifiers for you). Then at the end if you want to try and tweak performance, you can always go and write custom transformers (or indeed your own graph type if you want to merge all the functionality in to the actual type without using transformers) without having to change your code.

If this all works as I think/hope it will… 😉