view core/magnatagatune/ClipPairGraph.m @ 0:e9a9cd732c1e tip

first hg version after svn

% ---
% mother class for the directed clip graph classes
% contains general purpose and graph-theorethical
% functions
% ---
% we consider the similarity between clips
% as symmetric, thus sim(a,b) = sim(b,a)
% this makes the set of nodes much smaller
% ---

% ---
% TODO: change structure to 
% avoid using Vclips, mapping clip ids
% into a node number 00id1..00id2,
% 
% Enables full integration into Digraph / Graph class
% ---

classdef ClipPairGraph < DiGraph
    
    properties(Hidden)
        
        max_clipid = 10^6;
        vid_map;
        vid_last = 0;
    end
    
methods

% ---
% Constructor
% ---
function G = ClipPairGraph(comparison)
    
    if nargin == 0
        
    G.vid_map = containers.Map('KeyType', 'double', 'ValueType', 'double');

    elseif nargin == 1
        
        G = ClipPairGraph();

        % ---
        % Add the input graph to the empty one
        % ---
        G.add_graph(comparison);
        
        clas = cat(1, class(comparison), superclasses(comparison));
        if strcellfind(clas, 'ClipPairGraph')
            
            G.vid_map = comparison.vid_map; 
        end
    end
end

% ---
% Node id by clip
% ---
function Vid = node(G, a, b)

    % did we get just one clip?
    if nargin == 2
        % ---
        % TODO: this is terribly ineffective
        % create all possible pairs and search if they exist
        % ---
        Vid = [];
        for b = G.clips()';

            sm = min([a b]);
            bg = max([a b]);
            hash = G.max_clipid *bg + sm;

            % ---
            % does this pair exist? if so: return Vid
            % ---
            if G.vid_map.isKey(hash)
                Vid(end+1) = G.vid_map(hash);
            end
        end
        
        % Ah no, we got the 2 clips
    else
    
        % ---
        % hash function for clip pair
        % ---
        % sort clip ids
        sm = min([a b]);
        bg = max([a b]);

        % ---
        % get node code: 
        % max_clipid * bg + sm
        % ---
        hash = G.max_clipid *bg + sm;

        % ---
        % table lookup
        % ---
        if G.vid_map.isKey(hash)

            Vid = G.vid_map(hash);
        else

            % ---
            % create new psition in hash table and 
            % assign this ID to the node
            % ---
            G.vid_last = G.vid_last + 1;
            Vid = G.vid_last;

            G.vid_map(hash) = Vid;

            % ---
            % NOTE: this is intended for maybe swithcingto 
            % cell descriptions in future.
            % The node ids will be stored as well
            % ---
            G.Vlbl{Vid} = G.label(Vid);
        end
    end
end

% ---
% Returns all clip ids referenced in the Graph
% ---
function [a] = clips(G)
    
    [sm, bg] = G.clipsN(G.nodes);
    a = unique([sm; bg]);
end


% ---
% Clip ids for Node
% ---
function [sm, bg] = clipsN(G, Vid)
    
    % get all clips referenced in this graph
    if numel(Vid) > 1
        sm = [];
        bg = [];
        for i = 1:numel(Vid);
            [sm(end+1), bg(end+1)] = G.clipsN(Vid(i));
        end
    else
    
       % ---
       % TODO: There must be a more efficient way to do this
       % ---
       % get all hash data

       all_hashs = G.vid_map.values();
       all_keys = G.vid_map.keys();
       % ---
       % search for this Node ID and return hash value
       % ---
       hash = all_keys{cell2mat(all_hashs) == Vid};

       sm = mod(hash, G.max_clipid);
       bg = div(hash, G.max_clipid);
    end
end


% ---
% Edge weight by clip id
% ---
function [weight, V1, V2] = edge(G, a, b, c)

    if nargin == 4
        V1 = add_node(G, a, b);
        V2 = add_node(G, a, c);
        
    elseif nargin == 3
        V1 = a;
        V2 = b;
    end

    weight = edge@DiGraph(G, V1, V2);
end

function [weight, varargout] = edges(G,a,b)
    
    % all edges or from specified node ?
    if nargin >= 2
        
        % is there a clip pair or node number input?
        if nargin == 3
            V1 = add_node(G, a, b);

        elseif nargin == 2
            V1 = a;
        end
        
        [weight, V1, V2] = edges@DiGraph(G, V1);
        
    else
        % ---
        % ok, get ALL edges
        % ---
        [weight, V1, V2] = edges@DiGraph(G);
    end

    % how to represent the output
    if nargout <= 3
        varargout{1} = V1;
        varargout{2} = V2;
    else
        % ---
        % get all the clips from the edges
        % ---
        ao = zeros(1,numel(V1));
        bo = zeros(1,numel(V1));
        co = zeros(1,numel(V1));
        for i =1:numel(V1)
            [ao(i), bo(i), co(i)] = G.clipsE(V1(i), V2(i));
        end
        varargout{1} = ao;
        varargout{2} = bo;
        varargout{3} = co;
    end
end

% ---
% add an edge saying sim(a,b) > sim(a,c)
% ---
function add_edge(G, a, b, c, weight)
    
    if nargin == 5
        V1 = add_node(G, a, b);
        V2 = add_node(G, a, c);
        
    elseif nargin == 4
        V1 = a;
        V2 = b;
        weight = c;
    end
    
    % ---
    % call superclass
    % --- 
    add_edge@DiGraph(G, V1, V2, weight);

end

function Vid = add_node(G, a, b)

    if nargin == 3
        Vid = G.node(a,b);
    else
        Vid = a;
    end
    
    % ---
    % call superclass
    % ---
    add_node@DiGraph(G, Vid);
end

% ---
% the pairgraph variant of add_graph also updates the 
% clip id hashmap
% ----
function add_graph(G, G2)
    
    % determine if symmetric  edges have to be added
    clas = cat(1, class(G2), superclasses(G2));
    if strcellfind(clas, 'Graph')
        add_symm = 1;
    else
        add_symm = 0;
    end
    
    % ---
    % add all nodes and edges in G2
    % ---
    for V = G2.nodes();
        
        [a, count] = sscanf(G2.label(V),'%u:%u');
        
        if count == 2
            b = a(2);
            a = a(1);
            
            G.add_node(a,b);
        else
            G.add_node(V);
        end
    end
    
    % ---
    % NOTE / TODO: 
    % this LABEL inheritance is far too expensive when 
    % creating many copiesof the same graph
    % Its also unnessecary for lots of them 
    % except for debugging :(. 
    % ---
    G.Vlbl = cell(1, numel(G2.V));
    if G2.cardinality > 1
        G.Vlbl(G.nodes()) = G2.label(G2.nodes());
    else
        G.Vlbl(G.nodes()) = {G2.label(G2.nodes())};
    end
    
    % ---
    % get all edges in G2
    % CAVE: if we added the edges above using 
    %       label clip indices, we have to address them 
    %       using these below!
    % ---
    [val, V1, V2] = edges(G2);
    
    for i = 1:numel(val)
        
        % ---
        % add edges to graph
        % NOTE: we assume either all or no edges
        % are labeled with clip indices
        % ---
        if count == 2
            % ---
            % ok, they were labeled above, 
            % so index by clips.
            %
            % TODO:
            % 1. get rid of this sscanf stuff and use add_edge for 
            %  creating the nodes first, the only add single nodes
            % 2. use cell labels globally instead of hashmap here
            
            [u, count] = sscanf(G2.label(V1(i)),'%u:%u');
            [v, count] = sscanf(G2.label(V2(i)),'%u:%u');
            
            a = intersect(u,v);
            b = setdiff(u,a);
            c = setdiff(v,a);
            
            G.add_edge(a, b, c, val(i));
            
            if add_symm
                % ---
                % add symmetric edges to graph
                % ---
                G.add_edge(a, c, b, val(i));
            end
        
        else
            G.add_edge(V1(i), V2(i), val(i));
            
             if add_symm
                % ---
                % add symmetric edges to graph
                % ---
                G.add_edge(V2(i), V1(i), val(i));
            end
        
        end
        
       
    end

end

function remove_node(G, a, b)

    if nargin == 3
        Vid = G.node(a,b);
    else
        Vid = a;
    end
    
    % ---
    % call superclass
    % ---
    remove_node@DiGraph(G, Vid);
end

% ---
% Clip ids for Edge
% ---
function [a,b,c] = clipsE(G, V1, V2)
    
   [c1, c2] = clipsN(G, V1);
   [c3, c4] = clipsN(G, V2);
   
   % common clip
   a = intersect([c1 c2],[c3 c4]);
   
   % nearer (similar) clip
   b = setdiff([c1 c2],a);
   
   % far clip
   c = setdiff([c3 c4],a);
   
   if isempty(a)
       error 'clip similarity graph inconsistent'
   end
end

% ---
function out = label(G, Vid)
    
    if nargin == 1
        out = cell(numel(G.V), 1);
        Vid = 1:numel(G.V);
    end
    
    for i = 1:numel(Vid)
        if (numel(G.Vlbl) < Vid(i)) || isempty(G.Vlbl{Vid(i)})

            [sm, bg] = G.clipsN(Vid(i));
            
            if numel(Vid) > 1
                out{i} = sprintf('%d:%d', sm, bg);
            else
                out = sprintf('%d:%d', sm, bg);
            end
        else
            if numel(Vid) > 1
                out{i} = G.Vlbl{Vid(i)};
            else
                out = G.Vlbl{Vid(i)};
            end
        end
    end   
end

% ---
% determines if Edges in G2 are the same as in G
% ---
function out = le(a,b)
    out = isSubgraph(a, b);
end

function [out] = isSubgraph(G, G2)
     
    [val, V1, V2] = G2.edges();
    
    i = 1;
    while i <= numel(V1)
        % ---
        % Test if edge exists in other graph, 
        % using clips as identifier
        % ---
        [a,b,c] = G2.clipsE(V1(i), V2(i));
        
        if G.edge(a,b,c) ~= val(i)
           out = 0;
           return,
        end
        i = i + 1;
    end
    out = 1;
end


function [Gout] = minus(a, b)
    Gout = feval(class(a),a);
    Gout.remove_graph(b);
end

function remove_graph(G, G2)
    
    % ---
    % Get Edges in G2 and remove them
    % ---
    [~, V1, V2] = G2.edges();
    for i = 1:numel(V1)
        % ---
        % Test if edge exists in other graph, 
        % using clips as identifier
        % ---
        [a,b,c] = G2.clipsE(V1(i), V2(i));
        
        G.remove_edge(a,b,c);
    end
    
    % ---
    % Note : we only remove nodes with no 
    % remaining incoming edges
    % ---
    V = G2.nodes();
    for i = 1:numel(V)
        
        % ---
        % get corresponding node in G via clips
        % ---
        [a,b] = G2.clipsN(V(i));
        
        Vid = node(G, a, b);
        if G.degree(Vid) == 0

            G.remove_node(Vid);
        end
    end 
end
end
end