Somewhat of an academic challange (but usefull if solved)

[Art]

This question/problem I'm presenting here is a result of my own struggles to
solve it. I promise you that solution to it will be used by many. Therefore
w/out further due:

Abstracts: BizTalk orchestrations need to be started/stopped/unlisted in
particual order. This happens when orchestrations reference themselves in
linear or tree fashion.

Examples:
- A references B therefore B needs to be stopped before A,
- A references B, B references C AND D therefore C and D need to be stopped
first then B and finally A.

I'm sure you get the picture. So here are rules of the game.
- there can be any number of orchestrations running of a server,
- referencial complexity is arbitrary; X number of orchestrations can
reference one another in any nuber of ways including circular. If circular
dependency is discovered it should to be reported.
- every orchestration (object if you prefer) can provide you with a list of
all other objects it references.

Let's look at an example (this is actual output from one of our
orchestrations trimmed here for brevity):

<RootOrchestration Name="Root">
<UpstreamOrchestration Name="1.1.1"/>
<UpstreamOrchestration Name="2.1.2">
<UpstreamOrchestration Name="3.2.1">
<UpstreamOrchestration Name="4.3.1"/>
<UpstreamOrchestration Name="5.3.2">
<UpstreamOrchestration Name="6.4.1"/>
<UpstreamOrchestration Name="7.4.2"/>
</UpstreamOrchestration>
<UpstreamOrchestration Name="8.3.1">
<UpstreamOrchestration Name="9.4.1">
<UpstreamOrchestration Name="10.5.1"/>
<UpstreamOrchestration Name="11.5.2"/>
</UpstreamOrchestration>
</UpstreamOrchestration>
<UpstreamOrchestration Name="12.3.1"/>
</UpstreamOrchestration>
</UpstreamOrchestration>
</RootOrchestration>

First number = sequetial node # counted from the top
Second Number = depth as counted from the root
Third number = sibling order

This numbering convention was estabilished only for illustrative purposes
and to avoid abiguity.

This sample output tells you that before you stop orchestration named "Root"
you have to stop at least 12 z(twelve) other orchestrations in a particular
order. Rules state that you have to stop the child before the parent. So, one
possible solution would be this ("/" means that stop order does not matter
for these objects):

1. 10.5.1 / 11.5.2
2. 9.4.1
3. 12.3.1 / 8.3.1
4. 7.4.2 / 6.4.1
5. 5.3.2 / 4.3.1
6. 3.2.1
7. 2.1.2 / 1.1.1

This only for "Root" object. Remember that there can be any number of
objects/orchestrations running. So, for each of the twelve objects referenced
by the "Root" you have to find out their own relationships before you can
successfully stop "Root".

 

[Jeroen Mostert]

Abstracts: BizTalk orchestrations need to be started/stopped/unlisted in
particual order. This happens when orchestrations reference themselves in
linear or tree fashion.

Examples:
- A references B therefore B needs to be stopped before A,
- A references B, B references C AND D therefore C and D need to be stopped
first then B and finally A.

What you're looking for is called a topological sort on a dependency graph.
It's a classic problem found in many areas.

 

[Art]

This was exaclty what I was looking for. Thanks for your help!