Loopy Решетки Redux

Пройдя через решетку с титаном

С помощью Titan / Gremlin можно рассчитать количество путей длиной 1, 2, 3,…, 40 в  20x20решетке. Обход длины 40 — это полный обход решетки от верхнего левого угла до нижнего правого. Код обхода и время выполнения приведены ниже. Потенцируя  выполнения реализуются: 10,9 минут (28 шагов), 2,3 часа (29 шагов), и 9,8 часа (30 шагов) обходы. Расчет был остановлен на 31-м шаге. Число путей длиной 40 не может быть разумно рассчитано с помощью Titan / Gremlin. Путем исчерпывающего перечисления путей и с ростом числа путей в геометрической прогрессии по мере увеличения длины пути вычисление этой формы обречено на большие значения  n.

/usr/local/titan-all-0.3.1$ bin/gremlin.sh
 
         \,,,/
         (o o)
-----oOOo-(_)-oOOo-----
gremlin> g = generateLattice(20)
==>titangraph[cassandrathrift:127.0.0.1]
gremlin> g.V.count()
==>441
gremlin> g.E.count()
==>840
gremlin> (1..40).each{ l ->
  t = System.currentTimeMillis();
  c = g.v(4).out.loop(1){it.loops <= l}.count()
  t = System.currentTimeMillis() - t;
  println(l + ":" + c + ":" + t)
}

Пройдя через решетку с Фавном

Faunus  — это движок графической аналитики, использующий  Hadoop  и  широкую  реализацию Gremlin . С помощью Faunus пути можно перечислять аналогично Titan / Gremlin, но если требуются только подсчеты (места назначения или пути), то более эффективно распространять и суммировать счетчики. Вместо того, чтобы явно хранить каждый Гремлин в каждой вершине, Фаунус хранит  количество  Гремлинов в каждой вершине. В этом разница между представлением  списка  длины  m и  длинной  со значением  m. Следствием этой модели является то, что можно эффективно вычислить количество путей длиной 40 в 20x20 решетка с Фавном. Этот механизм встречного распространения аналогичен механическому способу вычисления  биномиальных коэффициентов, предложенному  Блезом Паскалем  через  треугольник Паскаля  (в западном мире). Важно отметить, что это вычисление требует первого шага.

g = FaunusFactory.open('bin/titan-cassandra-input.properties')
t = System.currentTimeMillis()
// As of Faunus 0.3.1, the loop() construct is not supported
g.v(4).out.out.out.out.count() // 4-steps
t = System.currentTimeMillis() - t