StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>When you say you're "storing the priorities, in degrees and out degrees", it suggests you don't quite grok adjacency matrices. For an adjacency matrix M, vertices correspond to indices, and edges from <em>v</em> to <em>u</em> correspond to an entry in the matrix at M<sub>vu</sub> (i.e. M<sub>vu</sub> is the number of edges from <em>v</em> to <em>u</em>). The out-degree of a vertex <em>v</em> is ΣM<sub>*v</sub>; the in-degree is ΣM<sub>v*</sub>. If the matrix is in row-major order (M<sub>row, col</sub>), these correspond to the column and row sums, respectively. </p> <p>"Priority" isn't a vertex property in plain DAGs. If you have priorities associated with the vertices, your graph class should contain another data structure mapping vertices to priorities (probably a vector, since vertices are usually numbered consecutively). Better still, have two graph classes: a <code>DAG</code> class, and a child <code>PriorityDAG</code> class that adds a priority property for nodes:</p> <pre><code>class DAG { public: typedef int Vertex; ... }; class PriorityDAG : public DAG { public: using DAG::Vertex; typedef int Priority; Priority priority(Vertex vertex); protected: std::vector<Priority> priorities; ... }; </code></pre> <p>If you're ever going to have other types of graphs (undirected, cyclic), you can make a <code>Graph</code> class to be the parent of <code>DAG</code>.</p> <p>Thus, to insert an edge, increment the value M<sub>vu</sub>. If <em>v</em> is a parent of <em>u</em>, then there is an edge from <em>v</em> to <em>u</em>, so M<sub>vu</sub> > 0.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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