Skip to Content

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.

  1. Feeding the input with XML
  2. Try to loop back to XI itself for recursive like functions.
  3. Usage of BPM
  4. 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

image

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.

To report this post you need to login first.

8 Comments

You must be Logged on to comment or reply to a post.

  1. Community User Post author
    Interesting again!!

    >>Please give me your valuable comments on my TSP implementation on XI.
    Yes…I am always there for your interesting blogs.:-)

    My 1st Question is are you showing that how any
    XYZ algorithm which can be done in java or other
    platform can be done in XI (using
    either msg mapping functions or module processors
    or external libs in JAVA)? OR are you showing
    how XI can be marketed to those companies
    that are implementing this algo. for TSP?

    Let me start with small example, an ABC courier
    services is going to setup 4 branches in Indian
    cities namely Hyderabad,Mumbai,Bangalore and
    Chennai and in each city they will be having
    15-20 sub-branches.
    All items that are couriered to a city reaches
    to main branch first and then they are sent to
    their sub-branches and finally to destination from sub-branch.

    Now finding out the most feasible route from
    main branch to sub-branches will be done say using TSP.
    But it’s required only once as this is fixed.
    Only variables will be from sub-brances to destinations
    as they will vary daily.Now ABC courier services can obviously
    develop an application which will cater to TSP problem,
    Where we can give the distance input and total destinations
    to be covered to get the feasible path. say as per your blog
    these are all XML files,Then the application will take care
    of extracting distance inputs from XMLs.

    Now my Question here would be…How I (say manger
    of IT dept. for ABC courier services) would be
    convinced to buy XI instead of developing an application
    for above problem?and how the ROI is promised?

    Now coming to technical analysis as how TSP will work with XI,
    then the 1st thing obviosly to consider is the number of
    loops to XI when the number of destinations grow to
    an extent.
    Also…
    >>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.

    Yes…
    Many other factors go without saying like decreased
    performance (even if BPM not used), increased maintenance.

    Now if the aim of your blog was to show how any algo.
    can be technically implemented using XI, then I may not be surprised
    if you come up with say Leaky Bucket or Token bucket
    algorithms or socket programming,or other routing algorithms,
    computer networks in XI instead of java/c++.

    Lastly, As u pointed out 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.

    There is a major flaw in the above logic.What you have mentioned
    in the statement for broadcasting of info is not Travelling Salesman Problem(TSP)
    but it’s Minimal Spanning Tree(MST) problem.Because TSP doesn’t broad cast info
    but only determines SHORTEST path connecting all
    nodes.Ex: for TSP is like the courier service.
    The MST broadcasts info in an OPTIMAL path for Ex: IRC (Internet Relay Chat), where
    the nodes are servers that send the messages to other servers.

    In the TSP one has to return to starting point after covering all locations.
    But in broadcasting info (MST) the job is finihed once the last
    node receives message.
    The minimal spanning tree problem is a normal one.
    But in TSP when ‘N’ (number of nodes)
    tends to a very large number the solution cannot be guaranteed as
    optimal (NP-complete problem) and in fact the research is still going on this TSP prob.

    Anyways my point is…here it fails to give a true business motive
    for above blog (if any).

    Cheers
    Sudhir

    (0) 
    1. Community User Post author
      Hi,
      Well..in the above comment I mentioned about TSP being NP-complete problem.I feel i should describe
      a liitle what NP Problems are so if anyone is reading this he/she is not confused 🙂

      ‘P’ problems are Class of decision problems that can be solved in
      polynomial time (quick time)

      NP(nondeterministic polynomial) problems are Class of decision problems
      such that if the answer to the problem is yes, then there is a method
      that can be checked/verified in polynomial time to show that the answer is
      correct.
      NP problems are one in which the “running time to find the solution” is
      NOT ploymimial and that we have no way to prove that the ALGORITHM
      we have to obtain the solution is the best.

      The hardest problems in NP class are called NP-Complete and they have
      a property that any problem in that class could be reduced to another.

      Cheers
      Sudhir

      (0) 
      1. Anonymous
        Sudhir,

        It was on the technical part that was concentrated more rather than the

        application. Whether TSP or MST, the core idea is to show how to solve such problems in XI.

        I started off with TSP in my mind and while developing in XI, seeing the technical complexities, I first decided to find only the shortest distance and also avoided the back trip which happened to be Minimum Spanning tree.

        When I was totally involved in developing this, I completely forgot that, the reduced version of Traveling salesman problem is nothing but Minimum spanning tree.

        Anyway, I had completely updated my blog and also posted the technical part (Part – 2) of it. Once again, thank you for your valuable comment!!

        Regards,
        Felix

        (0) 
        1. Community User Post author
          >>
          I started off with TSP in my mind and while developing in XI, seeing the technical complexities, I first decided to find only the shortest distance and also avoided the back trip which happened to be Minimum Spanning tree.

          When I was totally involved in developing this, I completely forgot that, the reduced version of Traveling salesman problem is nothing but Minimum spanning tree.

          u made a small mis-assumption… MST isn’t reduced version of TSP.If it was true then most research going on TSP will be out of funds
          ..as I mentioned in my 1st comment TSP deals with roundtrip and shortest distance b/w nodes…whereas MST deals with the minimum weight of tree…like IRC for spreading messages in the tree..where each node will receive the message…the traversal path
          is optimal path in MST..because the execution time is polynomial…where as in TSP it’s exponential
          (for large nodes..no guaranteed solution)
          Regards,
          Sudhir

          (0) 
          1. Anonymous
            Sudhir,
            I was a bit confused when you said Minimum Spanning tree and I even updated my blogs. Actually, it is Shortest Path Problem. Also, TSP is a kind of shortest path problem!
            ref: http://en.wikipedia.org/wiki/Shortest_path
            Hence, shortest path problem is a reduced version of Traveling sales man problem.
            Regards,
            Felix
            (0) 
            1. Community User Post author
              >>shortest path problem is a reduced version of Traveling sales man problem.

              Exactly…that’s what i initially wondered why u changed title to MST…but in blog as u specified abt spreading info.
              Spreading info is always MST…say if u want to spread a rumor …in a city with 50-60 friends…
              then the spanning of rumor/message in entire friend’s network with minimum cost is MST…but finding out shortest distance b/w two friends is Shortest path problem (SPP)…and traveling ALONE
              with shortest roundtrip distance is TSP

              Regards,
              Sudhir

              (0) 
        2. Community User Post author
          >>
          I started off with TSP in my mind and while developing in XI, seeing the technical complexities, I first decided to find only the shortest distance and also avoided the back trip which happened to be Minimum Spanning tree.

          When I was totally involved in developing this, I completely forgot that, the reduced version of Traveling salesman problem is nothing but Minimum spanning tree.

          u made a small mis-assumption… MST isn’t reduced version of TSP.If it was true then most research going on TSP will be out of funds
          ..as I mentioned in my 1st comment TSP deals with roundtrip and shortest distance b/w nodes…whereas
          MST deals with the minimum weight of tree…like IRC for spreading messages in the tree..where each
          node will receive the message…the traversal path
          is optimal path in MST..because the execution time is polynomial…where as in TSP it’s exponential
          (for large nodes..no guaranteed solution)
          Regards,
          Sudhir

          (0) 
    2. Anonymous
      The aim of the blog is neither to show how XYZ algorithm which can be done in XI nor to market XI to companies implementing TSP algo.

      The aim of the blog is to show how XI can be used in transforming values having same data structure and doing a data lookup on the same XML, only by using message mapping, without any advanced module programing or java libs. The aim is mostly on technical perspective rather than business perspective, giving an outlook of ResultList usage and XML context changes to extreme limits. To demonstrate this, TSP (MST) is taken as an example. This blog series has nothing to do with business or marketing, but I promise that its going to be a good feast for a technical developer.

      Yes, its Minimal Spanning Tree(MST) and I have updated (updating…). I totally forgot that TSP have return routes ;).

      >> Anyways my point is…here it fails to give a true business motive for above blog

      The blog doesn’t have any business motive. It only has pure technical motives 😉

      (0) 

Leave a Reply