Loopy Lattices Redux
Loopy Lattices Redux
Join the DZone community and get the full member experience.
Join For FreeDatabases are better when they can run themselves. CockroachDB is a SQL database that automates scaling and recovery. Check it out here.
A graph can be realized as a tessellated surface. Each vertex (or point) on the surface has a set of neighbors. Two vertices are neighbors if there is an edge that connects them. For a discrete traverser (e.g. a marble), movement in a space requires a decision at each vertex. The traverser must decide whether to go left, up, east, right, west, or down — i.e., it must choose one and only one edge emanating from its current vertex. The edge chosen leads to yet another vertex. At which point, another choice must be made ad infinitum.
kRegular Graphs: kAry String Generators
A directed graph is k
regular if each vertex has k
adjacent vertices. Starting from any vertex, there are k^{n}
possible n
length paths in a k
regular graph. For a 2regular graph (k=2
), the number of unique paths is equivalent to the number of objects that can be represented by abinary string. For instance, there are 4,294,967,296 length 32 paths in a 2regular graph (2^{32}
). This relationship is apparent if every vertex’s incident edges are labeled with either a 0 or 1. If the traversers print the edge label at each step in an n
step walk, then all possiblen
length binary strings will be generated.
A graph with 2degree vertices is rare in nature. A graph with 10+ degree vertices is more common, though such k
regularity is uncommon. A 10regular graph has 100,000,000,000,000,000,000,000,000,000,000 unique 32length paths (10^{32}
).Combinatorial explosions are readily apparent whencomputing on natural graphs. Such truths effect the way in which technology/algorithms should be implemented when solving realworld graph problems.
Lattice Graphs: Binary Strings with an Equal Number of 0s and 1s
A lattice is a planar graph with a rectangular tessellation. The “inside” of a finite lattice is regular in that each vertex connects to the same number of vertices, but the “outside” is not regular in that there are no neighbors beyond the border vertices. A 20x20
directed lattice has 441 vertices and 840 edges. As shown analytically in the original Loopy Latticespost, there are 137,846,528,820 (137.85 billion) unique paths from the topleft vertex to the bottomright vertex. A discrete traverser must take 40 steps to make the journey. Of those 40 steps, an equal number of 1s and 0s will be “printed.” Thus, the problem of determining how many unique paths there are in a directed 20x20
lattice is a question of how many unique 40length binary strings exist such that there is an equal number of 1s and 0s. This constraint yields a number that is much smaller than k^{n}
. In the previous post, Gremlin (in its depthfirst, enumerative form) could not calculate the answer due to the explosion of possibilities. Therefore, to answer the question, the closed form solution below was provided. The solution says “2n choose n” or, in particular, “40 choose 20.” The 20 chosen 1 slots in the 40length binary string forces the remaining 20 positions to be 0.
Titan vs. Faunus: The Enumerative/Counting Distinction
A graph database such as Titan can be used to store a 20x20
lattice. While a 840 edge graph is extremely small for a “database,” it is necessary for the experiment to follow. The Gremlin/Groovy code to create a 20x20
lattice in Titan is provided below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def
generateLattice(n) {
g = TitanFactory.open(
'bin/cassandra.local'
)
// total number of vertices
max
= Math.pow((n+
1
),
2
)
// generate the vertices
vertices = [];
(
1
..
max
).
each
{ vertices.add(g.addVertex()) }
// generate the edges
vertices.
eachWithIndex
{ v, i >
right = i +
1
if
(((right % (n +
1
)) >
0
) && (right <=
max
)) {
v.addEdge(
'link'
, vertices[right])
}
down = i + n +
1
if
(down <
max
) {
v.addEdge(
'link'
, vertices[down])
}
}
g.commit();
return
g
}

Traversing a Lattice with Titan
With Titan/Gremlin, it is possible to count the number of 1, 2, 3, …, 40length paths in the 20x20
lattice. A traversal of length 40 is a full traversal of the lattice from the topleft to the bottomright. The traversal code and the runtimes are provide below. An exponentiating runtime is realized: 10.9 minutes (28 steps), 2.3 hours (29 steps), and 9.8 hours (30 steps) traversals. The calculation was halted on the 31st step. The number of 40length paths could not be reasonably calculated with Titan/Gremlin. By exhaustively enumerating paths and with the number of paths growing exponentially as the path length increases, a calculation of this form is doomed for large values of n
.
/usr/local/titanall0.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) }
path length  path count  traversal time (ms)  path length  path count  traversal time (ms) 

1  2  9  2  4  2 
3  8  1  4  16  2 
5  32  3  6  64  5 
7  128  10  8  256  17 
9  512  36  10  1024  62 
11  2048  74  12  4096  96 
13  8192  49  14  16384  61 
15  32768  88  16  65536  163 
17  131072  325  18  262144  646 
19  524288  1296  20  1048576  2573 
21  2097150  5172  22  4194258  10306 
23  8388054  20659  24  16772566  41555 
25  33523880  82993  26  66941500  166828 
27  133422540  331954  28  265069020  654070 
29  523921830  8288566  30  1027813650  35512124 
…  …  …  …  …  … 
Traversing a Lattice with Faunus
Faunus is a graph analytics engine that leverages Hadoop and a breadthfirst implementation ofGremlin. With Faunus, paths can be enumerated in a similar fashion to Titan/Gremlin, but if only counts are required (destinations vs. paths), then it is more efficient to propagate and sum counters.Instead of explicitly storing each and every Gremlin at every vertex, Faunus stores the number of Gremlins at each vertex. This is the difference between representing a list of length m
and a long with value m
. A consequence of this model is that it is possible to efficiently compute the number of 40length paths in a 20x20
lattice with Faunus. This counter propagation mechanism is analogous to the mechanical technique for computing binomial coefficientsas proposed by Blaise Pascal via Pascal’s triangle (in the Western world). It is important to note the breadthfirst requirement of this computation.
g = FaunusFactory.open('bin/titancassandrainput.properties') t = System.currentTimeMillis() // As of Faunus 0.3.1, the loop() construct is not supported g.v(4).out.out.out.out.count() // 4steps t = System.currentTimeMillis()  t
The number of paths of length n
in a 20x20
lattice is plotted below in both y
linear (left) and y
logarithmic (right) form. In short, the number of paths grows exponentially as the path length increases. What is interesting to note in the following table of Faunus counts and runtimes is that Faunus is able to compute the total number of unique 40length paths in the lattice in 10.53 minutes — 137,846,528,820.
path length  path count  traversal time (ms)  path length  path count  traversal time (ms) 

1  2  32781  2  4  48071 
3  8  63537  4  16  78575 
5  32  94078  6  64  109246 
7  128  124574  8  256  139850 
9  512  156223  10  1024  171549 
11  2048  186049  12  4096  201111 
13  8192  218417  14  16384  232642 
15  32768  248019  16  65536  263355 
17  131072  278685  18  262144  296912 
19  524288  308225  20  1048576  324440 
21  2097150  340823  22  4194258  355349 
23  8388054  371546  24  16772566  385755 
25  33523880  402189  26  66941500  416868 
27  133422540  433917  28  265069020  448150 
29  523921830  462522  30  1027813650  478595 
31  1995537270  493224  32  3821729910  508492 
33  7191874140  524791  34  13237415400  539216 
35  23690879520  556108  36  40885872720  568512 
37  67156001220  586697  38  102501265020  601196 
39  137846528820  617152 
Titan’s runtime grows exponentially, in proportion to the number of paths computed. On the other hand, Faunus’ computation time grows linearly when computing an exponential path count. At step 28, Faunus executes the path count faster than Titan. This does not mean that Titan is inherently less efficient at such computations, it is simply a function of the depthfirst, enumerative nature of Gremlin/Titan vs. the breadthfirst, counter nature of Gremlin/Faunus. Implementing Faunus’ Gremlin engine over Titan would enable Titan to compute such path counts effectively. However, the purpose of Faunus is to serve as the global batch processer to Titan.
Conclusion
A graph is a data structure composed of vertices and edges. The natural interpretation of a computation on a graph is a traversal — i.e., a directed walk over the vertices by means of chosen incident edges. An exhaustive exploration of all paths within a graph is typically not feasible because the number of paths grows exponentially as a function of the path length and the graph’s branch factor. As demonstrated with Titan and Faunus, the goal of the traversal and the choice of the traversal engine ultimately determines the feasibility of the computation. Once again, the loopy lattice exposes a simple truth in the theory and practice of graphs.
Databases should be easy to deploy, easy to use, and easy to scale. If you agree, you should check out CockroachDB, a scalable SQL database built for businesses of every size. Check it out here.
Published at DZone with permission of Marko Rodriguez , DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
{{ parent.title  parent.header.title}}
{{ parent.tldr }}
{{ parent.linkDescription }}
{{ parent.urlSource.name }}