comparison 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