Mercurial > hg > camir-aes2014
diff 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 diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/core/magnatagatune/ClipPairGraph.m Tue Feb 10 15:05:51 2015 +0000 @@ -0,0 +1,499 @@ +% --- +% 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 \ No newline at end of file