Анализ и понимание этого алгоритма

Мне нужно реализовать найденный алгоритм here (стр. 5), используя данные от here (выберите данные в facebook, размер будет только KB, если вы хотите углубиться). Алгоритм:Анализ и понимание этого алгоритма

1: Ti ← 0 //Ti is pi’s count of triangles 
2: for v ∈ Vi do 
3: for u ∈ Nv do 
4:  if u ∈ Vi then 
5:  S ← Nv ∩ Nu 
6:  Ti ← Ti + |S| 
7:  else if u ∈ Vj then 
8:  Send <data,Nv> to pj if not sent already 
9: 
10: Check for incoming messages <t,X>: 
11: if t = data then 
12: Ti ← Ti+ SURROGATECOUNT(X, i) 
13: else 
14: Increment completion counter 
15: 
16: Broadcast <notifier,X> 
17: while completion counter < P-1 do 
18: Check for incoming messages <t,X>: 
19: if t = data then 
20:  Ti ← Ti+ SURROGATECOUNT(X, i) 
21: else 
22:  Increment completion counter 
23: 
24: MPIBARRIER 
25: Find Sum T ← Pi Ti using MPIREDUCE 
26: return T

Насколько я понимаю, мне нужен двухмерный массив. Мне нужно запросить каждый элемент внутри оператора if и сделать +1 в переменной Ti.

Первый вопрос, S ← Nv ∩ Nu с чем назначать эту переменную S?
Wikipedia говорит: A ∩ B means the set that contains all those elements that A and B have in common.

Второй вопрос, если вы посмотрите на данные, мне нужны все они? Мне кажется, мне нужен только файл .edges.

источник

2016-02-10 Ctrlfreak

Этот n-образный символ является пересечением, и большинство языков программирования имеют класс Set/object, который обеспечивает эту операцию. –

@ cricket_007. Я не знаком с этим классом, который вы могли бы предоставить и примером? – Ctrlfreak

['java.util.Set'] (http://docs.oracle.com/javase/7/docs/api/java/util/Set.html) и python [' set() '] (https://docs.python.org/2/tutorial/datastructures.html#sets) –

S ← Nv ∩ Nu 
Ti ← Ti + |S|

Похоже, вам нужно только количество элементов, которые находятся в обоих Nv и Nu. Поэтому просто подсчитайте их на Ti. Алгоритм, похоже, не использует набор S для чего-либо еще.

Не похоже, что вам нужна большая информация о соединениях, поэтому просто может быть достаточно.

источник

2016-02-10 13:52:35 Sorin

Итак, если 'Vi' является первым colum, а' Nv' является вторым в массиве, и мне нужно проверить, есть ли число 'Nv' также можно найти внутри 'Vi', что я делаю, например, что: http://imgur.com/qj2SDWH номер 3998, который подсвечен, находится в обеих сторонах. Добавляю ли я 1 для этого в 'Ti'? – Ctrlfreak

Я не уверен, что вы принесете «Vi» здесь. Вам нужны 'Nv' и' Nu'. Но если это столбцы, то да, вам нужно добавить один для 3998 и, возможно, больше, если есть другие числа, которые отображаются с обеих сторон. – Sorin

Спасибо, я начну кодирование и вернусь с большим количеством вопросов! : D – Ctrlfreak

Анализ и понимание этого алгоритма

ответ

Смежные вопросы