# Revision Tracking Graph

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it, which contains all edges leading into it on all paths from a node 0 (node with empty set). Each edge can be in a set exactly once!

You can also describe this data structure by the rules for its growth:

1. Start with node 0 with associated empty set C(0) = {}
2. For any node x create a new node y where (x,y) is oriented edge from x to y and C(y) = C(x) union { (x,y) }
3. For any nodes f and t, create node r, where (f,r) and (t,r) are oriented edges and C(r) = C(f) union C(t) union { (f,r), (t,r) }

Those rules can be described by words as 1) creating new object 2) branching and versioning 3) merging. You can see that the only difference between branching and versioning is whether there already is an edge leading from a node or not.

You can further differentiate the graph by naming branches (paths in the graph).

Base node is defined as a node b, such as C(b) = C(f) intersect C(t). For short: Result=(From-Base)+To. In other words, if you remove all edges in C(b) from C(f) and add edges from C(t), the resulting set would have every edge exactly once and all edges from C(f) and C(t) would be present in C(r).

I have actually several questions pertaining to this data structure:

1. Prove there are no circles in the graph
2. Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.
3. Prove that for each graph and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi where Fn = F and R = T + Sum(i=1..n) of (Fi-Bi).
4. Create algorithm to find B in simple case where n = 1.
5. Create algorithm to find Fi,Bi for i=1..n where n > 1.

I know the answers to 1,2 and 4, but I put them here to get you in the mood of working with this data structure. Have fun with it, pose additional problems and find answers. Any new answers could significantly advance the theory behind revision control systems.

• "Have fun with it" is not really a question... are you posing these questions as a puzzle/research problem? – Douglas S. Stones Jan 6 '13 at 12:54
• Explanation: Edges represent changes, Nodes represent versions and C(x) is a set of all changes contained in version x. (2) Proves 3-way merge is not always sufficient and simple base sometimes cannot be found in complex RTG. Finding base to solve the equation makes possible for 3-way merge tool to merge a change. – Jiri Klouda Jan 6 '13 at 12:59
• Well, there are 5 questions in there. I'm mainly putting it here so I don't have to repeat all the definition when talking with various mathematician friends and to have a single place for discussing the problem and in hopes someone on this site who I don't know can come up with the answers to questions 3 and 5. – Jiri Klouda Jan 6 '13 at 13:02
• Definition of base is not clear. What are $f$, $t$ and $r$ there? Are $+$ and $-$ same as set operations union and difference? – polkjh Jan 6 '13 at 16:13
• Cross-posted to cstheory: cstheory.stackexchange.com/questions/14991/… – Jukka Suomela Jan 9 '13 at 12:53