Design advice / suggestions

[Simon Parten]

Here's my problem. 

• Relatively small completely connected, acyclic digraph.  (Maybe 10 nodes)...
• Each node "transforms" it's input in topological order
• Inputs are of type "scenario"
• Each node transforms it's inputs (this transformation may be complex) and spits out two scenarios
• "transform" and "complement"
• The edge type will define which of these "scenarios", (transform or complement) is passed into the next along the edge
• If C~>A, B~>A, then the two scenarios on the edge will need to be "combined" before being transformed by A. The transfrom of any node in the graph may be "of reporting interest".

I've had some success with the docs. I think I've managed to constrain the graph to be connected, directed and acyclic. 

I believe I can figure out the topological order 

http://www.scala-graph.org/guides/core-traversing.html

But I'm havng a bit of a head scratcher on the last two points, how to select out the scenario of interest from the edge, and do the scenario combination before entry into the next node in the graph. 

Any design / algorithmic advice for this set of requirements?

Regards,

Simon

[Peter Empen]

Simon,

Let's clarify first what you mean by "node input" of type "Scenario"? "Input" with respect to which operation?

For instance, are you traversing the DAG while supplying some input at any node? Who is consuming the transformation results?

[Simon Parten]

Er, right, having read back my post I can see some holes. Let's say we have that small graph  C~>A, B~>A, A~>D. 

C ->

        A -> D

B->

B and C will be "scenario generators" - in the sense that they will generate some "scenario". Lets's have a simple scenario, where A generates 22, and B generates 15. ***

A has some "complicated" operation, something like quotient remainder mod 10. So if we "apply" A to the scenario generated by C, we'd get (2, 2), and for B (1, 5). 

"Scenarios" also have some canonical "combine" operation - in this case "addition"... but it's important that inputs are "combined" before processing. So for this "scenario", A(27) = (2, 7). 

Now, what happens in D? We need to decide whether to feed it the quotient or remainder. We choose that via as a property of the edge that the "scenario tuple" (7,2) "travels" along.

So if D was quotient / remainder 2, then we'd get either (3, 1) or (1, 0)...depending on whether our edge held a "quotient" or "remainder" property.

Does this clarify what I'm trying to achieve?

Regards, 

Simon

*** Really, A and B would generate (22, 0), and B (15, 0)... the edges would select 22 and 15, because it wouldn't make sense to select the "complement" of a "generator"

**** And really really in the domain of interest, there is a 3rd output, which is basically a "report" on the outcome of that particular node, but the "report" is not passed on in the digraph. Ideally, there would be a way to access it however...

[Simon Parten]

Sorry... the bottom of the above post is wrong. B & *C* are the scenario generators. 

[Peter Empen]

Yeah, understood. You are doing kinda topo-order-specific fold. Here is what comes to my mind:

Node Type

At first glance it seams, that the position of a given node determines what you need to calculate when touching it. So in case it is a root node (node with no predecessor) it generates a scenario. Otherwise it just transforms the scenarions of its predecessors. If so you may go with a single type. Otherwise you should opt for an ADT of nodes.

Edge Type

You told the node transformation also depends on some information provided by the incoming edge. This makes me recommend an ADT for your edges. If you prefer "property graphs" go with labeled edges where labels of an enumeration type stand for the edge type.

Algorithm

Check whether the layers you get as the result of the topological sort work out for your fold. Level 0 nodes will be generators. For all other nodes you should pick up their respective predecessors which are guaranteed to be contained in one of the proceeding layers...

[empen...@gmail.com]

Check out the enhanced support for edge ADTs in version 2!