%% Graph class difinition
% The class has a constructor g=Graph(map), whre map is mobility 2D matrix
% and following methos.
%
% function g=Reset(g): Reset properties in a node g.
%
% function [shortpathv g]=GetPath(g,init_node,final_node):getting shortest
% path from final_node to init node.
%
% function g=ComputeDistance(g,final_node): Computing sum of distance from
% final node to every node in the graph.
%
% function g=Visit(g,Queue): A recursive funtion in order to visit every
% node once.
%
% function [g Q]=UpdateWmin(g,parent_index):
%
% function shortpathxy=ShowPath(g,map,shortpathv)
%
%Author: Wasit Limprasert Email:wasit7(at)gmail.com Date:06Feb2012
classdef Graph
    properties        
        node_list %list of nodes in the graph
        node_index_map %mobility map matrix
        n
    end
    methods
        %% function g=Graph(map)
        % generating graph from a mobility map.
        function g=Graph(map)
            [xmax ymax]=size(map);
            node_list_index=0;
            mapv=zeros(xmax,ymax);
            for x=1:xmax
                for y=1:ymax
                    if map(x,y)
                        node_list_index=node_list_index+1;
                        mapv(x,y)=node_list_index;
                    end
                end
            end
            g.node_index_map=mapv;
            for x=1:xmax
                for y=1:ymax
                    parent=map(x,y);%mobility of the parent node.
                    if parent
                        %e1 e2 e3
                        %e4 v  e5
                        %e6 e7 e8
                        edge_list=[];
                        e=[];
                        if(x-1>=1&&y-1>=1)%e1
                            %mobility of the child node
                            childv=mapv(x-1,y-1);
                            child=map(x-1,y-1);
                            if child
                                e=Edge(childv,2.828/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end                        
                        if(x-1>=1)%e2
                            childv=mapv(x-1,y);
                            child=map(x-1,y);
                            if child
                                e=Edge(childv,2/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        if(x-1>=1&&y+1<=ymax)%e3
                            childv=mapv(x-1,y+1);
                            child=map(x-1,y+1);
                            if child
                                e=Edge(childv,2.828/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        if(y-1>=1)%e4
                            childv=mapv(x,y-1);
                            child=map(x,y-1);
                            if child
                                e=Edge(childv,2/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        if(y+1<=ymax)%e5
                            childv=mapv(x,y+1);
                            child=map(x,y+1);
                            if child
                                e=Edge(childv,2/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        if(x+1<=xmax&&y-1>=1)%e6
                            childv=mapv(x+1,y-1);
                            child=map(x+1,y-1);
                            if child
                                e=Edge(childv,2.828/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        if(x+1<=xmax)%e7
                            childv=mapv(x+1,y);
                            child=map(x+1,y);
                            if child
                                e=Edge(childv,2/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        if(x+1<=xmax&&y+1<=ymax)%e8
                            childv=mapv(x+1,y+1);
                            child=map(x+1,y+1);
                            if child
                                e=Edge(childv,2.828/(child+parent));
                                edge_list=[edge_list; e];
                            end
                        end
                        n=size(edge_list,1);
                        wmin=Inf;
                        vmin=0;
                        visited=0;
                        posx=x;
                        posy=y;
                        v=Node(posx,posy,visited,wmin,vmin,n,edge_list);
                        g.node_list=[g.node_list; v];
                    end
                end
            end
            %g.n=size(g.node_list,1);
        end
        %% function g=Reset(g)
        % initializing node parameters.
        function g=Reset(g)
            for i=1:size(g.node_list)
                g.node_list(i).visited=0;
                g.node_list(i).wmin=Inf;
                g.node_list(i).vmin=0;
            end
        end
        %% function [shortpathv g]=GetPath(g,init_node,final_node)
        % Displaying nodes index on shortest path after visiting all nodes.
        function [shortpathv g]=GetPath(g,init_node,final_node)
           g=Reset(g);
           g=ComputeDistance(g,final_node);
           shortpathv=[init_node];
           if final_node>0               
               if g.node_list(init_node).vmin
                   v=init_node;
                   while v~=final_node
                        v=g.node_list(v).vmin;
                        shortpathv=[shortpathv v];
                   end
                   disp('--->Found.')
                   shortpathv=[shortpathv final_node];
               else
                   disp('--->Could not found.')
                   shortpathv=[init_node];
               end
           end
        end
        %% function g=ComputeDistance(g,final_node) 
        % Computing shortest distance from final_node to all nodes in the
        % graph.
        function g=ComputeDistance(g,final_node)            
            g.node_list(final_node).wmin=0;
            g.node_list(final_node).vmin=final_node;
            g=Visit(g,final_node);
        end
        %% function g=Visit(g,Queue)
        % Visiting parent node in the list Queue. This is a recursive
        % function all nodes will be visited once and distacnce from a
        % particular node to final node will be computed recursively.
        function g=Visit(g,Queue)
            imax=size(Queue,1);
            Queue_next=[];
            for i=1:imax
                if ~g.node_list(Queue(i)).visited
                    [g Q]=UpdateWmin(g,Queue(i));
                    Queue_next=[Queue_next; Q];
                    g.node_list(Queue(i)).visited=1;
                end
            end
            if ~isempty(Queue_next)
                g=Visit(g,Queue_next);
            end
        end
        %% function [g Q]=UpdateWmin(g,parent_index)
        % Comparing and updating Wmin and Vmin in order to find shortest
        % path.
        function [g Q]=UpdateWmin(g,parent_index)
            %g graph
            parent=g.node_list(parent_index);
            num_child=parent.n; %number of edge of the child
            Q=[];
            for e=1:num_child
                edge=g.node_list(parent_index).edge_list(e); %edge from a parent node to a child node
                child=g.node_list(edge.node_index); %checking node
                neww=parent.wmin+edge.w;
                if neww<child.wmin
                    g.node_list(edge.node_index).wmin=neww;
                    g.node_list(edge.node_index).vmin=parent_index;
                end                
                if ~g.node_list(edge.node_index).visited
                    Q=[Q; edge.node_index];
                end
            end
        end
        %% function shortpathxy=ShowPath(g,map,shortpathv)
        % Displaying
        function shortpathxy=ShowPath(g,map,shortpathv)
            delete(gca);
            [xmax ymax]=size(map);
            
%             [x y]=meshgrid([0.5:xmax+0.5],[0.5:ymax+0.5]);
%             surface(x',y',zeros(xmax+1,ymax+1),[map zeros(xmax,1);zeros(1,ymax+1)],'EdgeColor','none');
%             colormap(gray(255));
%             hold on
            shortpathxy=[];
            lastv=size(shortpathv,2);
            for i=1:lastv
               shortpathxy=[shortpathxy [g.node_list(shortpathv(i)).posx; g.node_list(shortpathv(i)).posy]];
            end
%             plot(shortpathxy(1,:),shortpathxy(2,:),'r-','Linewidth',3)
%             plot(shortpathxy(1,lastv),shortpathxy(2,lastv),'s','MarkerFaceColor','g')
%             plot(shortpathxy(1,1),shortpathxy(2,1),'s','MarkerFaceColor','r')
%             camroll(270)
%             axis off
        end
    end
end