<p>If you insist that the edges in the complex merge equation don't appear twice (eg. that the <code>+</code> you use is actually a disjunctive union), and you only subtract sets that are superset of one another (*), I think the assertion you want to prove (4) is actually false. Imagine RTG with 5 vertices and 6 edges:</p>
<pre><code>V = { 0, a, b, c, d }
E = { (0,a), (0,b), (a,c), (a,d), (b,c), (b,d) }
</code></pre>
<p>now, if <code>To = c</code> and <code>F = d</code>: <code>C(c)</code> contains already all the edges except <code>(b,d)</code> and <code>(c,d)</code>, So <code>Sum (Fi-Bi)</code> has to be exactly those edges. Since these edges are only contained in <code>C(d)</code>, they must be (not necessarily both) contained in summand <code>d-B</code> for some <code>B</code>. But that is not possible, because whatever <code>B</code> we choose, we add also edges that are already in <code>C(To)</code>.</p>
<p>(*) otherwise the assertion (2) is actually false: <code>Result = To + (From - To)</code> satisfies the simple merge equation for all <code>From</code> and <code>To</code> (even if it looks bizarre).</p>
<p>Long story short: You gave inadequate or incomplete definitions.</p>
<blockquote>
<p>Q: Why do we have to state definitions rigorously if the proofs are usually trivial if the definitions are right?</p>
<p>A: The definitions are almost always wrong.</p>
</blockquote>

CC BY-SA 3.0
2013-01-09T08:34:42.383Z
You are absolutely right, the definition is not adequate and congratulations to finding minimal graph to show the problem with non-existing base. I'm at work on fixing the definition of the problem.
Jiri Klouda
CC BY-SA 3.0
2013-01-09T02:33:07.900Z
2013-01-09T02:33:07.900Z
2020-06-17T09:38:08.363Z
jpalecek
<p>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. C(x) contains all edges on all paths from a node 0 ( C(0) = {} ). Each edge can be in a set at most once!</p>

<p>You can also describe this data structure by the rules for its growth:</p>

<ol>
<li>Start with node 0 with associated empty set <code>C(0) = {}</code> = <em>creating new object</em></li>
<li>For any node x create a new node y where (x,y) is oriented edge from x to y and <code>C(y) = C(x) union { (x,y) }</code> = <em>versioning and branching</em></li>
<li>For any nodes f and t, create node r, where (f,r) and (t,r) are oriented edges and <code>C(r) = C(f) union C(t) union { (f,r), (t,r) }</code> = <em>merging</em></li>
</ol>

<p>Note: You can see there is no mathematical difference between creating new version and a branch. It is a semantical difference depending on whether there is already an edge leading from the node or not. </p>

<p><strong>Base node</strong> is defined as a node b, such as <code>C(b) = C(f) intersect C(t)</code>, where f and t are nodes representing two versions to be merged. </p>

<p><strong>Simple Merge equation</strong> <code>Result=To + (From-Base)</code> = means that if we subtract every edge in C(b) from C(f) and add all edges in C(t) we get a resulting C(r) minus (f,r) and (t,r) edges exactly. No edge would appear twice and all edges in C(f) and C(t) would be represented. = <em>3-way merge</em></p>

<p><strong>Complex merge equation</strong> <code>Result = To + Sum(i=1..n) for (Fi-Bi), where Fn = From</code>. Each edge can be in exactly one of the sets To, (Fi-Bi). For n=1 this turns into a simple merge equation. In case there exist no base in simple case, we might find sequence of F,B nodes to fit the complex equation. <em>(1+2n)-way merge</em></p>

<p>I have actually several questions pertaining to this data structure. I am posing the first 3 for "frame of mind", as I already know the answers. And I believe question 4 directly leads to answering question 5, which I really try to get answered.</p>

<blockquote>
  <ol>
  <li>Prove there can be no circles in the graph</li>
  <li>Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.</li>
  <li>Create algorithm to find B in simple case where n = 1.</li>
  <li>Prove that for each RTG and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi, where i=1..n to fit the complex merge equation.</li>
  <li>Create algorithm to find minimum n and Fi,Bi for i=1..n where n > 1.</li>
  </ol>
</blockquote>

CC BY-SA 3.0
2013-01-08T03:53:16.140Z
Cross-posted to [math.SE](http://math.stackexchange.com/questions/271508/revision-tracking-graph).
mhum
CC BY-SA 3.0
2013-01-09T08:27:23.083Z
I find out in my discussion in math.se that the problem is not stated correctly. I will be editing it soon.
Jiri Klouda
CC BY-SA 3.0
2013-01-11T04:54:01.203Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions.
Kaveh
CC BY-SA 3.0
2013-01-11T04:55:52.183Z
ps: please read the [FAQ] if you haven't.
Kaveh
CC BY-SA 3.0
2013-01-11T04:58:37.470Z
Kaveh, the discussion on math hit dead end pretty soon, but then I found this site and thought the question might be better suited for it. And it seems I have been right. I am doing some extra research on the problem and will update the question with all relevant information by Monday.
Jiri Klouda
CC BY-SA 3.0
2013-01-14T06:51:59.570Z
You have waited less than two days before cross posting your question here, that is not permitted by our policy. You should have waited more. I would suggest that you remove the question from [Math.SE] if you think it wasn't suitable place for the question and be more careful in future.
Kaveh
CC BY-SA 3.0
2013-01-14T12:56:27.630Z
Since you care more about following the rules than actual answers to interesting questions, I think I should move on and instead of trying to improve my question, let it be as it is, answered and all. This site was supposed to be about knowledge. Whatever. I am out of here.
Jiri Klouda
CC BY-SA 3.0
2013-03-30T16:59:53.493Z
Should not it be "cycles" rather than "circles"?
J.y B.y
CC BY-SA 3.0
2013-03-30T17:01:31.920Z
@JiriKlouda: few people  check stacks exchange every day, so declaring the theme "dead" on math after only two days seems dishonest to me, never mind the rules :(
J.y B.y
<ds.algorithms><graph-theory><graph-algorithms><ds.data-structures><directed-acyclic-graph>
Revision Tracking Graph
Jiri Klouda
# Revision Tracking Graph

(Asked by: username_0 on 2013-01-07)

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. C(x) contains all edges on all paths from a node 0 ( C(0) = {} ). Each edge can be in a set at most 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) = {}` = *creating new object*
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) }` = *versioning and branching*
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) }` = *merging*

Note: You can see there is no mathematical difference between creating new version and a branch. It is a semantical difference depending on whether there is already an edge leading from the node or not.

**Base node** is defined as a node b, such as `C(b) = C(f) intersect C(t)`, where f and t are nodes representing two versions to be merged.

**Simple Merge equation** `Result=To + (From-Base)` = means that if we subtract every edge in C(b) from C(f) and add all edges in C(t) we get a resulting C(r) minus (f,r) and (t,r) edges exactly. No edge would appear twice and all edges in C(f) and C(t) would be represented. = *3-way merge*

**Complex merge equation** `Result = To + Sum(i=1..n) for (Fi-Bi), where Fn = From`. Each edge can be in exactly one of the sets To, (Fi-Bi). For n=1 this turns into a simple merge equation. In case there exist no base in simple case, we might find sequence of F,B nodes to fit the complex equation. *(1+2n)-way merge*

I have actually several questions pertaining to this data structure. I am posing the first 3 for "frame of mind", as I already know the answers. And I believe question 4 directly leads to answering question 5, which I really try to get answered.

> 1. Prove there can be 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. Create algorithm to find B in simple case where n = 1.
> 4. Prove that for each RTG and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi, where i=1..n to fit the complex merge equation.
> 5. Create algorithm to find minimum n and Fi,Bi for i=1..n where n > 1.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, ds.data-structures, directed-acyclic-graph

> **Comments:**
> **username_1**: Cross-posted to [math.SE](http://math.stackexchange.com/questions/271508/revision-tracking-graph).  
> **username_0**: I find out in my discussion in math.se that the problem is not stated correctly. I will be editing it soon.  
> **username_2**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions.  
> **username_2**: ps: please read the [FAQ] if you haven't.  
> **username_0**: username_2, the discussion on math hit dead end pretty soon, but then I found this site and thought the question might be better suited for it. And it seems I have been right. I am doing some extra research on the problem and will update the question with all relevant information by Monday.  
> **username_2**: You have waited less than two days before cross posting your question here, that is not permitted by our policy. You should have waited more. I would suggest that you remove the question from [Math.SE] if you think it wasn't suitable place for the question and be more careful in future.  
> **username_0**: Since you care more about following the rules than actual answers to interesting questions, I think I should move on and instead of trying to improve my question, let it be as it is, answered and all. This site was supposed to be about knowledge. Whatever. I am out of here.  
> **username_3**: Should not it be "cycles" rather than "circles"?  
> **username_3**: @JiriKlouda: few people  check stacks exchange every day, so declaring the theme "dead" on math after only two days seems dishonest to me, never mind the rules :(  

---

## 1 answers

### Answer by username_4 on 2013-01-09. Score: 3 | Accepted answer

If you insist that the edges in the complex merge equation don't appear twice (eg. that the + you use is actually a disjunctive union), and you only subtract sets that are superset of one another (*), I think the assertion you want to prove (4) is actually false. Imagine RTG with 5 vertices and 6 edges:
V = { 0, a, b, c, d }
E = { (0,a), (0,b), (a,c), (a,d), (b,c), (b,d) }

now, if To = c and F = d: C(c) contains already all the edges except (b,d) and (c,d), So Sum (Fi-Bi) has to be exactly those edges. Since these edges are only contained in C(d), they must be (not necessarily both) contained in summand d-B for some B. But that is not possible, because whatever B we choose, we add also edges that are already in C(To).
(*) otherwise the assertion (2) is actually false: Result = To + (From - To) satisfies the simple merge equation for all From and To (even if it looks bizarre).
Long story short: You gave inadequate or incomplete definitions.

Q: Why do we have to state definitions rigorously if the proofs are usually trivial if the definitions are right?
A: The definitions are almost always wrong.

> **Comments:**
> **username_0**: You are absolutely right, the definition is not adequate and congratulations to finding minimal graph to show the problem with non-existing base. I'm at work on fixing the definition of the problem.  

---

