wolffd@0: % ---
wolffd@0: % mother class for the directed clip graph classes
wolffd@0: % contains general purpose and graph-theorethical
wolffd@0: % functions
wolffd@0: % ---
wolffd@0: % we consider the similarity between clips
wolffd@0: % as symmetric, thus sim(a,b) = sim(b,a)
wolffd@0: % this makes the set of nodes much smaller
wolffd@0: % ---
wolffd@0: 
wolffd@0: % ---
wolffd@0: % TODO: change structure to 
wolffd@0: % avoid using Vclips, mapping clip ids
wolffd@0: % into a node number 00id1..00id2,
wolffd@0: % 
wolffd@0: % Enables full integration into Digraph / Graph class
wolffd@0: % ---
wolffd@0: 
wolffd@0: classdef ClipPairGraph < DiGraph
wolffd@0:     
wolffd@0:     properties(Hidden)
wolffd@0:         
wolffd@0:         max_clipid = 10^6;
wolffd@0:         vid_map;
wolffd@0:         vid_last = 0;
wolffd@0:     end
wolffd@0:     
wolffd@0: methods
wolffd@0: 
wolffd@0: % ---
wolffd@0: % Constructor
wolffd@0: % ---
wolffd@0: function G = ClipPairGraph(comparison)
wolffd@0:     
wolffd@0:     if nargin == 0
wolffd@0:         
wolffd@0:     G.vid_map = containers.Map('KeyType', 'double', 'ValueType', 'double');
wolffd@0: 
wolffd@0:     elseif nargin == 1
wolffd@0:         
wolffd@0:         G = ClipPairGraph();
wolffd@0: 
wolffd@0:         % ---
wolffd@0:         % Add the input graph to the empty one
wolffd@0:         % ---
wolffd@0:         G.add_graph(comparison);
wolffd@0:         
wolffd@0:         clas = cat(1, class(comparison), superclasses(comparison));
wolffd@0:         if strcellfind(clas, 'ClipPairGraph')
wolffd@0:             
wolffd@0:             G.vid_map = comparison.vid_map; 
wolffd@0:         end
wolffd@0:     end
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: % Node id by clip
wolffd@0: % ---
wolffd@0: function Vid = node(G, a, b)
wolffd@0: 
wolffd@0:     % did we get just one clip?
wolffd@0:     if nargin == 2
wolffd@0:         % ---
wolffd@0:         % TODO: this is terribly ineffective
wolffd@0:         % create all possible pairs and search if they exist
wolffd@0:         % ---
wolffd@0:         Vid = [];
wolffd@0:         for b = G.clips()';
wolffd@0: 
wolffd@0:             sm = min([a b]);
wolffd@0:             bg = max([a b]);
wolffd@0:             hash = G.max_clipid *bg + sm;
wolffd@0: 
wolffd@0:             % ---
wolffd@0:             % does this pair exist? if so: return Vid
wolffd@0:             % ---
wolffd@0:             if G.vid_map.isKey(hash)
wolffd@0:                 Vid(end+1) = G.vid_map(hash);
wolffd@0:             end
wolffd@0:         end
wolffd@0:         
wolffd@0:         % Ah no, we got the 2 clips
wolffd@0:     else
wolffd@0:     
wolffd@0:         % ---
wolffd@0:         % hash function for clip pair
wolffd@0:         % ---
wolffd@0:         % sort clip ids
wolffd@0:         sm = min([a b]);
wolffd@0:         bg = max([a b]);
wolffd@0: 
wolffd@0:         % ---
wolffd@0:         % get node code: 
wolffd@0:         % max_clipid * bg + sm
wolffd@0:         % ---
wolffd@0:         hash = G.max_clipid *bg + sm;
wolffd@0: 
wolffd@0:         % ---
wolffd@0:         % table lookup
wolffd@0:         % ---
wolffd@0:         if G.vid_map.isKey(hash)
wolffd@0: 
wolffd@0:             Vid = G.vid_map(hash);
wolffd@0:         else
wolffd@0: 
wolffd@0:             % ---
wolffd@0:             % create new psition in hash table and 
wolffd@0:             % assign this ID to the node
wolffd@0:             % ---
wolffd@0:             G.vid_last = G.vid_last + 1;
wolffd@0:             Vid = G.vid_last;
wolffd@0: 
wolffd@0:             G.vid_map(hash) = Vid;
wolffd@0: 
wolffd@0:             % ---
wolffd@0:             % NOTE: this is intended for maybe swithcingto 
wolffd@0:             % cell descriptions in future.
wolffd@0:             % The node ids will be stored as well
wolffd@0:             % ---
wolffd@0:             G.Vlbl{Vid} = G.label(Vid);
wolffd@0:         end
wolffd@0:     end
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: % Returns all clip ids referenced in the Graph
wolffd@0: % ---
wolffd@0: function [a] = clips(G)
wolffd@0:     
wolffd@0:     [sm, bg] = G.clipsN(G.nodes);
wolffd@0:     a = unique([sm; bg]);
wolffd@0: end
wolffd@0: 
wolffd@0: 
wolffd@0: % ---
wolffd@0: % Clip ids for Node
wolffd@0: % ---
wolffd@0: function [sm, bg] = clipsN(G, Vid)
wolffd@0:     
wolffd@0:     % get all clips referenced in this graph
wolffd@0:     if numel(Vid) > 1
wolffd@0:         sm = [];
wolffd@0:         bg = [];
wolffd@0:         for i = 1:numel(Vid);
wolffd@0:             [sm(end+1), bg(end+1)] = G.clipsN(Vid(i));
wolffd@0:         end
wolffd@0:     else
wolffd@0:     
wolffd@0:        % ---
wolffd@0:        % TODO: There must be a more efficient way to do this
wolffd@0:        % ---
wolffd@0:        % get all hash data
wolffd@0: 
wolffd@0:        all_hashs = G.vid_map.values();
wolffd@0:        all_keys = G.vid_map.keys();
wolffd@0:        % ---
wolffd@0:        % search for this Node ID and return hash value
wolffd@0:        % ---
wolffd@0:        hash = all_keys{cell2mat(all_hashs) == Vid};
wolffd@0: 
wolffd@0:        sm = mod(hash, G.max_clipid);
wolffd@0:        bg = div(hash, G.max_clipid);
wolffd@0:     end
wolffd@0: end
wolffd@0: 
wolffd@0: 
wolffd@0: % ---
wolffd@0: % Edge weight by clip id
wolffd@0: % ---
wolffd@0: function [weight, V1, V2] = edge(G, a, b, c)
wolffd@0: 
wolffd@0:     if nargin == 4
wolffd@0:         V1 = add_node(G, a, b);
wolffd@0:         V2 = add_node(G, a, c);
wolffd@0:         
wolffd@0:     elseif nargin == 3
wolffd@0:         V1 = a;
wolffd@0:         V2 = b;
wolffd@0:     end
wolffd@0: 
wolffd@0:     weight = edge@DiGraph(G, V1, V2);
wolffd@0: end
wolffd@0: 
wolffd@0: function [weight, varargout] = edges(G,a,b)
wolffd@0:     
wolffd@0:     % all edges or from specified node ?
wolffd@0:     if nargin >= 2
wolffd@0:         
wolffd@0:         % is there a clip pair or node number input?
wolffd@0:         if nargin == 3
wolffd@0:             V1 = add_node(G, a, b);
wolffd@0: 
wolffd@0:         elseif nargin == 2
wolffd@0:             V1 = a;
wolffd@0:         end
wolffd@0:         
wolffd@0:         [weight, V1, V2] = edges@DiGraph(G, V1);
wolffd@0:         
wolffd@0:     else
wolffd@0:         % ---
wolffd@0:         % ok, get ALL edges
wolffd@0:         % ---
wolffd@0:         [weight, V1, V2] = edges@DiGraph(G);
wolffd@0:     end
wolffd@0: 
wolffd@0:     % how to represent the output
wolffd@0:     if nargout <= 3
wolffd@0:         varargout{1} = V1;
wolffd@0:         varargout{2} = V2;
wolffd@0:     else
wolffd@0:         % ---
wolffd@0:         % get all the clips from the edges
wolffd@0:         % ---
wolffd@0:         ao = zeros(1,numel(V1));
wolffd@0:         bo = zeros(1,numel(V1));
wolffd@0:         co = zeros(1,numel(V1));
wolffd@0:         for i =1:numel(V1)
wolffd@0:             [ao(i), bo(i), co(i)] = G.clipsE(V1(i), V2(i));
wolffd@0:         end
wolffd@0:         varargout{1} = ao;
wolffd@0:         varargout{2} = bo;
wolffd@0:         varargout{3} = co;
wolffd@0:     end
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: % add an edge saying sim(a,b) > sim(a,c)
wolffd@0: % ---
wolffd@0: function add_edge(G, a, b, c, weight)
wolffd@0:     
wolffd@0:     if nargin == 5
wolffd@0:         V1 = add_node(G, a, b);
wolffd@0:         V2 = add_node(G, a, c);
wolffd@0:         
wolffd@0:     elseif nargin == 4
wolffd@0:         V1 = a;
wolffd@0:         V2 = b;
wolffd@0:         weight = c;
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % call superclass
wolffd@0:     % --- 
wolffd@0:     add_edge@DiGraph(G, V1, V2, weight);
wolffd@0: 
wolffd@0: end
wolffd@0: 
wolffd@0: function Vid = add_node(G, a, b)
wolffd@0: 
wolffd@0:     if nargin == 3
wolffd@0:         Vid = G.node(a,b);
wolffd@0:     else
wolffd@0:         Vid = a;
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % call superclass
wolffd@0:     % ---
wolffd@0:     add_node@DiGraph(G, Vid);
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: % the pairgraph variant of add_graph also updates the 
wolffd@0: % clip id hashmap
wolffd@0: % ----
wolffd@0: function add_graph(G, G2)
wolffd@0:     
wolffd@0:     % determine if symmetric  edges have to be added
wolffd@0:     clas = cat(1, class(G2), superclasses(G2));
wolffd@0:     if strcellfind(clas, 'Graph')
wolffd@0:         add_symm = 1;
wolffd@0:     else
wolffd@0:         add_symm = 0;
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % add all nodes and edges in G2
wolffd@0:     % ---
wolffd@0:     for V = G2.nodes();
wolffd@0:         
wolffd@0:         [a, count] = sscanf(G2.label(V),'%u:%u');
wolffd@0:         
wolffd@0:         if count == 2
wolffd@0:             b = a(2);
wolffd@0:             a = a(1);
wolffd@0:             
wolffd@0:             G.add_node(a,b);
wolffd@0:         else
wolffd@0:             G.add_node(V);
wolffd@0:         end
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % NOTE / TODO: 
wolffd@0:     % this LABEL inheritance is far too expensive when 
wolffd@0:     % creating many copiesof the same graph
wolffd@0:     % Its also unnessecary for lots of them 
wolffd@0:     % except for debugging :(. 
wolffd@0:     % ---
wolffd@0:     G.Vlbl = cell(1, numel(G2.V));
wolffd@0:     if G2.cardinality > 1
wolffd@0:         G.Vlbl(G.nodes()) = G2.label(G2.nodes());
wolffd@0:     else
wolffd@0:         G.Vlbl(G.nodes()) = {G2.label(G2.nodes())};
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % get all edges in G2
wolffd@0:     % CAVE: if we added the edges above using 
wolffd@0:     %       label clip indices, we have to address them 
wolffd@0:     %       using these below!
wolffd@0:     % ---
wolffd@0:     [val, V1, V2] = edges(G2);
wolffd@0:     
wolffd@0:     for i = 1:numel(val)
wolffd@0:         
wolffd@0:         % ---
wolffd@0:         % add edges to graph
wolffd@0:         % NOTE: we assume either all or no edges
wolffd@0:         % are labeled with clip indices
wolffd@0:         % ---
wolffd@0:         if count == 2
wolffd@0:             % ---
wolffd@0:             % ok, they were labeled above, 
wolffd@0:             % so index by clips.
wolffd@0:             %
wolffd@0:             % TODO:
wolffd@0:             % 1. get rid of this sscanf stuff and use add_edge for 
wolffd@0:             %  creating the nodes first, the only add single nodes
wolffd@0:             % 2. use cell labels globally instead of hashmap here
wolffd@0:             
wolffd@0:             [u, count] = sscanf(G2.label(V1(i)),'%u:%u');
wolffd@0:             [v, count] = sscanf(G2.label(V2(i)),'%u:%u');
wolffd@0:             
wolffd@0:             a = intersect(u,v);
wolffd@0:             b = setdiff(u,a);
wolffd@0:             c = setdiff(v,a);
wolffd@0:             
wolffd@0:             G.add_edge(a, b, c, val(i));
wolffd@0:             
wolffd@0:             if add_symm
wolffd@0:                 % ---
wolffd@0:                 % add symmetric edges to graph
wolffd@0:                 % ---
wolffd@0:                 G.add_edge(a, c, b, val(i));
wolffd@0:             end
wolffd@0:         
wolffd@0:         else
wolffd@0:             G.add_edge(V1(i), V2(i), val(i));
wolffd@0:             
wolffd@0:              if add_symm
wolffd@0:                 % ---
wolffd@0:                 % add symmetric edges to graph
wolffd@0:                 % ---
wolffd@0:                 G.add_edge(V2(i), V1(i), val(i));
wolffd@0:             end
wolffd@0:         
wolffd@0:         end
wolffd@0:         
wolffd@0:        
wolffd@0:     end
wolffd@0: 
wolffd@0: end
wolffd@0: 
wolffd@0: function remove_node(G, a, b)
wolffd@0: 
wolffd@0:     if nargin == 3
wolffd@0:         Vid = G.node(a,b);
wolffd@0:     else
wolffd@0:         Vid = a;
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % call superclass
wolffd@0:     % ---
wolffd@0:     remove_node@DiGraph(G, Vid);
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: % Clip ids for Edge
wolffd@0: % ---
wolffd@0: function [a,b,c] = clipsE(G, V1, V2)
wolffd@0:     
wolffd@0:    [c1, c2] = clipsN(G, V1);
wolffd@0:    [c3, c4] = clipsN(G, V2);
wolffd@0:    
wolffd@0:    % common clip
wolffd@0:    a = intersect([c1 c2],[c3 c4]);
wolffd@0:    
wolffd@0:    % nearer (similar) clip
wolffd@0:    b = setdiff([c1 c2],a);
wolffd@0:    
wolffd@0:    % far clip
wolffd@0:    c = setdiff([c3 c4],a);
wolffd@0:    
wolffd@0:    if isempty(a)
wolffd@0:        error 'clip similarity graph inconsistent'
wolffd@0:    end
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: function out = label(G, Vid)
wolffd@0:     
wolffd@0:     if nargin == 1
wolffd@0:         out = cell(numel(G.V), 1);
wolffd@0:         Vid = 1:numel(G.V);
wolffd@0:     end
wolffd@0:     
wolffd@0:     for i = 1:numel(Vid)
wolffd@0:         if (numel(G.Vlbl) < Vid(i)) || isempty(G.Vlbl{Vid(i)})
wolffd@0: 
wolffd@0:             [sm, bg] = G.clipsN(Vid(i));
wolffd@0:             
wolffd@0:             if numel(Vid) > 1
wolffd@0:                 out{i} = sprintf('%d:%d', sm, bg);
wolffd@0:             else
wolffd@0:                 out = sprintf('%d:%d', sm, bg);
wolffd@0:             end
wolffd@0:         else
wolffd@0:             if numel(Vid) > 1
wolffd@0:                 out{i} = G.Vlbl{Vid(i)};
wolffd@0:             else
wolffd@0:                 out = G.Vlbl{Vid(i)};
wolffd@0:             end
wolffd@0:         end
wolffd@0:     end   
wolffd@0: end
wolffd@0: 
wolffd@0: % ---
wolffd@0: % determines if Edges in G2 are the same as in G
wolffd@0: % ---
wolffd@0: function out = le(a,b)
wolffd@0:     out = isSubgraph(a, b);
wolffd@0: end
wolffd@0: 
wolffd@0: function [out] = isSubgraph(G, G2)
wolffd@0:      
wolffd@0:     [val, V1, V2] = G2.edges();
wolffd@0:     
wolffd@0:     i = 1;
wolffd@0:     while i <= numel(V1)
wolffd@0:         % ---
wolffd@0:         % Test if edge exists in other graph, 
wolffd@0:         % using clips as identifier
wolffd@0:         % ---
wolffd@0:         [a,b,c] = G2.clipsE(V1(i), V2(i));
wolffd@0:         
wolffd@0:         if G.edge(a,b,c) ~= val(i)
wolffd@0:            out = 0;
wolffd@0:            return,
wolffd@0:         end
wolffd@0:         i = i + 1;
wolffd@0:     end
wolffd@0:     out = 1;
wolffd@0: end
wolffd@0: 
wolffd@0: 
wolffd@0: function [Gout] = minus(a, b)
wolffd@0:     Gout = feval(class(a),a);
wolffd@0:     Gout.remove_graph(b);
wolffd@0: end
wolffd@0: 
wolffd@0: function remove_graph(G, G2)
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % Get Edges in G2 and remove them
wolffd@0:     % ---
wolffd@0:     [~, V1, V2] = G2.edges();
wolffd@0:     for i = 1:numel(V1)
wolffd@0:         % ---
wolffd@0:         % Test if edge exists in other graph, 
wolffd@0:         % using clips as identifier
wolffd@0:         % ---
wolffd@0:         [a,b,c] = G2.clipsE(V1(i), V2(i));
wolffd@0:         
wolffd@0:         G.remove_edge(a,b,c);
wolffd@0:     end
wolffd@0:     
wolffd@0:     % ---
wolffd@0:     % Note : we only remove nodes with no 
wolffd@0:     % remaining incoming edges
wolffd@0:     % ---
wolffd@0:     V = G2.nodes();
wolffd@0:     for i = 1:numel(V)
wolffd@0:         
wolffd@0:         % ---
wolffd@0:         % get corresponding node in G via clips
wolffd@0:         % ---
wolffd@0:         [a,b] = G2.clipsN(V(i));
wolffd@0:         
wolffd@0:         Vid = node(G, a, b);
wolffd@0:         if G.degree(Vid) == 0
wolffd@0: 
wolffd@0:             G.remove_node(Vid);
wolffd@0:         end
wolffd@0:     end 
wolffd@0: end
wolffd@0: end
wolffd@0: end