Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Consider a layout as follows:</p> <p><img src="https://i.stack.imgur.com/3bsRk.jpg" alt="enter image description here"></p> <p>An adjacency list can be implemented as an array of [Nx4] (n being 3 in this case, and 4 because you are saying that 4 is the maximum number of edges in your case) in the following form:</p> <pre><code>2 3 0 0 3 0 0 0 0 0 0 0 </code></pre> <p>the above representation assumes that the number of vertices are in sorted order where first index into the array is given by <code>(v-1)</code>.</p> <p>Incidence list on the other hand, requires you to define a vertex list, an edge list and connection elements in between (<a href="https://stackoverflow.com/questions/3904103/graph-incidence-list-implementation">incidence list - graph</a>).</p> <p>Both are good in terms of space usage compared to an adjacency matrix since your graph is very sparse, as you stated.</p> <p>My suggestion would be to go with the adjacency list, which you can initialize as an [Nx4] contiguous array in the memory (since you are saying that you will have at most 4 edges for one vertex). This representation will be faster to initialize. (<strong>Also, this representation will perform better in terms of cache efficiency.</strong>)</p> <p>However, if you expect the size of your graph changing dynamically and frequently, incidence lists might be better since they are generally implemented as lists which are non contiguous spaces (see the link above). De-allocation and allocation of the adjacency array might be undesirable in that case.</p>
    singulars
    1. This table or related slice is empty.
    1. POSparse Graph Implementation & Performance in C++
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USmeyumer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POSparse Graph Implementation & Performance in C++
      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. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COInteresting, haven't thought about representing an adj list like this - good to know, since another thing I was worried about (but didn't mention) was cache performance. The resulting matrix (aka adjacency list repr) will still be quite sparse but is definitely going to use less space than a vector-of-linked-list kind of representation that requires a lot of pointers.
      singulars
      1. PO
      1. UScompandu
    2. CODefinitely this contiguous representation will behave much better in terms of cache performance. let me add that to the answer.
      singulars
      1. PO
      1. USmeyumer
 

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