Re: Efficiently storing a directed graph

[Peter Brawley]

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

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

PB

[EMAIL PROTECTED] 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@lists.mysql.com>
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/[EMAIL PROTECTED]