Rosetta Code

User:Realazthat/Notes/Scrap

< User:Realazthat‎ | Notes
Revision as of 23:14, 8 January 2011 by rosettacode>Realazthat (→‎Better algorithm)

Du

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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)\neq0\right)\rightarrow\left(d\left(C,E,F,p,q,r,s\right)\neq0\right)\end{array}} {\min} c\left(C,E,p,q,r,s\right)\\ \end{array} }

Naive algorithm

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

If we know something about the size of E, we can improve the complexity. For example, in SAT when converted to DHC, all of the variable graph nodes will have a maximum of 3 edges leading in, and 3 out: Each node is connected to the node to the left, and to the right, and possibly to a clause node. The only nodes that have more than this are the clause nodes themselves, which will have m incoming edges, and m outgoing edges, where m is the number of variables in that clause. Thus, it is bounded by the number of variables in the problem. For 3SAT, it is additionally bounded by three, and for k-SAT, by k. Converting from DHC to UHC splits the incoming edges to one node and outgoing to another. Thus, for a k-SAT problem, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |E| \in O(k|G|)} instead of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |E| \in O(\left|G\right|^{2})} .

As we iterate over the different possible values for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} , there are incrementally more possibilities for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (r,s)} . Each selection of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (r,s)} implies a possible breakpoint for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p,r)} .

For each q, for all the valid (r,s) for that q, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_{q}} will track those that result in no breakpoint for (p,r).

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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\} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{q}} will track those s, valid with q, that result in a breakpoint (p,r) that is a former breakpoint.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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\} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{q}} will track those s, valid with q, that result in a breakpoint (p,r) that are not a former breakpoint.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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\} }

The nice thing about these three sets, is that they can be incrementally calculated. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_{q} = T_{q+1} \cup \left\{C_{q+1}\right\}} and so on for U and V. Basically, iterate through each possible q (O(|G|), and for each q, determine which sets the two new possibilities (r,s) go into (O(1) time), and insert them (O(log |G|) time, or O(1) if hashset or similar structure; we will assume O(1)).


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{q}} is a set that contains the adjacent vertices to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{q}} in G.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{q} = \left\{ v : (C_{q},v) \in E \right\} }

All Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{i}} can be precalculated in a large table D, for all i in O(|G|^2) time, and be retrieved in O(1).

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_{q}} is a set that contains those adjacent vertices to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{q}} in G, which don't form a breakpoint in F, the set of former main breakpoints. In other words, all v, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (v,C_{q}) \in E \wedge (v,C_{q}) \notin F} .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_{q} = \left\{ v \in D_{q} : f(F,v,C_{q})=0 \right\} }

Calculating Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_{q}} takes a maximum of O(|G|) time, since there can be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |G|^2} edges in E, each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{q}} can have a maximum of O(|G|) adjacent vertices recorded, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_{q}} is linear to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{q}} . However, for k-SAT problems, we can assume that each node has a maximum of k adjacent nodes, making Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |D_{q}| \in O(k)} , thus making the calculation and size of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_{q} \in O(k)} .


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\left(C,F,E,p\right) = \min_{q \in C} W(C,F,E,q) }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W(C,F,E,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} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_{0}\left(C,F,E,q\right) \in \left\{0,1,2,\infty\right\} = \begin{cases} 0 & \text{if } \left|T_{q} \backslash D_{q}\right| \not= 0 \text{,}\\ 1 & \text{else if } \left( \left|T_{q} \cap H_{q} \right| \not=0 \vee \left| V_{q} \backslash 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} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_{1}\left(C,F,E,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} \backslash D_{q} \right| \not=0 \vee \left| V_{q} \backslash 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} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_{2}\left(C,F,E,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}| \not=0 \right) \text{,}\\ 3 & \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} }

Perform an operation

New edges:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_{e}(C,p,q,r,s) = \left\{ (C_{p},C_{r}), (C_{q},C_{s}), (C_{p-1},C_{q+1}) \right\} }

Broken edges:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_{e}(C,p,q,r,s) = \left\{ (C_{p-1}, C_{p}), (C_{q},C_{q+1}) (C_{r}, C_{s}) \right\} }

Next cycle:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C^{2}\left(C,M,E_{e},p,q,r,s\right) = \begin{cases} C^{2_{pq}}(C,p,q,r,s) & \text{if } b(C_{p-1},C_{q+1}) = 1 \wedge f(C_{p-1},C_{q+1}) = 0 \text{,}\\ C^{2_{pr}}(C,p,q,r,s) & \text{else if } b(C_{p},C_{r}) = 1 \wedge f(C_{p},C_{r}) = 0 \text{,}\\ C^{2_{qs}}(C,p,q,r,s) & \text{else if } b(C_{q},C_{s}) = 1 \wedge f(C_{q},C_{s}) = 0 \text{,}\\ C^{2_e}(C,p,q,r,s,m \in M \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) )) & \text{else if } M \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) ) \not= \emptyset\\ C^{2_e}(C,p,q,r,s,e \in E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) )) & \text{else if } E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s) ) \not= \emptyset\\ C & \text{otherwise} \end{cases} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C^{2_{pq}}(C,p,q,r,s) = \begin{cases} < [C_{q+1}, C_{r}], [C_{p},C_{q}], [C_{s}, C_{p-1}] > & \text{if } (r < s) \text{,}\\ < [C_{q+1}, C_{s}], [C_{q},C_{p}], [C_{r}, C_{p-1}] > & \text{if } (r > s) \text{,}\\ \end{cases} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C^{2_{pr}}(C,p,q,r,s) = \begin{cases} < [C_{p},C_{q}], [C_{s}, C_{p-1}], [C_{q+1}, C_{r}] > & \text{if } (r < s) \text{,}\\ < [C_{r}, C_{p-1}], [C_{q+1}, C_{s}], [C_{q},C_{p}] > & \text{if } (r > s) \text{,}\\ \end{cases} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C^{2_{qs}}(C,p,q,r,s) = \begin{cases} < [C_{s}, C_{p-1}], [C_{q+1}, C_{r}], [C_{p},C_{q}] > & \text{if } (r < s) \text{,}\\ < [C_{q},C_{p}], [C_{r}, C_{p-1}], [C_{q+1}, C_{s}] > & \text{if } (r > s) \text{,}\\ \end{cases} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_{e}^{2}(E_{e},C,p,q,r,s) = E_{e} \backslash (B_{e}(C,p,q,r,s) \backslash N_{e}(C,p,q,r,s)) }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M^{2}(M,C,p,q,r,s) = (M \backslash B_{e}(C,p,q,r,s)) \cap N_{e}(C,p,q,r,s) }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F^{2}(F_{e}, M,C,p,q,r,s) = F \cap M^{2}(M,C,p,q,r,s) }

Retrieved from "https://rosettacode.org/wiki/User:Realazthat/Notes/Scrap?oldid=168874"