Continue Passing Style (CPS) when plotting

Question

I am working on a library for split surfaces. To represent the cell topology, I use a certain data structure with a breakdown of the vertex table (see the diagram on the left).

During the construction of the grid, which can also be viewed as a graph, it creates nodes that should point to others that do not yet exist (see the diagram on the right side - the dashed arrow represents future links). The classic solution is to create a node with a null pointer, and then update it when you create another. Since I am working on Haskell :), and I don’t want to go to the dark side of the code (impurity), I wonder if it is possible to build a grid (graph) without updating the data. I assume that CPS (Continuation Passing Style) can do the job, but I cannot figure out a way.

Is it just a dream?

UPDATE

Let me clarify my question a bit. I am looking for a method for creating nodes with direct links (pointers), and for a direct link - intermediate tables or maps. Just a simple data definition:

data Mesh = Edge Vertex Mesh Mesh Vertex | Ground 

If I am not mistaken, and if it is feasible, CPS will provide efficient creation (without node updates) and efficient cross (without searching on maps) graphics. On the other hand, the schedule will become completely unchanged, i.e. One change should spread across the entire graph, for example. change tail list.

Am I really wrong? If not, how to do it?

Answer 1

What you need is a method known as node binding . He uses a lazy grade to do his job. No need for CPS.

Suppose you can identify each node with some unique identifier (string, integer, or any other). Suppose also that when creating a node, you already know the identifiers of all the nodes it points to, regardless of whether they are created or not. Then you can use this technique.

You produce the string nodes :: Data.Map NodeID Node through your graph creation functions (use the additional exclusive monad). When you create a node, you add it to the map. When you create an edge that should point to a node named x , you use fromMaybe $ lookup nodes x . It does not matter if a node with the name x is already created or will be created in the future. While it is being created at some point, you are tuned. It will only be removed from the card when you need it.

This is how I used to create a graph from its text description. Perhaps there are other, better ways.

If when creating a node you do not know the identifiers of all the nodes that your node points to, you need to slightly modify this method, for example. go from the node ID to the list of your neighbors on the map and build each list step by step.

You should be careful and avoid evaluating lazy values ​​before you finish plotting.

Answer 2

It does not use CPS ... but I am working on a planar graph library for Haskell using a similar scheme to what you described above. Edges are added by specifying which existing front comes before or after it.

The actual implementation of the graph is performed, resulting in binary serialization working and working (using PLANAR_CODE for beginners, possibly Graph6 and Sparse6) and a few additional things.

You are currently getting a double graph (which you seem to have drawn as well) with a separate function, although I am considering the possibility of double-calculating each time you add an edge (assuming a connected graph).

The code can be obtained from darcs get http://code.haskell.org/~ivanm/planar-graph/ ; A usage example (which I am developing for this library) is at http://code.haskell.org/~ivanm/dangd/ .

---

Taken from the Haddock documentation as an example of its use:

For example, let g refer to the following graph (where n1 , etc. are both labels and variable names):

  ==== ==== ( n1 ) ( n2 ) ==== ==== ==== ( n3 ) ==== 

We can add an edge between n1 and n2 (using Anywhere as EdgePos , since there are currently no edges on 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 parameters for the location on n2 :

• Use Anywhere : since there is only one other edge, it does not make a difference in terms of nesting where the second edge goes.

• Place the new edge BeforeEdge e2 (clockwise around n2 ).

• Place the new AfterEdge e2 edge (clockwise around n2 ).

Since n2 has only one edge, all three EdgePos values ​​will lead to the same graph, so we can arbitrarily choose one:

  ((e3,e4),g'') = addEdge n2 (BeforeEdge e2) n3 Anywhere "e3" "e4" g' 

However, with more edges, care must be taken at which EdgePos value is used. Received Count:

  e2 ==== <--------------- ==== ( n1 ) ( n2 ) ==== ---------------> ==== e1 | ^ | | e3 | | e4 | | v | ==== ( n3 ) ==== 

The same graph (up to the actual values ​​of Edge , so it will not satisfy == ) would be obtained with:

  ((e4,e3), g'') = addEdge n3 Anywhere n2 (BeforeEdge e2) "e4" "e3" g' 

Answer 3

You don't seem to need to keep the link to NextA and NextB within Edge. Since this is something that can be calculated by walking along the current Edge, why not write a function that takes Edge and return its edge NextA / NextB, which are analogous to a diagram based on the clockwise direction of parts of Edge A and B.