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:
- Start with node 0 with associated empty set
C(0) = {} - 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) } - 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:
- Prove there are no circles in the graph
- Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.
- 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).- Create algorithm to find B in simple case where n = 1.
- 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.
