Introduction
What is Shortest Path Problem?
In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized.
There are some important points that we had to note when we try to solve such similar problems in XI.
- Feeding the input with XML
- Try to loop back to XI itself for recursive like functions.
- Usage of BPM
- Message Mapping - Java functions will be handy in transforming data while the XML is in recursive loop.
Structuring the Input
The input is obviously XML. We can have two sections like running value tags and unchanged value tags. Hence the value changes from one mapping to another in temporary value tags and the values do not change in permanent value tags. So, why are these temporary and permanent value tags for? Well, in permanent section of the XML, we have the distances between all the cities and in the running section we have the distance from the question – source to all the other cities.
Assume we want to calculate distance from A to D
Running value tags:
(All routes and distances from city A)
A to B
A to C
A to D
Permanent value tags:
(All the cities and the available routes and distances
between them)
A to B
B to D
D to C
A to C
How is the above structure help XI in solving the Shortest Path problem?
The basic initial idea is to use the same structure for input as well as output. Secondly, the same logic can be applied on the produced XML for different source cities updating the actually required distance. Finally, it is easier to lookup within the same XML structure rather than having the data in database or an external file.
The Logic:Every city broadcasts its information to its neighboring cities. These neighboring cities will in turn update this information with respect to its neighbors and broadcasts it to its neighbors. This includes the source city also. The source city sends back (a broadcast message) if and only if there is any change. Through this the distance between the source and target can be easily found using XI by sweeping through the entire city network once.
Theoretical Implementation
The above is a diagram representing the cities A-I with distance. Here we will use XI to find the shortest distance between A and I.
Let’s take the message from city A:
(Message Sent)
AB=3
AE=2
AG=3
Let’s take the message from city B:
(Before transforming)
BA=3
BF=3
BH=1
(After transforming)
AB=3
AF=6 (AB+BF), If ‘AF’ already exists, place the value which is smaller.
AH=4 (AB+BH)
(Message Sent)
AB=3
AE=2
AG=3
AF=6
AH=4
By doing this to all the cities we finally get a message with values all shortest distances from A to all cities.
How to implement it on XI?
Every city can be considered as an interface mapping in XI with message from one city goes to another in the form of XML through BPM. A set of interface mappings and sequential transformations with all the cities (mappings) for no of cities, 'n'- times the XML with the shortest distances from the required source will be produced
Algorithm for message mapping lookup: While updating the running value tags, a lookup is made on the permanent value tags for the distance between a particular source and destination. This value will get updated by adding the value of source to source tag, to make value from A (source) to destinations and comparing with the existing value to update the smaller value. Through this technique, the distance for intermediate cities are calculated and dynamically updated on the same XML and fed into the next city (interface maping) The real challenge lies in the Message mapping - java functions to do a lookup within the same XML and do arithmetic operations and update the same.
On the A practical implementation of Shortest Path Problem in XI (Part II) of this blog series, we will look into the practical implementation of this shortest path problem.
8 Comments
