Min Net Path and Min Span Tree with ORMSware Discrete Event Simulator~2
(Great illustrative teaching problem, which I believe was created by William Fiset for his work on Graph Theory Algorithms at youtube.com/c/WilliamFiset-videos.)
Minding p's (probes) and queues brings exceeding joy!
Introduction
For anyone wondering what minimum network path and minimum spanning tree of a network are, I could not find any nontechnical sites online that explain them. Not that the explanation here is nontechnical, of course. The best I could think of was to go through a few steps of the solution process here with the above example so that visitors can easily understand the problem and the solution strategy used here. The level of difficulty is no higher than that of solving fun, ordinary puzzles everyone has seen before.
In this article I present a slightly different ORMSware Discrete Event Simulator implementation of the Minimum Path (MP) and Minimum Spanning Tree (MST) algorithm I presented before. I have also included a standalone EXE file of the new model, which will execute on Windows platforms without ORMSware's presence. Also included are various text files, Excel files in XML Spreadsheet 2003 format which the model's EXE can read, and source files of the algorithm implemented using ORMSware-simulator-driven programming.
Discussion of example problem in this article's banner image above
Modified copy of banner image for printing, if desired: https://www.ushar.com/ormsware/models/minspantree/linkedin/LinkedInBanner~V2Pr.png
Keeping open in another window the banner image at the link above will make it easier to follow the problem and the solution approach.
This problem is similar to various puzzles you may have solved before. There is only simple arithmetic, comparison of available choices, and very simple logic involved in finding both MP and MST solutions for problems of this type.
Nodes and arcs (the circles and the links connecting them) on the right side of the image above are parts of the whole problem on the left. Notice that node A at top right is connected to nodes B, D, and E and are respectively at 5, 9, and 1 unit(s) of measure away from A. The measure can be any metric such as time, distance, cost, revenue, quantities, mass/weight, volume, etc., for which the generic term "weight" is often used by technical professionals.
Notice that the nodes, connections, and measures displayed on the right are their identical namesakes on the left. You may also wish to verify that E is connected to A, D, and F with 1, 2, and 1 unit(s) respectively, and that F is connected to E, D, and G with 1, 5, and 7 unit(s). Copies of these nodes and arcs and their relationships are displayed on the right to make our discussion of the algorithm easier.
A challenge for fun (Minimum Network Path or Minimum Path - MP)
Please look at the network picture on the left side of the banner. Find the shortest possible path from node A to node J. What is the total units one would need to travel on the shortest path you found?
The answer to this puzzle is 10 units. In fact, in this problem there are multiple paths with the same total distance.
Another challenge for fun (Minimum Spanning Tree - MST)
Start at node A or J or any node you wish. What is the least total length of pipes that will be necessary to connect every node in the network?
The answer to this puzzle is 14 units and in this problem there are multiple ways to connect all nodes, yielding the same minimum total length.
Of course, by definition, answers from both models are theoretical. And, of course, the two challenges above show that most people already know what MP and MST problems are.
MP/MST algorithm in easier terms using the example problem
[I use ORMSware, my discrete event simulator to solve both problems. (My guess is that most process-oriented or orientation-independent simulators can be used as well.) ORMSware implementation of both algorithms (MP and MST) are virtually identical. You will see the difference in a few minutes.]
The solution involves an iterative process, of course. We will start with the MP problem in the first challenge above at its Source Node, viz., node A. You can see on right hand side of the image that node A has 3 successor nodes, viz., B, D, and E. We will be talking in terms of "probes" or "customer surrogates" traveling systematically through the network, starting at the Source Node, to find the shortest path to the Target/Sink Node (traveling A to J).
Algorithm
Node A is the pivot/origin node in the first iteration. We want to launch probes in search of the Sink Node, but need to be be careful not to blindly launch probes to successor nodes that have no potential. These rules will help us do that:
Watch the algorithm at work (the above process in operation)
(You can watch it happen in a story log. There's a link further below to such log files.)
From A (colored green for illustration here, because it is this starting iteration's pivot node), we launch probes to all successors (B, D, and E). They get on the Events schedule in the simulator's Events queue to land on their destinations at 5, 9, and 1 on the simulation clock.
Probe to E (colored yellow), the first one to land, lands at sim clock 1.000. A new iteration begins upon this landing, and E becomes the new pivot node.
E cannot launch to A, since A is already fathomed (colored red) and the landed probe came from A.
E launches probes to D and F. Probe to F lands first (1 time unit later), when the sim clock is at 2.000. Probe from E to D is still on its way to D. It will reach D another time unit later at 3.000 on the sim clock.
Meantime, it's another new iteration since F has landed and F becomes the new pivot node while the clock is at 2.000. Node F's successors are E, D, and G.
F cannot launch to E as E is already fathomed and the landed probe came from E. (It is probably clear by now that a probe will not come from a node that is not already fathomed.)
F cannot launch to D. But why?...
Because a probe from E to D is already on its way to land at D at 3.000 on the clock. It is 2.000 on the clock now and if we launch from F to D, that probe will not reach D until 2.000 + 5.000 = 7.000 on the clock. No launches to destination nodes with no promise. Therefore, no F-to-D launch. (This is the example I referred to in algorithm rule #3 above.)
However, do we launch to G? Well, we cannot say without looking at the full network on the left part of the image. If you do look, you'll see that we will not launch to G, either, from F. In case you cannot see why yet, you will when you look at MP's story log.
Story log files
I like to provide "story log" or story-telling log of a program execution that tells the story of what happened. A story log helps stakeholders of a problem as well as the modelers.
Story log is at a level higher than ORMSware's technical execution log, which gets down to the more granular nitty-gritty details of the program to show what the program did, and in case anything went wrong, what went wrong, and where, why and how a program crashed.
In addition to the story log developed for a given model or program, virtually the entire story log also automatically gets inserted into the technical execution log. There the story log gets interspersed with the technical details. Technical execution log will not be helpful to most stakeholders. It is, however, it often comes in quite handy to modelers/analysts.
At any rate, story log of MP and MST executions of this example problem, and summaries of the min path taken, and min spanning tree built, are in the files posted at the links below:
Where Minimum Path and Minimum Spanning Tree processes differ
There is just one key difference in nature between MP and MST search processes.
(As mentioned before, the "weight" of an arc in network problems is just a generic term referring to unit of measurement in a problem. It can be anything, such as time, distance, mass/weight, money, etc. I tend to use time and distance frequently in discussions instead of weight, because I think time and distance make it easier for people to get their minds wrapped around network algorithms as well as other concepts. So, please keep in mind. Time doesn't necessarily mean TIME here [:)])
Minimum Path
In MP we are concerned with minimizing time between just two points (any pair of nodes), viz., the source/start point, and the sink/end point. The source is at clock zero, and we seek to find a path that minimizes the time on the clock at each node on the path/chain as we converge on the sink. When a probe reaches a node, whether or not it is the sink node, the time on the clock will always be the most minimum possible from the source to that node.
领英推荐
Minimum Spanning Tree
In MST we are concerned with choosing the connections in a network such that the combined total length ("weight") of all the connections (arcs) are minimized.
So, in MST, at any iteration, we look for the nearest node that is not yet in the MST set, to any node that is already in the set. At no point are we concerned about where we are compared to where we were when the search started. We are only concerned with the minimum distance it will take at that very point, to connect any node that is already in MST, to any other node not yet in the set.
Therefore, sim clock which keeps time from the start as events happen in a simulation, is irrelevant in MST search. However, the Events queue that the clock uses to keep time, is still indispensable. At each iteration, we are starting over, with clock at zero, by neutralizing the clock. However, the Events queue makes sure we pick the nearest node to existing MST set.
Why? Because what we put in the events queue at every pivot-and-launch is always the distance between a node in MST set and another node not in MST set. And the shortest connection will always be at the head of the Events queue. In MST algorithm Events queue is just sort queue to keep arc distances at each pivot in ascending order.
This can be verified easily by examining the story logs of MP and MST executions (see links above, or you can make your own runs with the downloadable Zip file provided at https://www.ushar.com/ormsware/models/minspantree/linkedin/MinSpanTree.zip.
Neutralizing simulation clock for MST
What moves a simulation clock is a scheduled event (such as a probe landing) that is the very next event in the simulator's Events queue, and that scheduled time is later than the current time on the sim clock.
Scheduled time of an event completion is calculated by the simulator with a simple equation:
[scheduled completion time] = [cur time on sim clock] + [Duration of event to be scheduled]
By taking [cur time on sim clock] out of the equation for MST, we get
[scheduled completion time] = [Duration of event to be scheduled]
ensuring that the clock is neutralized. This can be accomplished through the Duration time formula entered at arc [17] in TopNet network of MinSpanTree model.
Thus, at the end of each iteration, the sim clock will always show the current time to be equal to the distance from MST set to the node just added to the set. It will so happen that the new node added at each iteration will be a node closest to the set, because as mentioned before, in Events queue the events will have been sorted in ascending order of [Duration of event to be scheduled], ensuring that the node with an arc to the MST with the smallest Duration is at the head of the Events queue.
The story log for ORMSware MST implementation still displays the sim clock at each iteration, though the clock is neutralized. However, since the clock time displayed will always equal the smallest Duration of the arcs in a given iteration, if you add up the clock time at each iteration, you will find that the sum equals to the sum of MST arc weights.
Check the story log for MST. https://www.ushar.com/ormsware/models/minspantree/Output/MST-EventsQ.TXT
Revised ORMSware Implementation of MP/MST algorithm
(Until now we have been focused mostly on the network on the right part of image below. It is a network of nodes and arcs and we have been solving two problems involving them. Now we will also be looking at the network on the left part of the image with rectangle nodes and directed arcs. The network on the right is data. Network on the left is a model with which we operate on the data. Whenever there is potential for confusion, I will be referring to nodes and arcs on the right as data nodes and arcs, and nodes and arcs on the left as logical nodes and arcs.)
As I was writing about the slightly revised algorithm implementation from my first LinkedIn article on MP/MST with discrete event simulators, it seemed that it would be easier to explain it with a network diagram. Should have known that because that was one of the motivations for building and laboring on ORMSware since 2001!
After sketching out the logic with ORMSware Visio Stencil, I realized that virtually all changes were in Node [11]. [See bottom of yellow rectangle (portrait orientation) in image below.] And it became clear that the sketched out logic could be fleshed out and plugged in as a subnet into the TopNet network that was already implemented.
That fleshed out network diagram became Launch, a subnet nested under arc [17] (see below). Launch network image is pasted right under this TopNet image below.
The Launch subnet
(If you are an IT person, you most likely have heard about "Clean Code" and many an IT professional's obsession with clean code, and overwhelming fear of becoming known as someone who has written unclean code [:)]. My field is Decision Science / Operations Research. Let me state here for some levity that I like "Clean Queues" instead and it is my obsession with clean queues that led to this update in ORMSware implementation of MP/MST algorithm [:)].)
The Launch network above starts executing when node [11]Abstract_Pivot_Node in TopNet network is finished. Then, Arc [17] executes when the Launch subnet is finished, provided Branch condition on Arc [17] evaluates to TRUE at that time.
At the beginning of each iteration of MP/MST algorithm, Node [11]Abstract_Pivot_Node identifies the next data node to pivot on. That would be either the start/source data node or the data node on which a probe just landed. Execution thread then goes into Launch subnet's logical Start node (i.e., [3]First/next Successor). Logical node [3] then sends probes to all unfathomed successor data nodes of the pivot data node it is representing at the time.
Pasted below are the four launch rules in the informal algorithm description presented earlier. While repeating those launch rules here, I have inserted at the beginning of each launch rule (2, 3, and 4), the nodes and arcs in the Launch network image above. This list shows how those rules completely represent the Launch network logic (and vice versa).
Keeping queues clean and model compact
Execution-related files and information (All rights reserved)
Files for executing MinSpanTree on Windows machines: https://www.ushar.com/ormsware/models/minspantree/linkedin/MinSpanTree.zip
Zip file contains the ten files listed below. After extracting all files from Zip to an empty (preferably) folder, execute MinSpanMinPath.BAT in that folder to create all necessary folders, and to copy these files to appropriate folders in preparation for MinSpanTree.exe execution. To know what new folders will be created, please check the contents of MinSpanMinPath.BAT.
All files created while running MinSpanTree.exe will be under C:\ORMSware, which will be the root folder containing all folders and files related this model. To get rid of everything created by the model, all you need to do is delete folders C:\ORMSware and below.
ORMSware libraries and models have hard-coded references to C:\ as the root. All files need to be on C drive. Isn't it possible to make a not-C drive a logical C drive? I do not have the expertise to say. My apologies for this inconvenience. If there is something relatively simple I can do to help anyone who really wants to run MinSpanTree.exe, but cannot, please feel free to contact me (Reginald Joules at https://www.ushar.com/#ContactInfo).
In creating and compiling programs my focus tends to be on feasibility rather than optimality. I prefer to write and implement code as quickly as possible and take measures to minimize mean time to repair the program in case things go wrong. Here, as always, I have traded execution time heavily in favor of minimizing MTTR. You will see this tendency in MinSpanTree.exe's source files, available now to readers who wish to see them.
Where the action is concentrated
Recall that the core part of the model is in node [11], arc [17] and its subnet Launch, and node [12]. Nodes and arcs before [11] are straightforward logic for extracting and structuring network data from external source(s). Nodes and arcs after [12] are also straightforward, concerned merely with producing output from the solution.
To anyone who really wants to know more than the obvious matters about the model, I recommend starting with Visio network diagrams of TopNet and Launch networks of MinSpanTree model at the links below:
Coordinated supplemental code that fleshes out both TopNet and Launch networks of MinSpanTree model is in this NET file: https://www.ushar.com/ormsware/models/minspantree/MinSpanTree.NET.TXT
Local (non-library) procedures supporting the NET file above is this ADD file: https://www.ushar.com/ormsware/models/minspantree/MinSpanTree.ADD.TXT
NET and ADD files are also included in the Zip file download. The TXT extension to both files posted online was to make it easy to post them online.