List:General Discussion« Previous MessageNext Message »
From:mgainty Date:March 2 2008 12:57am
Subject:Re: Efficiently storing a directed graph
View as plain text  
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=1
>
>

Thread
Efficiently storing a directed graphKelly Jones1 Mar
  • Re: Efficiently storing a directed graphPeter Brawley2 Mar
  • Re: Efficiently storing a directed graphmgainty2 Mar
    • Re: Efficiently storing a directed graphPeter Brawley2 Mar
  • Re: [GENERAL] Efficiently storing a directed graphJoe Conway2 Mar