1 Reply Latest reply on Apr 14, 2009 1:43 PM by wvxvw

    Write a recursive function to determine all possible paths between a number of addresses

      Hi,

       

      I have a matrix which holds the time data it takes to travel between different addresses (Zipcodes actually).

       

      I want to determine all possible unique routes (each route should travel each zipcode), so I can than determine which routes take the least amount of time. I thought up the easiest solution to use a recursive function and determine all unique routes by mimicing a tree like structure with arrays.

       

      However my ActionScript/Flex knowledge is not sufficient enough to write that up I'm afraid.

       

      My begin scenario looks like this:

       

      var TimeMatrix:Array = {
           "3014CD" : {
                "1011AB" : 50,
                "9714AM" : 30,
                "2727"   : 20 }
           "1011AB" : {
                "3014CD" : 30,
                "9714AM" : 40,
                "2727"   : 10,
           "9714AM" : {
                "3014CD" : 55,
                "1011AB" : 20,
                "2727"   : 30 }
           "2727" : {
                "3014CD" : 78,
                "1011AB" : 30,
                "9714AM" : 25 }
      };
      
      var Zipcodes:Array;
      Zipcodes.push("3014CD");
      Zipcodes.push("1011AB");
      Zipcodes.push("9714AM");
      Zipcodes.push("2727");
      
      

       

      Thanks in advance

        • 1. Re: Write a recursive function to determine all possible paths between a number of addresses
          wvxvw
          1.     var allRoutes:XML =
          2.     <routes>
          3.         <zip n="3014CD" t="0">
          4.             <zip n="1011AB" t="50"/>
          5.             <zip n="9714AM" t="55"/>
          6.             <zip n="2727" t="78"/>
          7.         </zip>
          8.             <zip n="1011AB" t="0">
          9.             <zip n="3014CD" t="50"/>
          10.             <zip n="9714AM" t="20"/>
          11.             <zip n="2727" t="10"/>
          12.         </zip>
          13.             <zip n="9714AM" t="0">
          14.             <zip n="3014CD" t="55"/>
          15.             <zip n="1011AB" t="20"/>
          16.             <zip n="2727" t="25"/>
          17.         </zip>
          18.         <zip n="2727" t="0">
          19.             <zip n="3014CD" t="78"/>
          20.             <zip n="1011AB" t="10"/>
          21.             <zip n="9714AM" t="25"/>
          22.         </zip>
          23.     </routes>;
          24.     var hash:Array = [];
          25.     function shortestCircut(routes:XML, startPoint:String, endPoint:String):int
          26.     {
          27.         if (!routes.*.length()) return int.MAX_VALUE - int(routes.@t);
          28.         trace(startPoint, " => ", endPoint);
          29.         trace("---------------------------");
          30.         trace(routes.toXMLString());
          31.         trace("---------------------------");
          32.         var startZip:XML = routes.*.(@n == startPoint)[0];
          33.         var endZip:XML = routes.*.(@n == endPoint)[0];
          34.         var pTime:int = routes.hasOwnProperty("@t") ? int(routes.@t) : 0;
          35.         var time:int = int(startZip.*.(@n == endPoint).@t) + pTime;
          36.         if (time == pTime) return int.MAX_VALUE - pTime;
          37.         trace("pTime:", pTime, "time:", time);
          38.         var available:XMLList = startZip.*.(int(@t) < time);
          39.         var availableZips:Array = [];
          40.         available.(availableZips.push(String(@n)));
          41.         var totalAvailables:XMLList =
          42.         routes.*.((valueOf() !== startZip &&
          43.         availableZips.indexOf(String(@n)) > -1) ?
          44.         true : !hash.push(String(@n)));
          45.         var unavailable:XMLList = routes..*.(int(@t) >= time);
          46.         while (unavailable.length())
          47.         {
          48.             delete unavailable[0];
          49.         }
          50.         delete routes.*.(@n == endPoint)[0];
          51.         if (!routes.*.length()) time;
          52.         var lookUp:XML;
          53.         var addedTime:int;
          54.         for each (var n:String in availableZips)
          55.         {
          56.             lookUp = totalAvailables.(@n == n)[0];
          57.             addedTime = pTime + int(available.(@n == n)[0].@t);
          58.             unavailable =
          59.                 routes.*.(@n == n && (@t = int(@t) +
          60.                 addedTime)).*.(int(@t) + addedTime >= time);
          61.             while (unavailable.length())
          62.             {
          63.                 delete unavailable[0];
          64.             }
          65.         }
          66.         unavailable = routes.*.(hasSimpleContent());
          67.         while (unavailable.length())
          68.         {
          69.             delete unavailable[0];
          70.         }
          71.         totalAvailables = routes.*.(valueOf() !== startZip);
          72.         delete routes.*.(valueOf() === startZip)[0];
          73.         if (!routes.*.length()) time;
          74.         while (routes.*.length())
          75.         {
          76.             routes.@t = routes.*[0].@t;
          77.             addedTime = shortestCircut(routes.copy(), routes.*[0].@n, endPoint);
          78.             trace(time, "- adding -", routes.*[0].@t, "- next approach -", addedTime);
          79.             if (addedTime < time) time = addedTime;
          80.             delete routes.*[0];
          81.         }
          82.         trace("<--------------------------->");
          83.         return time;
          84.     }
          85.     trace(shortestCircut(allRoutes.copy(), "2727", "3014CD"));