User:Realazthat/Notes/Scrap

Du

${\begin{array}{lcl}C&=&{\text{Cycle modular sequence of vertices}}\\E&=&{\text{Edges set/matrix}}\\F&=&{\text{Former main breakpoints set/matrix}}\\u,v&=&{\text{Vertices in a graph}}\\p,q,r,s&=&{\text{Indices in a sequence}}\\(C_{p},C_{p-1})&=&{\text{Current main breakpoint}}\\\left[p,q\right]\in C&=&{\text{Segment to cut, ranged from }}p{\text{ to }}q{\text{ in }}C\\\left(r,s\right)\in C&=&{\text{Pair of neighboring vertices representing an edge to insert the segment in between}}\\b\left(E,u,v\right)\in \left\{0,1\right\}&=&{\begin{cases}0&{\text{if }}\left(u,v\right)\in E\\1&{\text{if }}\left(u,v\right)\notin E\end{cases}}\\f\left(EF,u,v\right)\in \left\{0,1\right\}&=&{\begin{cases}0&{\text{if }}\left(u,v\right)\in F\\1&{\text{if }}\left(u,v\right)\notin F\end{cases}}\\c\left(C,E,p,q,r,s\right)\in \left\{0,1,2,3\right\}&=&b\left(E,C_{p-1},C_{q+1}\right)+b\left(E,C_{q},C_{s}\right)+b\left(E,C_{p},C_{r}\right)\\d\left(C,E,F,p,q,r,s\right)\in \left\{0,1,2,3\right\}&=&f\left(E,F,C_{p-1},C_{q+1}\right)+f\left(E,F,C_{q},C_{s}\right)+f\left(E,F,C_{p},C_{r}\right)\\b,c,d,f\in O\left(1\right)\\\end{array}}$

${\begin{array}{lcl}m\left(C,F,E,p\in C\right)\in \left\{0,1,2,3,\infty \right\}&=&{\underset {\begin{array}{c}q,r,s\in C\\\left(r\notin [p,q]\right)\wedge \left(s\notin [p,q]\right)\wedge \left(\left|s-r\right|=1\right)\\\left(c\left(C,E,p,q,r,s\right)\neq 0\right)\rightarrow \left(d\left(C,E,F,p,q,r,s\right)\neq 0\right)\end{array}}{\min }}c\left(C,E,p,q,r,s\right)\\\end{array}}$

Naive algorithm

$m\left(C,F,E,p\right)\in O\left(\left|n\right|^{2}\right)$

newedgdes(C,p,q,r,s):
  return { (C[p-1],C[q+1]), (C[q],C[s]), (C[p], C[r]) }

countbps(E,NE):
  newbps = 0
  for ( ne in NE )
    if ( ne !in E )
      ++newbps
  return newbps


countmainbps(F,E,NE):
  newmainbps = 0
  for ( ne in NE )
    if ( ne !in E && ne in F )
      ++newmainbps
  return newmainbps



m(C,F,E,p):
  min = infinity
  n = |C|
  for ( q in range(p,p-2) )
    for ( s in range( q + 2, p ) )
      r = s - 1
      for ( i in range(2) )
        NE = newedges(C,p,q,r,s)
        if ( |NE| != 0 )
          newbps = countbps(F,E,NE)
          newmainbps = countmainbps(F,E,NE)
          
          if ( newbps == 0 || newmainbps > 0 )
            min = newbps < min ? newbps : min
       
        swap(r,s)
  return min

Better algorithm

As we iterate over the different possible values for $q$, there are incrementally more possibilities for $(r,s)$. Each selection of $(r,s)$ implies a possible breakpoint for $(p,r)$.

For each q, for all the valid (r,s) for that q, $T_{q}$ will track those that result in no breakpoint for (p,r).

$T_{q}=\left\{C_{s}:s\notin [p,q]\wedge \exists _{r,|r-s|=1,r\notin [p,q]}\left[b(E,C_{p},C_{r})=0\right]\right\}$

$U_{q}$ will track those s, valid with q, that result in a breakpoint (p,r) that is a former breakpoint.

$U_{q}=\left\{C{s}:s\notin [p,q]\wedge \exists _{r,|r-s|=1,r\notin [p,q]}\left[b(E,C_{p},C_{r})=1\wedge f(E,F,C_{p},C_{r})=1\right]\right\}$

$V_{q}$ will track those s, valid with q, that result in a breakpoint (p,r) that are not a former breakpoint.

$V_{q}=\left\{C{s}:s\notin [p,q]\wedge \exists _{r,|r-s|=1,r\notin [p,q]}\left[b(E,C_{p},C_{r})=1\wedge f(E,F,C_{p},C_{r})=0\right]\right\}$

$D_{q}$ is a set that contains the adjacent vertices to $C_{q}$ in G.

$D_{q}=\left\{v:(C_{q},v)\in E\right\}$

$H_{q}$ is a set that contains those adjacent vertices to $C_{q}$ in G, which don't form a breakpoint in F, the set of former main breakpoints. In other words, all v, where $(v,C_{q})\in E\wedge (v,C_{q})\notin F$.

$H_{q}=\left\{v\in D_{q}:f(F,v,C_{q})=0\right\}$ $W(q)\in \left\{0,1,2,3,\infty \right\}={\begin{cases}W_{0}(q)&{\text{if }}b(E,C_{p-1},C_{q+1})=0{\text{,}}\\W_{1}(q)&{\text{if }}b(E,C_{p-1},C_{q+1})=1\wedge f(F,C_{p-1},C_{q+1})=0{\text{,}}\\W_{2}(q)&{\text{if }}b(E,C_{p-1},C_{q+1})=1\wedge f(F,C_{p-1},C_{q+1})=1\end{cases}}$

$W_{0}\left(q\right)\in \left\{0,1,2,\infty \right\}={\begin{cases}0&{\text{if }}\left|T_{q}/D_{q}\right|\not =0{\text{,}}\\1&{\text{else if }}\left(\left|T_{q}\cap H_{q}\right|\not =0\vee \left|V_{q}/D_{q}\right|\not =0\right){\text{,}}\\2&{\text{else if }}\left(\left|U_{q}\cap H_{q}\right|\not =0\vee \left|V_{q}\cap D_{q}\right|\not =0\right){\text{,}}\\\infty &{\text{otherwise}}\end{cases}}$

$W_{1}\left(q\right)\in \left\{1,2,3,\infty \right\}={\begin{cases}1&{\text{if }}\left|T_{q}/D_{q}\right|\not =0{\text{,}}\\2&{\text{else if }}\left(\left|T_{q}\cap D_{q}\right|\not =0\vee \left|U_{q}/D_{q}\right|\not =0\vee \left|V_{q}/D_{q}\right|\not =0\right){\text{,}}\\3&{\text{else if }}\left(\left|U_{q}\cap D_{q}\right|\not =0\vee \left|V_{q}\cap D_{q}\right|\not =0\right){\text{,}}\\\infty &{\text{otherwise}}\end{cases}}$

$W_{2}\left(q\right)\in \left\{2,3,\infty \right\}={\begin{cases}2&{\text{if }}\left|T_{q}\cap H_{q}\right|\not =0\vee \left(|V{q}/D{q}|\right){\text{,}}\\3&{\text{else if }}\left(\left|U_{q}\cap H_{q}\right|\not =0\vee \left|V_{q}/D_{q}\right|\not =0\right){\text{,}}\\\infty &{\text{otherwise}}\end{cases}}$