--
-- G-alaxy Stored Procedures
--
-- by Alan G. Labouseur
--    alan@labosueur.com
-- 

-- drop function shortestPath(integer, integer);
create or replace function shortestPath(graphId integer,                  -- See CLRS chapter 24, pages 643-662 (in the 3rd edition) 
                                     fromVertex integer) returns boolean   -- for single-source shortest path algorithm stuff.

as $$
declare
    numVertexesInGraph integer;
    e                  record; -- Index variable used to iterate over the edges.
    fromVertexEst      real;
    toVertexEst        real;
    currentEdgeWeight  real;
    newEst             real;
begin
    -- Progress report:
    --RAISE NOTICE 'Computing shortest path from vertex % to all other vertexex in graph %.', fromVertex, graphId;
    --RAISE NOTICE '';
    
    -- Initialize the vertex data. (CLRS 3ed, page 648)
    -- Set all of the single-source shortest path estimate values to something like infinity and 
    -- set all of vertex predecessors to null.
    update Vertexes 
    set sssp_est  = 32768, -- TODO: Use a more natural stand-in for infinity. (MaxInt() or something.)
        sssp_pred = NULL
    where Vertexes.gid = graphId;

    -- Set our fromVertex's sssp_est to 0, since we're already there. (CLRS 3ed, page 648)
    update Vertexes
    set sssp_est = 0
    where Vertexes.gid = graphId
      and Vertexes.vid = fromVertex;

    -- Iterate over all of the count(verticies in our target graph)-1 times
    select count(*) into strict numVertexesInGraph  from Vertexes where Vertexes.gid = graphId;    
    for i in 1 .. numVertexesInGraph - 1 loop
        -- Iterate over all of the edges in our target graph. 
        for e in select Edges.fromVertex, Edges.toVertex, Edges.weight from Edges where Edges.gid = graphId loop 
            -- Relax (CLRS 3ed, page 649)
            select Vertexes.sssp_est into strict fromVertexEst from Vertexes where Vertexes.gid = graphId and Vertexes.vid = e.fromVertex;
            select Vertexes.sssp_est into strict   toVertexEst from Vertexes where Vertexes.gid = graphId and Vertexes.vid = e.toVertex;
            currentEdgeWeight = coalesce(e.weight,1); -- NULL edge weights are coalesced to 1.
            --RAISE NOTICE 'Examining edge of weight % from v% (%) to v% (%)', currentEdgeWeight, e.fromVertex, fromVertexEst, e.toVertex, toVertexEst;
            if toVertexEst > (fromVertexEst + currentEdgeWeight) then
                -- Update the new path estimate and predecessor vertex for the current vertex (v).
                newEst := (fromVertexEst + currentEdgeWeight);
                --RAISE NOTICE 'Relaxing v% estimate from % to %.', e.toVertex, toVertexEst, newEst;
                update Vertexes set sssp_est = newEst, sssp_pred = e.fromVertex where Vertexes.gid = graphId and Vertexes.vid = e.toVertex;
            end if;
        --RAISE NOTICE '';
        end loop;
    end loop;    
    -- TODO: Check for negative cycles (CLRS 3ed page 651) and ROLLBACK if there are any. Else COMMIT.
    return true;
end;
$$ language plpgsql;

select shortestPath(0, 10);

select vid, sssp_est, sssp_pred
from Vertexes 
where gid = 0
order by vid

select sssp_est, count(sssp_est)
from Vertexes 
where gid = 0
group by sssp_est
order by sssp_est