Reduce the size complexity of removeEdge

[snowleopard]

Reduce the size complexity of removeEdge

[snowleopard]

After #37, we have the following improvement:

g = clique [2,2,0,1,0,0,2,1,2,1,0,1,2,0,2,0,0,0,0,2,1,1,0,2,2,0,2,0,0,2,1,2,0
           ,2,0,1,1,2,0,0,0,1,2,1,0,1,1,2,2,0,2,2,2,1,0,0,1,2,0,1,0,0,2,0,2]

> size g
66

> size (removeEdge 0 1 g)
155

We also have a guarantee that the size of the resulting expression is at most 3x + 3 of the original. This is a very pessimistic worst case which only applies to strange cliques like in the above example (and also very small graphs like vertex 0 due a bunch of extra empty leaves -- this should be fixed). Here are several more realistic examples:

> p = path [1..10]
> size p
19
> size (removeEdge 5 6 p)
25

> q = path [1..100]
> size q
199
> size (removeEdge 50 51 q)
205

> r = clique [1..10]
> size r
11
> size (removeEdge 5 6 r)
24

> s = clique [1..100]
> size s
101
> size (removeEdge 50 51 s)
204

That is, if s does not have many connections (like in path) then the cost of removeEdge s is negligible. If s has a lot of connections (like in clique) then the cost of removeEdge s is around 2x. For most other graphs the cost is between 1x and 2x.

[snowleopard]

After merging #49, the results got better, but the worst case still remains at 3x, and I don't know how to improve it -- the last example below demonstrates the problem. I believe this is a rather rare case.

> g = clique [2,2,0,1,0,0,2,1,2,1,0,1,2,0,2,0,0,0,0,2,1,1,0,2,2,0,2,0,0,2,1,2,0
           ,2,0,1,1,2,0,0,0,1,2,1,0,1,1,2,2,0,2,2,2,1,0,0,1,2,0,1,0,0,2,0,2]

> size g
65

> size (removeEdge 0 1 g)
125

> p = path [1..10]
> size p
18
> size (removeEdge 5 6 p)
19

> q = path [1..100]
> size q
198
> size (removeEdge 50 51 q)
199

> r = clique [1..10]
> size r
10
> size (removeEdge 5 6 r)
19

> s = clique [1..100]
> size s
100
> size (removeEdge 50 51 s)
199

> z = clique [1,2,3,4,5,6,7,8,9,1]
> size z
10
> size (removeEdge 1 5 z)
26

Anyway, I'm satisfied for now, so I'm closing this issue.