Graph data structures and journal format for mini-IDE

Posted by matec on Programmers See other posts from Programmers or by matec
Published on 2014-02-08T17:02:07Z Indexed on 2014/06/09 21:39 UTC
Read the original article Hit count: 279

Filed under:

Background:

I am writing a small/partial IDE. Code is internally converted/parsed into a graph data structure (for fast navigation, syntax-check etc). Functionality to undo/redo (also between sessions) and restoring from crash is implemented by writing to and reading from journal. The journal records modifications to the graph (not to the source).

Question:

I am hoping for advice on a decision on data-structures and journal format.

For the graph I see two possible versions:
g-a Graph edges are implemented in the way that one node stores references to other nodes via memory address
g-b Every node has an ID. There is an ID-to-memory-address map. Graph uses IDs (instead of addresses) to connect nodes. Moving along an edge from one node to another each time requires lookup in ID-to-address map.

And also for the journal:
j-a There is a current node (like current working directory in a shell + file-system setting). The journal contains entries like "create new node and connect to current", "connect first child of current node" (relative IDs)
j-b Journal uses absolute IDs, e.g. "delete edge 7 -> 5", "delete node 5"

I could e.g. combine g-a with j-a or combine g-b with j-b. In principle also g-b and j-a should be possible.

[My first/original attempt was g-a and a version of j-b that uses addresses, but that turned out to cause severe restrictions: nodes cannot change their addresses (or journal would have to keep track of it), and using journal between two sessions is a mess (or even impossible)]

I wonder if variant a or variant b or a combination would be a good idea, what advantages and disadvantages they would have and especially if some variant might be causing troubles later.

© Programmers or respective owner

Related posts about data-structures