-2
$\begingroup$

I need a formalism to describe the following requirements:

  • I have a graph comprised of nodes and transitions between nodes
  • Nodes maybe one of three types, all are sub-classes of a base abstract node type
  • Activity nodes have one transition in and one out
  • Wrapper nodes have one transition in and one out
  • Routing nodes may have multiple transitions in and multiple transitions out
    • Routing nodes can either behave as AND-join, AND-split, OR-split, OR-join depending on how they are configured
    • Routing nodes can simultaneously be a join and a split, but not a join and a join, or a split and a split (obviously, since it can only join or split in one way)
  • There are no cycles.
  • There is only one root node - always a wrapper node - this is a source.
  • Any node can be a sink/leaf where it has no outgoing transitions
  • the terms Activity, Wrapper and Routing are just arbitrary names for classes in my graph that exhibit different behaviour and different semantics in terms of connecting them together
  • the terms AND-join etc describe the way transitions connect to routing nodes - so AND-join means more than one transition is incoming. AND-split is where there are multiple outgoing transitions, OR-split is where there are multiple potential outgoing branches but only one is chosen, and OR-join is multiple potential transitions incoming, but only one is chosen.

I have almost no experience of formal models, though I'm guessing I need to use set notation and logical symbols.

What would a formalisation of the above requirements look like?

Thanks for any advice.

Improve this question
$\endgroup$
26
  • $\begingroup$ Apologies in advance if these terms are well-defined in some particular branch of CS, but I want to ask: (1) What is the distinction between an 'activity node' and a 'wrapper node'? (2) What do you mean by 'AND-join', 'AND-split', etc.? (3) is is meant to be obvious whether the root is a source or a sink for the graph? $\endgroup$ – Niel de Beaudrap Sep 11 '10 at 11:07
  • $\begingroup$ I have amended, I hope this is a little clearer. $\endgroup$ – flesh Sep 11 '10 at 11:43
  • 3
    $\begingroup$ If your question is really “how you formally describe a rooted, directed, graph,” the answer is “Read any textbook on graph theory.” I do not think that your question is that simple. $\endgroup$ – Tsuyoshi Ito Sep 11 '10 at 20:47
  • 2
    $\begingroup$ Petri nets aren't just graphs, they also express a notion of flow of tokens. When you talk of "branches being chosen", it sounds you want a Petri-like semantics that goes beyond the description of the graphs. $\endgroup$ – Charles Stewart Sep 12 '10 at 8:26
  • 1
    $\begingroup$ As Charles points out, this fits well into the Petri net framework. en.wikipedia.org/wiki/Petri_net $\endgroup$ – András Salamon Sep 12 '10 at 17:28
1
$\begingroup$

Judging from the strictness of the requirements, I believe there is no formal name for all those requirements. I would call it a directed tree (the term polytree seems to be valid according to wikipedia, but I have never seen it being used).

I have used graphs that are close to your description in distributed computing scheduling, where we just called them "graphs" or maybe "scheduling graphs". In these graphs, there were two classes of nodes : The "branch" nodes are like the routing nodes you describe and there is also activity nodes, which usually depict "activity" or "computing" done in a processor.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Did you have a formal specification, particularly of the branch nodes? $\endgroup$ – flesh Sep 12 '10 at 11:55
  • $\begingroup$ I looked at my parallel computing notes. The graphs were also called "scheduling precedence graph" . Unlike wikipedia's example for databases, our graphs were always acyclic. The branch nodes were also called fork and joins, but that was for our own convenience, not formalization. $\endgroup$ – chazisop Sep 13 '10 at 1:50

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.