Graph Issues

[lhstrh]

Currently, we encode dependencies using a dependency graph. We are considering inverting the polarity of the edges, effectively turning it into a precedence graph. Before going ahead with this, we need to:

• understand all current uses of the graph
• understand whether changing the polarity will have algorithmic disadvantages
• come up with an API that we like
• stick to clear terminology across the code base
• Migrate DOT notation to mermaid.js
• ......

[axmmisaka]

Current API:

interface DependencyGraph<T>{
    // Map nodes to the set of nodes that they depend on.
    // Namely, the key is the effect and the value is the set of its origins
    adjacencyMap: Map<T, Set<T>>;

    // Merge two dependency graphs; 
    merge: (apg: DependencyGraph<T>) => void;
    // Add a node T
    addNode: (node: T) => void;
    // Given a `node` T denoting effect, return a set of its origins
    // TODO1: change the name, `getOrigins` maybe?
    // This is best achieved with a dependency graph. Called 6 times in reactor.ts
    getEdges: (node: T) => Set<T>;
    // Given a `node` denoting origin, return a set of its effects
    // TODO1: We MUST rename because "back edge" is very confusing and has a different meaning in graph theory.
    // This is best achieved with a precedence graph. Called 4 times in reactor.ts
    getBackEdges: (node: T) => Set<T>;

    // Return the subset of origins that are reachable from the given effect.
    // We should change the signature. presence of `origins` is confusing. It appears that it is effectively taking intersection with the actual reachable vertices.
    // Best achieved with a precedence graph. Never called anywhere.
    // Maybe change the recursion to be iteration.
    reachableOrigins: (effect: T, origins: Set<T>) => Set<T>;

    // Return if the graph has cycle.
    // Only called in Reactor::canConnect()
    hasCycle: () => boolean;

    // Remove a node and all associated origin/effect relationship with it.
    // Should be the same with precedence graph or dependency graph, as if we don't implement both it's gonna traverse the whole graph either way.
    // Only called in Reactor::_deleteConnections()
    removeNode: (node: T) => void;


    // The following 3 doesn't relate too much with the polarity as one can just invert the arguments
    // Add an edge that denotes node->dependson; `dependsOn` is the origin and `node` effect
    addEdge: (node: T, dependsOn: T) => void;

    // Never called
    // TODO: Change name. Reason idem.
    addBackEdges: (node: T, dependentNodes: Set<T>) => void;
    // Called once in Reactor::_recordDeps()
    // Can refactor it to just call `addEdge` multiple times
    addEdges: (node: T, dependsOn: Set<T>) => void;

    // Remove node->dependsOn edge
    // Called two times in reactor.ts
    removeEdge: (node: T, dependsOn: T) => void;

    // Returns [|V|, |E|], never used
    size: () => [number, number];

    nodes: () => IterableIterator<T>;

    // Returns the DOT representation of the graph. Currently it is a dependency graph,
    // but cognitively it might be better to invert the polarity of the graph and make it a precedence graph?
    toString: () => string;

    // Return a set of verticies that are root in the **precedence** graph,
    // i.e. leaf in the **dependency** graph,
    // i.e. that does not affect on others, i.e. that are not effects and purely origins.
    // Maybe rename it to "pureOriginNodes"? Very confusing
    // Never used
    rootNodes: () => Set<T>;

    // Return a set of verticies that are leaf in the **precedence** graph,
    // i.e. root in the **dependency** graph,
    // i.e. that does not depend on others, i.e. that are not origins and purely effects.
    // Maybe rename it, very confusing
    // Used once in `_analyzeDependencies` to collapse the graph.
    leafNodes: () => Set<T>;
}

Understand all current uses of the graph
There are two places this graph is actually used to make decisions:

1. In Reactor::_analyzeDependencies(), called only by Reactor::_start(). It uses leafNodes() to shrink the graph and check if it has cycles with SortableDependencyGraph<T>::updatePriorities.
2. In Reactor::canConnect, called by Reactor::_connect() and Reactor::_connectMulti() (this one is never called in tests) to check if new source/destination will introduce cycles.
   And the DOT representation that is printed from time to time.

Understand whether changing the polarity will have algorithmic disadvantages
For now, it appears to be that it will, and if we decide to store only one direction, dependency graph would be a better idea as algorithms that runs better on a dependency graph are called more frequently.

Come up with an API that we like
I would say the current API is kinda fine, some things that needs to be changed

1. Rename, i.e. stick to clear terminology, currently it is very confusing and misleading
2. Rewrite the implementations if possible; use iteration instead of recursion?

Stick to clear terminology across the code base
Yes

Some other questions:

1. Is SortableDependencyGraph necessary? The only time it got used appears to be checking if the graph has cycle? Anyway, since the graph is assumed to be a DAG it would not be hard to linearise.
2. Do we want to try saving certain graph properties (such as pure origin vertices), and update them on-the-fly as we update the graph, instead of calculating them every time?
3. We should also see if we want to re-write Reactor::_analyzeDependencies() because it appears that it contains a LOT of code that either breaks the abstraction barrier or is very confusing