0
$\begingroup$

I am trying to describe a novel type of DAG's construction algorithm. The directed edges of the graph corresponds to a partial ordering: i.e. any directed edge $e$ spanning from $f$ to $t$ also observes: $f \preceq t$.

Q: How can I precisely define the main task of edge construction: that is finding the node $f$ for a given $t$?

It is something like this:

find all $f_a \in \{ f_i \}$ s.t. $f_a \preceq t$ $\land \nexists f_j$ s.t. $f_i \preceq f_j$

but I'm not sure if this is sufficient or even understandable?

Some Background

Without getting too specific: the DAG itself is that of an executed program, and is used for dynamic runtime analysis. Each node represents the execution of some event, while an edge $e = f \rightarrow t$ means that $f$ triggered $t$.

$\endgroup$

1 Answer 1

0
$\begingroup$

If you represent the DAG as an adjacency list, where each node links to all of its predecessors, you can find all predecessors by iterating over that list.

If you represent the DAG as an adjacency list, where each node links to all of its successors, you can easily construct a list of predecessors in a linear-time (iterate over all nodes and all successor lists, and create the predecessor lists). Then see above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.