Mercurial > hg > camir-aes2014
view core/magnatagatune/ClipPairGraph.m @ 0:e9a9cd732c1e tip
first hg version after svn
author | wolffd |
---|---|
date | Tue, 10 Feb 2015 15:05:51 +0000 |
parents | |
children |
line wrap: on
line source
% --- % 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