Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If you're looking for <code>topological sort</code>, you can also do this, given an <a href="http://en.wikipedia.org/wiki/Adjacency_list" rel="nofollow noreferrer">adjacency list</a> (or a list of edges <code>(u,v)</code> which you can preprocess in <code>O(E)</code> time):</p> <pre><code>list top_sort( graph in adjacency list ) parent = new list queue = new queue for each u in nodes parent(u) = number of parents if ( parent(u) is 0 ) // nothing points to node i queue.enqueue( u ) while ( queue is not empty ) u = queue.pop add u to visited for each edge ( u, v ) decrement parent(v) // children all have one less parent if ( parent(v) is 0 ) queue.enqueue( v ) </code></pre> <p>Given an <code>adjacency list</code> (or a list of edges <code>(u,v)</code>), this is <code>O( V + E )</code>, since each edge is touched twice - once to increment, once to decrement, in <code>O(1)</code> time each. With a normal queue, each vertice will also be processed by the queue at most twice - which can be done also in <code>O(1)</code> with a standard queue.</p> <p>Note that this differs from the DFS (at least a straight-up implementation) in that it handles forests.</p> <p>Another interesting note is that if you substitute <code>queue</code> with a <code>priority_queue</code> imposing some sort of structure/ordering, you can actually return the results sorted in some order.</p> <p>For example, for a canonical class dependency graph (you can only take class X if you took class Y):</p> <pre><code>100: 101: 100 200: 100 101 201: 202: 201 </code></pre> <p>you would probably get, as a result:</p> <pre><code>100, 201, 101, 202, 200 </code></pre> <p>but if you change it so that you always want to take lower numbered classes first, you can easily change it to return:</p> <pre><code>100, 101, 200, 201, 202 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POneed a graph algorithm similar to DFS
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USLarry
    1. USLarry
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    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. VTUpMod
    1. This table or related slice is empty.
 

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