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
                                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
                //to the remaining locations
                if (_shortestPaths[_location].Cost == int.MaxValue)
                    return _shortestPaths;
                _locationToProcess = _location;

        //Select all connections where the startposition is the location to
        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.B].Connections =
                _shortestPaths[conn.B].Cost = conn.Weight +
        //Add the location to the list of processed locations

    return _shortestPaths;

----- Original Message -----
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:
> To unsubscribe:

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