<p>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).</p>

<p>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. </p>

CC BY-SA 2.5
2010-09-12T11:55:59.873Z
Did you have a formal specification, particularly of the branch nodes?
flesh
CC BY-SA 2.5
2010-09-13T01:50:58.237Z
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.
chazisop
CC BY-SA 2.5
2010-09-12T07:25:18.483Z
2010-09-12T07:25:18.483Z
chazisop
<p>I need a formalism to describe the following requirements:</p>

<ul>
<li>I have a graph comprised of nodes and transitions between nodes</li>
<li>Nodes maybe one of three types, all are sub-classes of a base abstract node type</li>
<li>Activity nodes have one transition in and one out</li>
<li>Wrapper nodes have one transition in and one out</li>
<li>Routing nodes may have multiple transitions in and multiple transitions out
<ul>
<li>Routing nodes can either behave as AND-join, AND-split, OR-split, OR-join depending on how they are configured</li>
<li>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)</li>
</ul></li>
<li>There are no cycles.</li>
<li>There is only one root node - always a wrapper node - this is a source.</li>
<li>Any node can be a sink/leaf where it has no outgoing transitions</li>
<li>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</li>
<li>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.</li>
</ul>

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

<p>What would a formalisation of the above requirements look like?</p>

<p>Thanks for any advice. </p>

CC BY-SA 2.5
2010-09-11T11:07:22.217Z
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?
Niel de Beaudrap
CC BY-SA 2.5
2010-09-11T11:43:06.103Z
I have amended, I hope this is a little clearer.
flesh
CC BY-SA 2.5
2010-09-11T11:56:00.927Z
This does clarify your question somewhat. I gather that your network describes a process in which multiple paths can be taken in parallel (the 'AND'-split), and may re-unite in different ways (the 'AND'-join); and in which one path among many may have to be chosen at different times (the 'OR'-split). But what does it mean to choose one 'incoming' transition among many? Do you mean to invoke some sort of scheduling process with a process lock of some sort?
Niel de Beaudrap
CC BY-SA 2.5
2010-09-11T11:58:48.053Z
Exactly, You have decribed it better than I have. "Choose" is probably the wrong word - it just means only one branch is active on incoming. In other words, despite the existence of multiple incoming transitions at a routing node, only one is ever executed in practice.
flesh
CC BY-SA 2.5
2010-09-11T12:01:06.340Z
Why the downvote? It would be nice if someone could explain what is wrong with this question? Thanks.
flesh
CC BY-SA 2.5
2010-09-11T12:06:40.933Z
To elaborate on my previous comment: the first thing you may need to do is to formalize (i.e. describe the pertinent features of)  the path-formation, or branching, process in this network.
Niel de Beaudrap
CC BY-SA 2.5
2010-09-11T12:12:09.080Z
I'm not sure how I go about this, that's my problem - what might an axiom look like? I'm guessing I might need to describe Nodes and Paths, then the branching processes as you say, but I'm not clear how.
flesh
CC BY-SA 2.5
2010-09-11T12:23:21.930Z
Using new terms before you define them will lose people.  You use "AND-split" long before you say what it means.  Also, I'm still not sure you resolved all the issues brought up by Niel de Beaudrap's first comment.  Also also, what do you need this formalism to do? The application matters.
Aaron Sterling
CC BY-SA 2.5
2010-09-11T12:26:11.863Z
Thanks Aaaron - I had assumed that AND-join etc were fairly well known - they are in petri-net / workflow type theory. I just need a way to describe the semantics of the graph in a way that leaves no ambiguity, nothing more than that. Does that help?
flesh
CC BY-SA 2.5
2010-09-11T12:38:10.577Z
@flesh: Don't worry about what an axiom "looks" like. (Or sounding "axiom-like".) All an 'axiom' is, is a description of the basic behaviour of the objects you deal with. Example:

-- A **graph** G is a set V(G) of "vertices", together with a set E(G) of **edges**, where the latter which are unordered pairs of "vertices" (of the form {a,b}⊆V(G)).

-- A **walk** in a graph G is a sequence of vertices v[0], v[1], v[2], ... such that each consecutive pair of vertices {v[j], v[j+1]} is an edge in E(G).

Etcetera: just define  terms as simply as possible, with as few undefined terms as possible.
Niel de Beaudrap
CC BY-SA 2.5
2010-09-11T12:43:16.900Z
@flesh: The Wikipedia page [en.wikipedia.org/wiki/Petri_net] does not mention 'AND-join', 'OR-split', etc. nodes explicitly --- and I didn't read too thoroughly to find out --- so I couldn't tell how these nodes are defined. Perhaps that page may give you what you want, however. Unless someone comes by who knows about petri-nets --- for which you may wish to add a tag for your question --- , it seems unlikely that we can answer it without you describing how the branching process in your network works on more basic terms.
Niel de Beaudrap
CC BY-SA 2.5
2010-09-11T12:56:51.583Z
Ok, thanks, that's a great help. Just to get me started, what would an AND-join look like? In natural language, it's a vertex, of type ROUTING and has more than one active, incoming edge. I'm guessing I need to define the set of incoming and outgoing edges for each node type, qualify what 'active' means and then provide a size of set qualification to give me the AND-join aspect? **Comment added without seeing previous**
flesh
CC BY-SA 2.5
2010-09-11T13:35:12.370Z
You state that wrapper nodes have in-degree 1, but you also state that a “root node” is a wrapper node and a source.  They contradict each other.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-11T13:45:15.427Z
I cannot understand the exact question, but if you want to define something like Petri nets, why don’t you define your object by describing the difference from Petri nets?  What is the difference between your object and acyclic Petri nets?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-11T13:48:53.150Z
The difference is that I don't use the intermediate concept of a transition in an edge. So a petri net runs Vertex -> Trans -> Vertex. My model simply runs Vertex -> Vertex.
flesh
CC BY-SA 2.5
2010-09-11T13:49:26.440Z
In terms of Wrapper nodes - a root is always a wrapper, but a wrapper is not always a root.
flesh
CC BY-SA 2.5
2010-09-11T13:54:35.717Z
A _source_ means a node with in-degree 0.  You state that wrapper nodes have in-degree 1 and that a source is a wrapper node.  If you do not see any contradiction, I have no idea how to explain it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-11T13:59:34.033Z
“So a petri net runs Vertex -> Trans -> Vertex. My model simply runs Vertex -> Vertex.”  If that is the only difference, I do not see why you want to define your model differently from Petri nets.  Petri nets are an established notion, and you should use an established notion when applicable because doing so often makes the notion much easier to understand.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-11T14:07:25.933Z
Ahh, with respect to wrapper nodes, my original definition is the problem - they ahve *either* zero or one transitions in, and one out. Does that help? In respect of petri-nets, I won't be defining arcs, which I thought was a requriement of the model?
flesh
CC BY-SA 2.5
2010-09-11T16:37:56.763Z
An explanation for the down votes: The question isn't clearly stated or motivated, and on first viewing doesn't explain why this question is appropriate here and not StackOverflow. To fix problem 1, you would usually have a short story preceding the question that explains how the question arises and what previous approaches you have tried. (This might fix Problem 2 too!)
Robin Kothari
CC BY-SA 2.5
2010-09-11T16:48:00.123Z
Thanks Robin. I tried to avoid making the situation even more complex by adding context that wouldn't help. All I really need to know is how you formally describe a rooted, directed, graph. It's a pretty straight forward question.. or so I thought!
flesh
CC BY-SA 2.5
2010-09-11T20:47:00.427Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-12T08:26:59.427Z
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.
Charles Stewart
CC BY-SA 2.5
2010-09-12T08:36:22.210Z
Charles - yes you're right, I am looking for more than that, but that would be a good start. I don't really know what I'm looking for, that's why I'm here asking others! :)
flesh
CC BY-SA 2.5
2010-09-12T17:28:57.370Z
As Charles points out, this fits well into the Petri net framework.  http://en.wikipedia.org/wiki/Petri_net
András Salamon
<graph-theory><formal-modeling>
How do I formally describe a rooted, directed, acyclic graph?
flesh
# How do I formally describe a rooted, directed, acyclic graph?

(Asked by: username_0 on 2010-09-11)

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.

**Tags:** graph-theory, formal-modeling

> **Comments:**
> **username_1**: 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?  
> **username_0**: I have amended, I hope this is a little clearer.  
> **username_1**: This does clarify your question somewhat. I gather that your network describes a process in which multiple paths can be taken in parallel (the 'AND'-split), and may re-unite in different ways (the 'AND'-join); and in which one path among many may have to be chosen at different times (the 'OR'-split). But what does it mean to choose one 'incoming' transition among many? Do you mean to invoke some sort of scheduling process with a process lock of some sort?  
> **username_0**: Exactly, You have decribed it better than I have. "Choose" is probably the wrong word - it just means only one branch is active on incoming. In other words, despite the existence of multiple incoming transitions at a routing node, only one is ever executed in practice.  
> **username_0**: Why the downvote? It would be nice if someone could explain what is wrong with this question? Thanks.  
> **username_1**: To elaborate on my previous comment: the first thing you may need to do is to formalize (i.e. describe the pertinent features of)  the path-formation, or branching, process in this network.  
> **username_0**: I'm not sure how I go about this, that's my problem - what might an axiom look like? I'm guessing I might need to describe Nodes and Paths, then the branching processes as you say, but I'm not clear how.  
> **username_2**: Using new terms before you define them will lose people.  You use "AND-split" long before you say what it means.  Also, I'm still not sure you resolved all the issues brought up by username_1's first comment.  Also also, what do you need this formalism to do? The application matters.  
> **username_0**: Thanks Aaaron - I had assumed that AND-join etc were fairly well known - they are in petri-net / workflow type theory. I just need a way to describe the semantics of the graph in a way that leaves no ambiguity, nothing more than that. Does that help?  
> **username_1**: @username_0: Don't worry about what an axiom "looks" like. (Or sounding "axiom-like".) All an 'axiom' is, is a description of the basic behaviour of the objects you deal with. Example:  -- A **graph** G is a set V(G) of "vertices", together with a set E(G) of **edges**, where the latter which are unordered pairs of "vertices" (of the form {a,b}⊆V(G)).  -- A **walk** in a graph G is a sequence of vertices v[0], v[1], v[2], ... such that each consecutive pair of vertices {v[j], v[j+1]} is an edge in E(G).  Etcetera: just define  terms as simply as possible, with as few undefined terms as possible.  
> **username_1**: @username_0: The Wikipedia page [en.wikipedia.org/wiki/Petri_net] does not mention 'AND-join', 'OR-split', etc. nodes explicitly --- and I didn't read too thoroughly to find out --- so I couldn't tell how these nodes are defined. Perhaps that page may give you what you want, however. Unless someone comes by who knows about petri-nets --- for which you may wish to add a tag for your question --- , it seems unlikely that we can answer it without you describing how the branching process in your network works on more basic terms.  
> **username_0**: Ok, thanks, that's a great help. Just to get me started, what would an AND-join look like? In natural language, it's a vertex, of type ROUTING and has more than one active, incoming edge. I'm guessing I need to define the set of incoming and outgoing edges for each node type, qualify what 'active' means and then provide a size of set qualification to give me the AND-join aspect? **Comment added without seeing previous**  
> **username_3**: You state that wrapper nodes have in-degree 1, but you also state that a “root node” is a wrapper node and a source.  They contradict each other.  
> **username_3**: I cannot understand the exact question, but if you want to define something like Petri nets, why don’t you define your object by describing the difference from Petri nets?  What is the difference between your object and acyclic Petri nets?  
> **username_0**: The difference is that I don't use the intermediate concept of a transition in an edge. So a petri net runs Vertex -> Trans -> Vertex. My model simply runs Vertex -> Vertex.  
> **username_0**: In terms of Wrapper nodes - a root is always a wrapper, but a wrapper is not always a root.  
> **username_3**: A _source_ means a node with in-degree 0.  You state that wrapper nodes have in-degree 1 and that a source is a wrapper node.  If you do not see any contradiction, I have no idea how to explain it.  
> **username_3**: “So a petri net runs Vertex -> Trans -> Vertex. My model simply runs Vertex -> Vertex.”  If that is the only difference, I do not see why you want to define your model differently from Petri nets.  Petri nets are an established notion, and you should use an established notion when applicable because doing so often makes the notion much easier to understand.  
> **username_0**: Ahh, with respect to wrapper nodes, my original definition is the problem - they ahve *either* zero or one transitions in, and one out. Does that help? In respect of petri-nets, I won't be defining arcs, which I thought was a requriement of the model?  
> **username_4**: An explanation for the down votes: The question isn't clearly stated or motivated, and on first viewing doesn't explain why this question is appropriate here and not StackOverflow. To fix problem 1, you would usually have a short story preceding the question that explains how the question arises and what previous approaches you have tried. (This might fix Problem 2 too!)  
> **username_0**: Thanks Robin. I tried to avoid making the situation even more complex by adding context that wouldn't help. All I really need to know is how you formally describe a rooted, directed, graph. It's a pretty straight forward question.. or so I thought!  
> **username_3**: 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.  
> **username_5**: 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.  
> **username_0**: Charles - yes you're right, I am looking for more than that, but that would be a good start. I don't really know what I'm looking for, that's why I'm here asking others! :)  
> **username_6**: As Charles points out, this fits well into the Petri net framework.  http://en.wikipedia.org/wiki/Petri_net  

---

## 1 answers

### Answer by username_7 on 2010-09-12. Score: 2

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.

> **Comments:**
> **username_0**: Did you have a formal specification, particularly of the branch nodes?  
> **username_7**: 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.  

---

