大数据图：循环点阵
本文的内容最初由Marko Rodriguez和Bobby Norton在Aurelius博客上共同撰写。
点阵是一个有特定且明确结构的图。N×N点阵是一个在X和Y轴都有N条边的二维网格，比如上面的图像就是两个20x20的点阵。请注意，两幅图像是“相同的”20x20点阵——无论网格是否“折叠”，两个图形都是同构的（即元素能够彼此一一对应）。因此，对于点阵来说重要的不是它在二维平面上呈现的方式，而是它的元素之间是如何连接的。使用R语言，我们有如下一些针对名为g的点阵基本的描述性统计计算。
~$ r
R version 2.13.1 (2011-07-08)
Copyright (C) 2011 The R Foundation for Statistical Computing
...
> length(V(g))
[1] 441
> length(E(g))
[1] 840
> hist(degree(g), breaks=c(0,2,3,4), freq=TRUE, xlab='vertex degree', ylab='frequency', cex.lab=1.25, main='', col=c('gray10','gray40','gray70'), labels=TRUE, axes=FALSE, cex=2)
20x20点阵的度数可以通过分析确定。首先必须存在4个角顶点，每个角顶点的度数都为2；然后在每边有19个度数为三的顶点，假设有4条边，则有76个这样的点（19 x 4 = 76）；最后，在点阵的内部正方形中存在19行每行19列个度数为4的顶点，总共有361个（19×19 = 361）。上面的直方图绘制了20x20点阵的度数分布 ，证实了上述推导：20x20点阵有441个顶点和840条边。通常，nxn的点阵中的顶点数为（n + 1）（n + 1），边数为2（（n^2）+ n）。
遍历一个有向点阵
假设有一个有向点阵，其中所有的边都指向正下和正右的顶点。在这样的结构中，左上角顶点只有出度。同样，右下角顶点只有入度。可以用如下的形式提出一个关于点阵的有趣的问题：
“存在多少条不同的路径能够从左上角开始走到右下角？”
对于1x1点阵，有两条不同的路径。
0→1→3
0→2→3
如上图所示，可以通过单纯地从左上角到右下角走两次来手动枚举这些路径而不会有重复。但是当点阵变得太大而不能有效地作图并手动枚举时，就可以通过数学技术来确定路径的数量。使用Blueprints的TinkerGraph方法来构造一个点阵并通过Gremlin方法来遍历它。为了对任意大小的点阵（任意的n）进行此操作，函数被定义为generateLattice（int n）。
def generateLattice(n) {
g = new TinkerGraph()
// 顶点总数
max = Math.pow((n+1),2)
// 生成顶点
(1..max).each { g.addVertex() }
// 生成边
g.V.each {
id = Integer.parseInt(it.id)
right = id + 1
if (((right % (n + 1)) > 0) && (right <= max)) {
g.addEdge(it, g.v(right), '')
}
down = id + n + 1
if (down < max) {
g.addEdge(it, g.v(down), '')
}
}
return g
}“从上到下”的路径有一个有趣的属性，就是它们长度总是相同。对于先前绘制的1x1点阵，该长度为2。因此，可以在两步之后到达右下角的顶点。一般来说，一个n×n点阵所需的步数是2n。
gremlin> g = generateLattice(1)
==>tinkergraph[vertices:4 edges:4]
gremlin> g.v(0).out.out.path
==>[v[0], v[2], v[3]]
==>[v[0], v[1], v[3]]
gremlin> g.v(0).out.loop(1){it.loops <= 2}.path
==>[v[0], v[2], v[3]]
==>[v[0], v[1], v[3]]
一个2x2点阵足够小，其路径也可以如上图展示的那样枚举。它有6条不同的路径，这可以在Gremlin中验证。
gremlin> g = generateLattice(2)
==>tinkergraph[vertices:9 edges:12]
gremlin> g.v(0).out.loop(1){it.loops <= 4}.count()
==>6
gremlin> g.v(0).out.loop(1){it.loops <= 4}.path
==>[v[0], v[3], v[6], v[7], v[8]]
==>[v[0], v[3], v[4], v[7], v[8]]
==>[v[0], v[3], v[4], v[5], v[8]]
==>[v[0], v[1], v[4], v[7], v[8]]
==>[v[0], v[1], v[4], v[5], v[8]]
==>[v[0], v[1], v[2], v[5], v[8]]
如果1x1点阵有2条路径，2×2点阵有6条路径，那么3×3点阵有多少条路径？更一般地，一个nxn点阵有多少条路径？理论上，Gremlin可以遍历和计数这些路径。但是，这种方法有限制。例如，尝试使用Gremlin的遍历方法来确定1000x1000点阵中的所有不同的路径，缺点很快就会暴露出来，Gremlin 将需要和宇宙的年龄一样长的时间来实现。下面的代码演示了Gremlin对直到尺寸为10x10的点阵的路径数量的计算。
gremlin> (1..10).collect{ n ->
gremlin> g = generateLattice(n)
gremlin> g.v(0).out.loop(1){it.loops <= (2*n)}.count()
gremlin> }
==>2
==>6
==>20
==>70
==>252
==>924
==>3432
==>12870
==>48620
==>184756闭式算法和分析的力量
为了知道任意nxn点阵的路径数量，必须导出一个闭式表达式。确定闭式方程的一种方法是在Google上搜索序列。返回的第一个网站是整数序列在线百科全书。Gremlin发现的序列称为A000984，在页面上有以下注释：
“从（0,0）到（n，n）的通过（1,0）和（0,1）的点阵路径的数量。Joerg Arndt，2011年7月1日“
在同一页面还说明了一般形式是“2n和n的组合数”，这可以展开成它的阶乘表示（例如5！= 5 * 4 * 3 * 2 * 1），如下图所示。
这种闭式方法不需要遍历显式的图形结构。相反，对于任何n都可以来计算它的组合数。20x20的有向点阵拥有超过1370亿个不同的路径！对于Gremlin来说，在合理的时间内枚举这些路径太勉强了。
> n = 20
> factorial(2 * n) / factorial(n)^2
[1] 137846528820可能会提出一个问题：“为什么C（n,2n）能够表示nxn点阵的不同的路径的数量？”当计算从顶点（0,0）到（n，n）的路径数量时，只有向下和向右两个方向允许移动，因此必须有n个下移，n个右移。这意味着总共有2n个移动，因此有n个选择（因为另外n个“选择”是由前面n个选择所确定的）。因此，移动的总数是“C（n,2n）”。在另一个似乎不相关的问题（由相同的网页提供）中也发现这个相同的整数序列。
“一个2 * n位二进制数的可能值的数量，其中一半的位是0，另一半是1。 - 加文斯科特，2003年8月9日“
每一条路径都是包含n个D和n个R的字母序列，其中向下两次然后向右两次将是DDRR。这将“点阵问题”映射到“长度为2n问题的二进制串”问题。两个问题实质上一种行为的两个不同的表示。
绘制函数的增长图像
可以在从1到20来绘制组合数的函数图像（下面的左图）。值得注意的是，当图像的y轴被设置为对数刻度时，该图像是一条直线（右下图）。这意味着当点阵的大小增长为线性时，有向点阵中的路径数目是呈指数增长的。
> factorial(2 * seq(1,n)) / factorial(seq(1,n))^2
[1] 2 6 20 70 252 924
[7] 3432 12870 48620 184756 705432 2704156
[13] 10400600 40116600 155117520 601080390 2333606220 9075135300
[19] 35345263800 137846528820
> x <- factorial(2 * seq(1,n)) / factorial(seq(1,n))^2
> plot(x, xlab='lattice size (n x n)', ylab='total number of paths', cex.lab=1.4, cex.axis=1.6, lwd=1.5, cex=1.5, type='b')
> plot(x, xlab='lattice size (n x n)', ylab="total number of paths", cex.lab=1.4, cex.axis=1.6, lwd=1.5, cex=1.5, type='b' log='y')
结论
一个20x20点阵（仅有441个顶点和840个边界）却有超过1370亿个从左上到右下的不同的有向路径听起来有点疯狂。但正是这个数据让它变成了这样一个循环点阵！任何跟图打交道的人都应该留意。图结构不像它简化的对应物（例如列表，地图和树）。图的连通性模式使它可以产生组合爆炸。处理图形时，理解这种行为很重要。因为很容易就遇到这种需要耗尽宇宙的时间来求解的方案。
致谢
Vadas Gintautas博士开展了这项探索。Vadas发表了关于生物网络，信息理论，计算机视觉和非线性动力学等各种问题的具有高影响力期刊文章。他拥有博士学位。来自伊利诺伊大学厄巴纳香槟分校的物理学专业。