From: Peter Brawley
Date: March 2 2008 5:32am
Subject: Re: Efficiently storing a directed graph
List-Archive: http://lists.mysql.com/mysql/211572
Message-Id: <47CA3C05.7030102@earthlink.net>
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------020800000506090302010600"

--------------020800000506090302010600
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

//How would you implement this in PL/SQL ?

Have a look at 
http://hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.aspx?

PB

mgainty@stripped wrote:
> Good Evening Peter-
>
> //so if I look at this algorithm from wikopedia I see something like
> //Java/C#/C++ no problem
> //How would you implement this in PL/SQL ?
>
> public Dictionary CalculateMinCost(Location _startLocation)
> {
>     //Initialise a new empty route list
>     Dictionary _shortestPaths = new Dictionary();
>     //Initialise a new empty handled locations list
>     List _handledLocations = new List();
>
>     //Initialise the new routes. the constructor will set the route weight
> to in.max
>     foreach (Location location in _locations)
>     {
>         _shortestPaths.Add(location, new Route(location.Identifier));
>     }
>
>     //The startPosition has a weight 0.
>     _shortestPaths[_startLocation].Cost = 0;
>
>     //If all locations are handled, stop the engine and return the result
>     while (_handledLocations.Count != _locations.Count)
>     {
>         //Order the locations
>         List _shortestLocations = (List < Location > )(from s in
> _shortestPaths
>                                 orderby s.Value.Cost
>                                 select s.Key).ToList();
>
>         Location _locationToProcess = null;
>
>         //Search for the nearest location that isn't handled
>         foreach (Location _location in _shortestLocations)
>         {
>             if (!_handledLocations.Contains(_location))
>             {
>                 //If the cost equals int.max, there are no more possible
> connections
>                 //to the remaining locations
>                 if (_shortestPaths[_location].Cost == int.MaxValue)
>                     return _shortestPaths;
>                 _locationToProcess = _location;
>                 break;
>             }
>         }
>
>         //Select all connections where the startposition is the location to
> Process
>         var _selectedConnections = from c in _connections
>                                    where c.A == _locationToProcess
>                                    select c;
>
>         //Iterate through all connections and search for a connection which
> is shorter
>         foreach (Connection conn in _selectedConnections)
>         {
>             if (_shortestPaths[conn.B].Cost > conn.Weight +
> _shortestPaths[conn.A].Cost)
>             {
>                 _shortestPaths[conn.B].Connections =
>                         _shortestPaths[conn.A].Connections.ToList();
>                 _shortestPaths[conn.B].Connections.Add(conn);
>                 _shortestPaths[conn.B].Cost = conn.Weight +
> _shortestPaths[conn.A].Cost;
>             }
>         }
>         //Add the location to the list of processed locations
>         _handledLocations.Add(_locationToProcess);
>     }
>
>     return _shortestPaths;
> }
>
> Thanks
> Martin-
> ----- Original Message -----
> Wrom: PKYLEJGDGVCJVTLBXFGGMEPYOQKEDOTWFAOBUZXUWLSZL
> To: <mysql@stripped>
> Sent: Saturday, March 01, 2008 7:19 PM
> Subject: Re: Efficiently storing a directed graph
>
>
>   
>> Kelly,
>>
>>     
>>> I'm not married to using SQL: are there other efficient solutions to
>>> store directed graphs? Could I hack something up in Perl or Ruby and
>>> then serialize my in-memory graph to a file (for efficient
>>> saving/reloading)?
>>>       
>> Did you look at Dijkstra's algorithm?
>>
>> PB
>>
>> --
>> MySQL General Mailing List
>> For list archives: http://lists.mysql.com/mysql
>> To unsubscribe:    http://lists.mysql.com/mysql?unsub=mgainty@stripped
>>
>>
>>     
>
>
>
>   

--------------020800000506090302010600--