Mercurial > hg > camir-aes2014
comparison 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 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:e9a9cd732c1e |
---|---|
1 % --- | |
2 % mother class for the directed clip graph classes | |
3 % contains general purpose and graph-theorethical | |
4 % functions | |
5 % --- | |
6 % we consider the similarity between clips | |
7 % as symmetric, thus sim(a,b) = sim(b,a) | |
8 % this makes the set of nodes much smaller | |
9 % --- | |
10 | |
11 % --- | |
12 % TODO: change structure to | |
13 % avoid using Vclips, mapping clip ids | |
14 % into a node number 00id1..00id2, | |
15 % | |
16 % Enables full integration into Digraph / Graph class | |
17 % --- | |
18 | |
19 classdef ClipPairGraph < DiGraph | |
20 | |
21 properties(Hidden) | |
22 | |
23 max_clipid = 10^6; | |
24 vid_map; | |
25 vid_last = 0; | |
26 end | |
27 | |
28 methods | |
29 | |
30 % --- | |
31 % Constructor | |
32 % --- | |
33 function G = ClipPairGraph(comparison) | |
34 | |
35 if nargin == 0 | |
36 | |
37 G.vid_map = containers.Map('KeyType', 'double', 'ValueType', 'double'); | |
38 | |
39 elseif nargin == 1 | |
40 | |
41 G = ClipPairGraph(); | |
42 | |
43 % --- | |
44 % Add the input graph to the empty one | |
45 % --- | |
46 G.add_graph(comparison); | |
47 | |
48 clas = cat(1, class(comparison), superclasses(comparison)); | |
49 if strcellfind(clas, 'ClipPairGraph') | |
50 | |
51 G.vid_map = comparison.vid_map; | |
52 end | |
53 end | |
54 end | |
55 | |
56 % --- | |
57 % Node id by clip | |
58 % --- | |
59 function Vid = node(G, a, b) | |
60 | |
61 % did we get just one clip? | |
62 if nargin == 2 | |
63 % --- | |
64 % TODO: this is terribly ineffective | |
65 % create all possible pairs and search if they exist | |
66 % --- | |
67 Vid = []; | |
68 for b = G.clips()'; | |
69 | |
70 sm = min([a b]); | |
71 bg = max([a b]); | |
72 hash = G.max_clipid *bg + sm; | |
73 | |
74 % --- | |
75 % does this pair exist? if so: return Vid | |
76 % --- | |
77 if G.vid_map.isKey(hash) | |
78 Vid(end+1) = G.vid_map(hash); | |
79 end | |
80 end | |
81 | |
82 % Ah no, we got the 2 clips | |
83 else | |
84 | |
85 % --- | |
86 % hash function for clip pair | |
87 % --- | |
88 % sort clip ids | |
89 sm = min([a b]); | |
90 bg = max([a b]); | |
91 | |
92 % --- | |
93 % get node code: | |
94 % max_clipid * bg + sm | |
95 % --- | |
96 hash = G.max_clipid *bg + sm; | |
97 | |
98 % --- | |
99 % table lookup | |
100 % --- | |
101 if G.vid_map.isKey(hash) | |
102 | |
103 Vid = G.vid_map(hash); | |
104 else | |
105 | |
106 % --- | |
107 % create new psition in hash table and | |
108 % assign this ID to the node | |
109 % --- | |
110 G.vid_last = G.vid_last + 1; | |
111 Vid = G.vid_last; | |
112 | |
113 G.vid_map(hash) = Vid; | |
114 | |
115 % --- | |
116 % NOTE: this is intended for maybe swithcingto | |
117 % cell descriptions in future. | |
118 % The node ids will be stored as well | |
119 % --- | |
120 G.Vlbl{Vid} = G.label(Vid); | |
121 end | |
122 end | |
123 end | |
124 | |
125 % --- | |
126 % Returns all clip ids referenced in the Graph | |
127 % --- | |
128 function [a] = clips(G) | |
129 | |
130 [sm, bg] = G.clipsN(G.nodes); | |
131 a = unique([sm; bg]); | |
132 end | |
133 | |
134 | |
135 % --- | |
136 % Clip ids for Node | |
137 % --- | |
138 function [sm, bg] = clipsN(G, Vid) | |
139 | |
140 % get all clips referenced in this graph | |
141 if numel(Vid) > 1 | |
142 sm = []; | |
143 bg = []; | |
144 for i = 1:numel(Vid); | |
145 [sm(end+1), bg(end+1)] = G.clipsN(Vid(i)); | |
146 end | |
147 else | |
148 | |
149 % --- | |
150 % TODO: There must be a more efficient way to do this | |
151 % --- | |
152 % get all hash data | |
153 | |
154 all_hashs = G.vid_map.values(); | |
155 all_keys = G.vid_map.keys(); | |
156 % --- | |
157 % search for this Node ID and return hash value | |
158 % --- | |
159 hash = all_keys{cell2mat(all_hashs) == Vid}; | |
160 | |
161 sm = mod(hash, G.max_clipid); | |
162 bg = div(hash, G.max_clipid); | |
163 end | |
164 end | |
165 | |
166 | |
167 % --- | |
168 % Edge weight by clip id | |
169 % --- | |
170 function [weight, V1, V2] = edge(G, a, b, c) | |
171 | |
172 if nargin == 4 | |
173 V1 = add_node(G, a, b); | |
174 V2 = add_node(G, a, c); | |
175 | |
176 elseif nargin == 3 | |
177 V1 = a; | |
178 V2 = b; | |
179 end | |
180 | |
181 weight = edge@DiGraph(G, V1, V2); | |
182 end | |
183 | |
184 function [weight, varargout] = edges(G,a,b) | |
185 | |
186 % all edges or from specified node ? | |
187 if nargin >= 2 | |
188 | |
189 % is there a clip pair or node number input? | |
190 if nargin == 3 | |
191 V1 = add_node(G, a, b); | |
192 | |
193 elseif nargin == 2 | |
194 V1 = a; | |
195 end | |
196 | |
197 [weight, V1, V2] = edges@DiGraph(G, V1); | |
198 | |
199 else | |
200 % --- | |
201 % ok, get ALL edges | |
202 % --- | |
203 [weight, V1, V2] = edges@DiGraph(G); | |
204 end | |
205 | |
206 % how to represent the output | |
207 if nargout <= 3 | |
208 varargout{1} = V1; | |
209 varargout{2} = V2; | |
210 else | |
211 % --- | |
212 % get all the clips from the edges | |
213 % --- | |
214 ao = zeros(1,numel(V1)); | |
215 bo = zeros(1,numel(V1)); | |
216 co = zeros(1,numel(V1)); | |
217 for i =1:numel(V1) | |
218 [ao(i), bo(i), co(i)] = G.clipsE(V1(i), V2(i)); | |
219 end | |
220 varargout{1} = ao; | |
221 varargout{2} = bo; | |
222 varargout{3} = co; | |
223 end | |
224 end | |
225 | |
226 % --- | |
227 % add an edge saying sim(a,b) > sim(a,c) | |
228 % --- | |
229 function add_edge(G, a, b, c, weight) | |
230 | |
231 if nargin == 5 | |
232 V1 = add_node(G, a, b); | |
233 V2 = add_node(G, a, c); | |
234 | |
235 elseif nargin == 4 | |
236 V1 = a; | |
237 V2 = b; | |
238 weight = c; | |
239 end | |
240 | |
241 % --- | |
242 % call superclass | |
243 % --- | |
244 add_edge@DiGraph(G, V1, V2, weight); | |
245 | |
246 end | |
247 | |
248 function Vid = add_node(G, a, b) | |
249 | |
250 if nargin == 3 | |
251 Vid = G.node(a,b); | |
252 else | |
253 Vid = a; | |
254 end | |
255 | |
256 % --- | |
257 % call superclass | |
258 % --- | |
259 add_node@DiGraph(G, Vid); | |
260 end | |
261 | |
262 % --- | |
263 % the pairgraph variant of add_graph also updates the | |
264 % clip id hashmap | |
265 % ---- | |
266 function add_graph(G, G2) | |
267 | |
268 % determine if symmetric edges have to be added | |
269 clas = cat(1, class(G2), superclasses(G2)); | |
270 if strcellfind(clas, 'Graph') | |
271 add_symm = 1; | |
272 else | |
273 add_symm = 0; | |
274 end | |
275 | |
276 % --- | |
277 % add all nodes and edges in G2 | |
278 % --- | |
279 for V = G2.nodes(); | |
280 | |
281 [a, count] = sscanf(G2.label(V),'%u:%u'); | |
282 | |
283 if count == 2 | |
284 b = a(2); | |
285 a = a(1); | |
286 | |
287 G.add_node(a,b); | |
288 else | |
289 G.add_node(V); | |
290 end | |
291 end | |
292 | |
293 % --- | |
294 % NOTE / TODO: | |
295 % this LABEL inheritance is far too expensive when | |
296 % creating many copiesof the same graph | |
297 % Its also unnessecary for lots of them | |
298 % except for debugging :(. | |
299 % --- | |
300 G.Vlbl = cell(1, numel(G2.V)); | |
301 if G2.cardinality > 1 | |
302 G.Vlbl(G.nodes()) = G2.label(G2.nodes()); | |
303 else | |
304 G.Vlbl(G.nodes()) = {G2.label(G2.nodes())}; | |
305 end | |
306 | |
307 % --- | |
308 % get all edges in G2 | |
309 % CAVE: if we added the edges above using | |
310 % label clip indices, we have to address them | |
311 % using these below! | |
312 % --- | |
313 [val, V1, V2] = edges(G2); | |
314 | |
315 for i = 1:numel(val) | |
316 | |
317 % --- | |
318 % add edges to graph | |
319 % NOTE: we assume either all or no edges | |
320 % are labeled with clip indices | |
321 % --- | |
322 if count == 2 | |
323 % --- | |
324 % ok, they were labeled above, | |
325 % so index by clips. | |
326 % | |
327 % TODO: | |
328 % 1. get rid of this sscanf stuff and use add_edge for | |
329 % creating the nodes first, the only add single nodes | |
330 % 2. use cell labels globally instead of hashmap here | |
331 | |
332 [u, count] = sscanf(G2.label(V1(i)),'%u:%u'); | |
333 [v, count] = sscanf(G2.label(V2(i)),'%u:%u'); | |
334 | |
335 a = intersect(u,v); | |
336 b = setdiff(u,a); | |
337 c = setdiff(v,a); | |
338 | |
339 G.add_edge(a, b, c, val(i)); | |
340 | |
341 if add_symm | |
342 % --- | |
343 % add symmetric edges to graph | |
344 % --- | |
345 G.add_edge(a, c, b, val(i)); | |
346 end | |
347 | |
348 else | |
349 G.add_edge(V1(i), V2(i), val(i)); | |
350 | |
351 if add_symm | |
352 % --- | |
353 % add symmetric edges to graph | |
354 % --- | |
355 G.add_edge(V2(i), V1(i), val(i)); | |
356 end | |
357 | |
358 end | |
359 | |
360 | |
361 end | |
362 | |
363 end | |
364 | |
365 function remove_node(G, a, b) | |
366 | |
367 if nargin == 3 | |
368 Vid = G.node(a,b); | |
369 else | |
370 Vid = a; | |
371 end | |
372 | |
373 % --- | |
374 % call superclass | |
375 % --- | |
376 remove_node@DiGraph(G, Vid); | |
377 end | |
378 | |
379 % --- | |
380 % Clip ids for Edge | |
381 % --- | |
382 function [a,b,c] = clipsE(G, V1, V2) | |
383 | |
384 [c1, c2] = clipsN(G, V1); | |
385 [c3, c4] = clipsN(G, V2); | |
386 | |
387 % common clip | |
388 a = intersect([c1 c2],[c3 c4]); | |
389 | |
390 % nearer (similar) clip | |
391 b = setdiff([c1 c2],a); | |
392 | |
393 % far clip | |
394 c = setdiff([c3 c4],a); | |
395 | |
396 if isempty(a) | |
397 error 'clip similarity graph inconsistent' | |
398 end | |
399 end | |
400 | |
401 % --- | |
402 function out = label(G, Vid) | |
403 | |
404 if nargin == 1 | |
405 out = cell(numel(G.V), 1); | |
406 Vid = 1:numel(G.V); | |
407 end | |
408 | |
409 for i = 1:numel(Vid) | |
410 if (numel(G.Vlbl) < Vid(i)) || isempty(G.Vlbl{Vid(i)}) | |
411 | |
412 [sm, bg] = G.clipsN(Vid(i)); | |
413 | |
414 if numel(Vid) > 1 | |
415 out{i} = sprintf('%d:%d', sm, bg); | |
416 else | |
417 out = sprintf('%d:%d', sm, bg); | |
418 end | |
419 else | |
420 if numel(Vid) > 1 | |
421 out{i} = G.Vlbl{Vid(i)}; | |
422 else | |
423 out = G.Vlbl{Vid(i)}; | |
424 end | |
425 end | |
426 end | |
427 end | |
428 | |
429 % --- | |
430 % determines if Edges in G2 are the same as in G | |
431 % --- | |
432 function out = le(a,b) | |
433 out = isSubgraph(a, b); | |
434 end | |
435 | |
436 function [out] = isSubgraph(G, G2) | |
437 | |
438 [val, V1, V2] = G2.edges(); | |
439 | |
440 i = 1; | |
441 while i <= numel(V1) | |
442 % --- | |
443 % Test if edge exists in other graph, | |
444 % using clips as identifier | |
445 % --- | |
446 [a,b,c] = G2.clipsE(V1(i), V2(i)); | |
447 | |
448 if G.edge(a,b,c) ~= val(i) | |
449 out = 0; | |
450 return, | |
451 end | |
452 i = i + 1; | |
453 end | |
454 out = 1; | |
455 end | |
456 | |
457 | |
458 function [Gout] = minus(a, b) | |
459 Gout = feval(class(a),a); | |
460 Gout.remove_graph(b); | |
461 end | |
462 | |
463 function remove_graph(G, G2) | |
464 | |
465 % --- | |
466 % Get Edges in G2 and remove them | |
467 % --- | |
468 [~, V1, V2] = G2.edges(); | |
469 for i = 1:numel(V1) | |
470 % --- | |
471 % Test if edge exists in other graph, | |
472 % using clips as identifier | |
473 % --- | |
474 [a,b,c] = G2.clipsE(V1(i), V2(i)); | |
475 | |
476 G.remove_edge(a,b,c); | |
477 end | |
478 | |
479 % --- | |
480 % Note : we only remove nodes with no | |
481 % remaining incoming edges | |
482 % --- | |
483 V = G2.nodes(); | |
484 for i = 1:numel(V) | |
485 | |
486 % --- | |
487 % get corresponding node in G via clips | |
488 % --- | |
489 [a,b] = G2.clipsN(V(i)); | |
490 | |
491 Vid = node(G, a, b); | |
492 if G.degree(Vid) == 0 | |
493 | |
494 G.remove_node(Vid); | |
495 end | |
496 end | |
497 end | |
498 end | |
499 end |