Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It's from a project management theory (or scheduling theory, I don't know the exact term). There the task is about sorting jobs (vertex is a job, arc is a job order relationship).</p> <p>Obviously we have some connected oriented graph without loops. There is an arc from vertex <code>a</code> to vertex <code>b</code> if and only if <code>a</code> hates <code>b</code>. Let's assume there is a source (without incoming arcs) and destination (without outgoing arcs) vertex. If that is not the case, just add imaginary ones. Now we want to find length of a longest path from source to destination (it will be number of rows - 1, but mind the imaginary verteces).</p> <p>We will define vertex rank (<code>r[v]</code>) as number of arcs in a longest path between source and this vertex <code>v</code>. Obviously we want to know <code>r[destination]</code>. Algorithm for finding rank:</p> <pre><code>0) r_0[v] := 0 for all verteces v repeat t) r_t[end(j)] := max( r_{t-1}[end(j)], r_{t-1}[start(j)] + 1 ) for all arcs j until for all arcs j r_{t+1}[end(j)] = r_t[end(j)] // i.e. no changes on this iteration </code></pre> <p>On each step at least one vertex increases its rank. Therefore in this form complexity is <strong><code>O(n^3)</code></strong>. </p> <p>By the way, this algorithm also gives you student distribution among rows. Just group students by their respective ranks.</p> <p><strong>Edit:</strong> Another code with the same idea. Possibly it is better understandable.</p> <pre><code># Python # V is a list of vertex indices, let it be something like V = range(N) # source has index 0, destination has index N-1 # E is a list of edges, i.e. tuples of the form (start vertex, end vertex) R = [0] * len(V) do: changes = False for e in E: if R[e[1]] &lt; R[e[0]] + 1: changes = True R[e[1]] = R[e[0]] + 1 while changes # The answer is derived from value of R[N-1] </code></pre> <p>Of course this is the simplest implementation. It can be optimized, and time estimate can be better.</p> <p><strong>Edit2:</strong> obvious optimization - update only verteces adjacent to those that were updated on the previous step. I.e. introduce a queue with verteces whose rank was updated. Also for edge storing one should use adjacency lists. With such optimization complexity would be <strong><code>O(N^2)</code></strong>. Indeed, each vertex may appear in the queue at most <code>rank</code> times. But vertex rank never exceeds <code>N</code> - number of verteces. Therefore total number of algorithm steps will not exceed <strong><code>O(N^2)</code></strong>.</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm to establish ordering amongst a set of items
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USdragonfly
    1. USdragonfly
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POAlgorithm to establish ordering amongst a set of items
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COHi, is there a possibility I can get some help understanding your code? It looks a little exotic for me to grasp it properly. Some kind of a pseudo code maybe?
      singulars
      1. PO
      1. USSkylark
    2. COYep, it's kind of pseudocode. Actually I wanted to express it more like a mathematical one. `For all` there is for universal quantifier. So the idea is just to spread the maximum possible rank value through the verteces.
      singulars
      1. PO
      1. USdragonfly
    3. COUpdated the post with equivalent code in Python.
      singulars
      1. PO
      1. USdragonfly
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload