From Rosetta Code
Revision as of 23:19, 8 January 2011 by rosettacode>Realazthat (→‎Better algorithm)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


Naive algorithm

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

  newbps = 0
  for ( ne in NE )
    if ( ne !in E )
  return newbps

  newmainbps = 0
  for ( ne in NE )
    if ( ne !in E && ne in F )
  return newmainbps

  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
  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, instead of .

As we iterate over the different possible values for , there are incrementally more possibilities for . Each selection of implies a possible breakpoint for .

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

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

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

The nice thing about these three sets, is that they can be incrementally calculated. 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)).

is a set that contains the adjacent vertices to in G.

All can be precalculated in a large table D, for all i in O(|G|^2) time, and be retrieved in O(1).

is a set that contains those adjacent vertices to in G, which don't form a breakpoint in F, the set of former main breakpoints. In other words, all v, where .

Calculating takes a maximum of O(|G|) time, since there can be edges in E, each can have a maximum of O(|G|) adjacent vertices recorded, and is linear to . However, for k-SAT problems, we can assume that each node has a maximum of k adjacent nodes, making , thus making the calculation and size of .

Perform an operation

New edges:

Broken edges:

Next cycle: