site/docs/0.9.2/graphx-programming-guide.html


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226

<!DOCTYPE html>
<!--[if lt IE 7]>      <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
<!--[if IE 7]>         <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
<!--[if IE 8]>         <html class="no-js lt-ie9"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]-->
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
        <title>GraphX Programming Guide - Spark 0.9.2 Documentation</title>
        <meta name="description" content="">

        <link rel="stylesheet" href="css/bootstrap.min.css">
        <style>
            body {
                padding-top: 60px;
                padding-bottom: 40px;
            }
        </style>
        <meta name="viewport" content="width=device-width">
        <link rel="stylesheet" href="css/bootstrap-responsive.min.css">
        <link rel="stylesheet" href="css/main.css">

        <script src="js/vendor/modernizr-2.6.1-respond-1.1.0.min.js"></script>

        <link rel="stylesheet" href="css/pygments-default.css">

        
        <!-- Google analytics script -->
        <script type="text/javascript">
          var _gaq = _gaq || [];
          _gaq.push(['_setAccount', 'UA-32518208-1']);
          _gaq.push(['_trackPageview']);

          (function() {
            var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
            ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
            var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
          })();
        </script>
        

    </head>
    <body>
        <!--[if lt IE 7]>
            <p class="chromeframe">You are using an outdated browser. <a href="http://browsehappy.com/">Upgrade your browser today</a> or <a href="http://www.google.com/chromeframe/?redirect=true">install Google Chrome Frame</a> to better experience this site.</p>
        <![endif]-->

        <!-- This code is taken from http://twitter.github.com/bootstrap/examples/hero.html -->

        <div class="navbar navbar-fixed-top" id="topbar">
            <div class="navbar-inner">
                <div class="container">
                    <div class="brand"><a href="index.html">
                      <img src="img/spark-logo-hd.png" style="height:50px;"/></a><span class="version">0.9.2</span>
                    </div>
                    <ul class="nav">
                        <!--TODO(andyk): Add class="active" attribute to li some how.-->
                        <li><a href="index.html">Overview</a></li>

                        <li class="dropdown">
                            <a href="#" class="dropdown-toggle" data-toggle="dropdown">Programming Guides<b class="caret"></b></a>
                            <ul class="dropdown-menu">
                                <li><a href="quick-start.html">Quick Start</a></li>
                                <li><a href="scala-programming-guide.html">Spark in Scala</a></li>
                                <li><a href="java-programming-guide.html">Spark in Java</a></li>
                                <li><a href="python-programming-guide.html">Spark in Python</a></li>
                                <li class="divider"></li>
                                <li><a href="streaming-programming-guide.html">Spark Streaming</a></li>
                                <li><a href="mllib-guide.html">MLlib (Machine Learning)</a></li>
                                <li><a href="bagel-programming-guide.html">Bagel (Pregel on Spark)</a></li>
                                <li><a href="graphx-programming-guide.html">GraphX (Graph Processing)</a></li>
                            </ul>
                        </li>

                        <li class="dropdown">
                            <a href="#" class="dropdown-toggle" data-toggle="dropdown">API Docs<b class="caret"></b></a>
                            <ul class="dropdown-menu">
                                <li><a href="api/core/index.html#org.apache.spark.package">Spark Core for Java/Scala</a></li>
                                <li><a href="api/pyspark/index.html">Spark Core for Python</a></li>
                                <li class="divider"></li>
                                <li><a href="api/streaming/index.html#org.apache.spark.streaming.package">Spark Streaming</a></li>
                                <li><a href="api/mllib/index.html#org.apache.spark.mllib.package">MLlib (Machine Learning)</a></li>
                                <li><a href="api/bagel/index.html#org.apache.spark.bagel.package">Bagel (Pregel on Spark)</a></li>
                                <li><a href="api/graphx/index.html#org.apache.spark.graphx.package">GraphX (Graph Processing)</a></li>
                                <li class="divider"></li>
                                <li class="dropdown-submenu">
                                    <a tabindex="-1" href="#">External Data Sources</a>
                                    <ul class="dropdown-menu">
                                        <li><a href="api/external/kafka/index.html#org.apache.spark.streaming.kafka.KafkaUtils$">Kafka</a></li>
                                        <li><a href="api/external/flume/index.html#org.apache.spark.streaming.flume.FlumeUtils$">Flume</a></li>
                                        <li><a href="api/external/twitter/index.html#org.apache.spark.streaming.twitter.TwitterUtils$">Twitter</a></li>
                                        <li><a href="api/external/zeromq/index.html#org.apache.spark.streaming.zeromq.ZeroMQUtils$">ZeroMQ</a></li>
                                        <li><a href="api/external/mqtt/index.html#org.apache.spark.streaming.mqtt.MQTTUtils$">MQTT</a></li>
                                    </ul>
                                </li>
                            </ul>
                        </li>

                        <li class="dropdown">
                            <a href="#" class="dropdown-toggle" data-toggle="dropdown">Deploying<b class="caret"></b></a>
                            <ul class="dropdown-menu">
                                <li><a href="cluster-overview.html">Overview</a></li>
                                <li><a href="ec2-scripts.html">Amazon EC2</a></li>
                                <li><a href="spark-standalone.html">Standalone Mode</a></li>
                                <li><a href="running-on-mesos.html">Mesos</a></li>
                                <li><a href="running-on-yarn.html">YARN</a></li>
                            </ul>
                        </li>

                        <li class="dropdown">
                            <a href="api.html" class="dropdown-toggle" data-toggle="dropdown">More<b class="caret"></b></a>
                            <ul class="dropdown-menu">
                                <li><a href="configuration.html">Configuration</a></li>
                                <li><a href="monitoring.html">Monitoring</a></li>
                                <li><a href="tuning.html">Tuning Guide</a></li>
                                <li><a href="hadoop-third-party-distributions.html">Running with CDH/HDP</a></li>
                                <li><a href="hardware-provisioning.html">Hardware Provisioning</a></li>
                                <li><a href="job-scheduling.html">Job Scheduling</a></li>
                                <li class="divider"></li>
                                <li><a href="building-with-maven.html">Building Spark with Maven</a></li>
                                <li><a href="https://cwiki.apache.org/confluence/display/SPARK/Contributing+to+Spark">Contributing to Spark</a></li>
                            </ul>
                        </li>
                    </ul>
                    <!--<p class="navbar-text pull-right"><span class="version-text">v0.9.2</span></p>-->
                </div>
            </div>
        </div>

        <div class="container" id="content">
          <h1 class="title">GraphX Programming Guide</h1>

          <ul id="markdown-toc">
  <li><a href="#overview">Overview</a>    <ul>
      <li><a href="#background-on-graph-parallel-computation">Background on Graph-Parallel Computation</a></li>
      <li><a href="#graphx-replaces-the-spark-bagel-api">GraphX Replaces the Spark Bagel API</a></li>
    </ul>
  </li>
  <li><a href="#getting-started">Getting Started</a></li>
  <li><a href="#the-property-graph">The Property Graph</a>    <ul>
      <li><a href="#example-property-graph">Example Property Graph</a></li>
    </ul>
  </li>
  <li><a href="#graph-operators">Graph Operators</a>    <ul>
      <li><a href="#summary-list-of-operators">Summary List of Operators</a></li>
      <li><a href="#property-operators">Property Operators</a></li>
      <li><a href="#structural-operators">Structural Operators</a></li>
      <li><a href="#join-operators">Join Operators</a></li>
      <li><a href="#neighborhood-aggregation">Neighborhood Aggregation</a>        <ul>
          <li><a href="#map-reduce-triplets-mapreducetriplets">Map Reduce Triplets (mapReduceTriplets)</a></li>
          <li><a href="#computing-degree-information">Computing Degree Information</a></li>
          <li><a href="#collecting-neighbors">Collecting Neighbors</a></li>
        </ul>
      </li>
      <li><a href="#caching-and-uncaching">Caching and Uncaching</a></li>
    </ul>
  </li>
  <li><a href="#pregel-api">Pregel API</a></li>
  <li><a href="#graph-builders">Graph Builders</a></li>
  <li><a href="#vertex-and-edge-rdds">Vertex and Edge RDDs</a>    <ul>
      <li><a href="#vertexrdds">VertexRDDs</a></li>
      <li><a href="#edgerdds">EdgeRDDs</a></li>
    </ul>
  </li>
  <li><a href="#optimized-representation">Optimized Representation</a></li>
  <li><a href="#graph-algorithms">Graph Algorithms</a>    <ul>
      <li><a href="#pagerank">PageRank</a></li>
      <li><a href="#connected-components">Connected Components</a></li>
      <li><a href="#triangle-counting">Triangle Counting</a></li>
    </ul>
  </li>
  <li><a href="#examples">Examples</a></li>
</ul>

<p style="text-align: center;">
  <img src="img/graphx_logo.png" title="GraphX Logo" alt="GraphX" width="65%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<h1 id="overview">Overview</h1>

<p>GraphX is the new (alpha) Spark API for graphs and graph-parallel computation. At a high-level,
GraphX extends the Spark <a href="api/core/index.html#org.apache.spark.rdd.RDD">RDD</a> by introducing the
<a href="#property_graph">Resilient Distributed Property Graph</a>: a directed multigraph with properties
attached to each vertex and edge.  To support graph computation, GraphX exposes a set of fundamental
operators (e.g., <a href="#structural_operators">subgraph</a>, <a href="#join_operators">joinVertices</a>, and
<a href="#mrTriplets">mapReduceTriplets</a>) as well as an optimized variant of the <a href="#pregel">Pregel</a> API. In
addition, GraphX includes a growing collection of graph <a href="#graph_algorithms">algorithms</a> and
<a href="#graph_builders">builders</a> to simplify graph analytics tasks.</p>

<h2 id="background-on-graph-parallel-computation">Background on Graph-Parallel Computation</h2>

<p>From social networks to language modeling, the growing scale and importance of
graph data has driven the development of numerous new <em>graph-parallel</em> systems
(e.g., <a href="http://giraph.apache.org">Giraph</a> and
<a href="http://graphlab.org">GraphLab</a>).  By restricting the types of computation that can be
expressed and introducing new techniques to partition and distribute graphs,
these systems can efficiently execute sophisticated graph algorithms orders of
magnitude faster than more general <em>data-parallel</em> systems.</p>

<p style="text-align: center;">
  <img src="img/data_parallel_vs_graph_parallel.png" title="Data-Parallel vs. Graph-Parallel" alt="Data-Parallel vs. Graph-Parallel" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>However, the same restrictions that enable these substantial performance gains also make it
difficult to express many of the important stages in a typical graph-analytics pipeline:
constructing the graph, modifying its structure, or expressing computation that spans multiple
graphs.  Furthermore, how we look at data depends on our objectives and the same raw data may have
many different table and graph views.</p>

<p style="text-align: center;">
  <img src="img/tables_and_graphs.png" title="Tables and Graphs" alt="Tables and Graphs" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>As a consequence, it is often necessary to be able to move between table and graph views of the same
physical data and to leverage the properties of each view to easily and efficiently express
computation.  However, existing graph analytics pipelines must compose graph-parallel and data-
parallel systems, leading to extensive data movement and duplication and a complicated programming
model.</p>

<p style="text-align: center;">
  <img src="img/graph_analytics_pipeline.png" title="Graph Analytics Pipeline" alt="Graph Analytics Pipeline" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>The goal of the GraphX project is to unify graph-parallel and data-parallel computation in one
system with a single composable API. The GraphX API enables users to view data both as a graph and
as collections (i.e., RDDs) without data movement or duplication. By incorporating recent advances
in graph-parallel systems, GraphX is able to optimize the execution of graph operations.</p>

<h2 id="graphx-replaces-the-spark-bagel-api">GraphX Replaces the Spark Bagel API</h2>

<p>Prior to the release of GraphX, graph computation in Spark was expressed using Bagel, an
implementation of Pregel.  GraphX improves upon Bagel by exposing a richer property graph API, a
more streamlined version of the Pregel abstraction, and system optimizations to improve performance
and reduce memory overhead.  While we plan to eventually deprecate Bagel, we will continue to
support the <a href="api/bagel/index.html#org.apache.spark.bagel.package">Bagel API</a> and
<a href="bagel-programming-guide.html">Bagel programming guide</a>. However, we encourage Bagel users to
explore the new GraphX API and comment on issues that may complicate the transition from Bagel.</p>

<h1 id="getting-started">Getting Started</h1>

<p>To get started you first need to import Spark and GraphX into your project, as follows:</p>

<div class="highlight"><pre><code class="scala"><span class="k">import</span> <span class="nn">org.apache.spark._</span>
<span class="k">import</span> <span class="nn">org.apache.spark.graphx._</span>
<span class="c1">// To make some of the examples work we will also need RDD</span>
<span class="k">import</span> <span class="nn">org.apache.spark.rdd.RDD</span>
</code></pre></div>

<p>If you are not using the Spark shell you will also need a <code>SparkContext</code>.  To learn more about
getting started with Spark refer to the <a href="quick-start.html">Spark Quick Start Guide</a>.</p>

<h1 id="the-property-graph">The Property Graph</h1>
<p><a name="property_graph"></a></p>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.Graph">property graph</a> is a directed multigraph
with user defined objects attached to each vertex and edge.  A directed multigraph is a directed
graph with potentially multiple parallel edges sharing the same source and destination vertex.  The
ability to support parallel edges simplifies modeling scenarios where there can be multiple
relationships (e.g., co-worker and friend) between the same vertices.  Each vertex is keyed by a
<em>unique</em> 64-bit long identifier (<code>VertexID</code>).  GraphX does not impose any ordering constraints on
the vertex identifiers.  Similarly, edges have corresponding source and destination vertex
identifiers.</p>

<p>The property graph is parameterized over the vertex (<code>VD</code>) and edge (<code>ED</code>) types.  These
are the types of the objects associated with each vertex and edge respectively.</p>

<blockquote>
  <p>GraphX optimizes the representation of vertex and edge types when they are plain old data-types
(e.g., int, double, etc&#8230;) reducing the in memory footprint by storing them in specialized
arrays.</p>
</blockquote>

<p>In some cases it may be desirable to have vertices with different property types in the same graph.
This can be accomplished through inheritance.  For example to model users and products as a
bipartite graph we might do the following:</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">VertexProperty</span><span class="o">()</span>
<span class="k">case</span> <span class="k">class</span> <span class="nc">UserProperty</span><span class="o">(</span><span class="k">val</span> <span class="n">name</span><span class="k">:</span> <span class="kt">String</span><span class="o">)</span> <span class="k">extends</span> <span class="nc">VertexProperty</span>
<span class="k">case</span> <span class="k">class</span> <span class="nc">ProductProperty</span><span class="o">(</span><span class="k">val</span> <span class="n">name</span><span class="k">:</span> <span class="kt">String</span><span class="o">,</span> <span class="k">val</span> <span class="n">price</span><span class="k">:</span> <span class="kt">Double</span><span class="o">)</span> <span class="k">extends</span> <span class="nc">VertexProperty</span>
<span class="c1">// The graph might then have the type:</span>
<span class="k">var</span> <span class="n">graph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VertexProperty</span>, <span class="kt">String</span><span class="o">]</span> <span class="k">=</span> <span class="kc">null</span>
</code></pre></div>

<p>Like RDDs, property graphs are immutable, distributed, and fault-tolerant.  Changes to the values or
structure of the graph are accomplished by producing a new graph with the desired changes.  Note
that substantial parts of the original graph (i.e., unaffected structure, attributes, and indicies)
are reused in the new graph reducing the cost of this inherently functional data-structure.  The
graph is partitioned across the workers using a range of vertex-partitioning heuristics.  As with
RDDs, each partition of the graph can be recreated on a different machine in the event of a failure.</p>

<p>Logically the property graph corresponds to a pair of typed collections (RDDs) encoding the
properties for each vertex and edge.  As a consequence, the graph class contains members to access
the vertices and edges of the graph:</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">val</span> <span class="n">vertices</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD</span><span class="o">]</span>
  <span class="k">val</span> <span class="n">edges</span><span class="k">:</span> <span class="kt">EdgeRDD</span><span class="o">[</span><span class="kt">ED</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p>The classes <code>VertexRDD[VD]</code> and <code>EdgeRDD[ED]</code> extend and are optimized versions of <code>RDD[(VertexID,
VD)]</code> and <code>RDD[Edge[ED]]</code> respectively.  Both <code>VertexRDD[VD]</code> and <code>EdgeRDD[ED]</code> provide  additional
functionality built around graph computation and leverage internal optimizations.  We discuss the
<code>VertexRDD</code> and <code>EdgeRDD</code> API in greater detail in the section on <a href="#vertex_and_edge_rdds">vertex and edge
RDDs</a> but for now they can be thought of as simply RDDs of the form:
<code>RDD[(VertexID, VD)]</code> and <code>RDD[Edge[ED]]</code>.</p>

<h3 id="example-property-graph">Example Property Graph</h3>

<p>Suppose we want to construct a property graph consisting of the various collaborators on the GraphX
project. The vertex property might contain the username and occupation.  We could annotate edges
with a string describing the relationships between collaborators:</p>

<p style="text-align: center;">
  <img src="img/property_graph.png" title="The Property Graph" alt="The Property Graph" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>The resulting graph would have the type signature:</p>

<div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">userGraph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[(</span><span class="kt">String</span>, <span class="kt">String</span><span class="o">)</span>, <span class="kt">String</span><span class="o">]</span>
</code></pre></div>

<p>There are numerous ways to construct a property graph from raw files, RDDs, and even synthetic
generators and these are discussed in more detail in the section on
<a href="#graph_builders">graph builders</a>.  Probably the most general method is to use the
<a href="api/graphx/index.html#org.apache.spark.graphx.Graph$">Graph object</a>.  For example the following
code constructs a graph from a collection of RDDs:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Assume the SparkContext has already been constructed</span>
<span class="k">val</span> <span class="n">sc</span><span class="k">:</span> <span class="kt">SparkContext</span>
<span class="c1">// Create an RDD for the vertices</span>
<span class="k">val</span> <span class="n">users</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="o">(</span><span class="kt">String</span>, <span class="kt">String</span><span class="o">))]</span> <span class="k">=</span>
  <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="nc">Array</span><span class="o">((</span><span class="mi">3L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;rxin&quot;</span><span class="o">,</span> <span class="s">&quot;student&quot;</span><span class="o">)),</span> <span class="o">(</span><span class="mi">7L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;jgonzal&quot;</span><span class="o">,</span> <span class="s">&quot;postdoc&quot;</span><span class="o">)),</span>
                       <span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;franklin&quot;</span><span class="o">,</span> <span class="s">&quot;prof&quot;</span><span class="o">)),</span> <span class="o">(</span><span class="mi">2L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;istoica&quot;</span><span class="o">,</span> <span class="s">&quot;prof&quot;</span><span class="o">))))</span>
<span class="c1">// Create an RDD for edges</span>
<span class="k">val</span> <span class="n">relationships</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">Edge</span><span class="o">[</span><span class="kt">String</span><span class="o">]]</span> <span class="k">=</span>
  <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="nc">Edge</span><span class="o">(</span><span class="mi">3L</span><span class="o">,</span> <span class="mi">7L</span><span class="o">,</span> <span class="s">&quot;collab&quot;</span><span class="o">),</span>    <span class="nc">Edge</span><span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="mi">3L</span><span class="o">,</span> <span class="s">&quot;advisor&quot;</span><span class="o">),</span>
                       <span class="nc">Edge</span><span class="o">(</span><span class="mi">2L</span><span class="o">,</span> <span class="mi">5L</span><span class="o">,</span> <span class="s">&quot;colleague&quot;</span><span class="o">),</span> <span class="nc">Edge</span><span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="mi">7L</span><span class="o">,</span> <span class="s">&quot;pi&quot;</span><span class="o">)))</span>
<span class="c1">// Define a default user in case there are relationship with missing user</span>
<span class="k">val</span> <span class="n">defaultUser</span> <span class="k">=</span> <span class="o">(</span><span class="s">&quot;John Doe&quot;</span><span class="o">,</span> <span class="s">&quot;Missing&quot;</span><span class="o">)</span>
<span class="c1">// Build the initial Graph</span>
<span class="k">val</span> <span class="n">graph</span> <span class="k">=</span> <span class="nc">Graph</span><span class="o">(</span><span class="n">users</span><span class="o">,</span> <span class="n">relationships</span><span class="o">,</span> <span class="n">defaultUser</span><span class="o">)</span>
</code></pre></div>

<p>In the above example we make use of the <a href="api/graphx/index.html#org.apache.spark.graphx.Edge"><code>Edge</code></a> case class. Edges have a <code>srcId</code> and a
<code>dstId</code> corresponding to the source and destination vertex identifiers. In addition, the <code>Edge</code>
class has an <code>attr</code> member which stores the edge property.</p>

<p>We can deconstruct a graph into the respective vertex and edge views by using the <code>graph.vertices</code>
and <code>graph.edges</code> members respectively.</p>

<div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">graph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[(</span><span class="kt">String</span>, <span class="kt">String</span><span class="o">)</span>, <span class="kt">String</span><span class="o">]</span> <span class="c1">// Constructed from above</span>
<span class="c1">// Count all users which are postdocs</span>
<span class="n">graph</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">filter</span> <span class="o">{</span> <span class="k">case</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">pos</span><span class="o">))</span> <span class="k">=&gt;</span> <span class="n">pos</span> <span class="o">==</span> <span class="s">&quot;postdoc&quot;</span> <span class="o">}.</span><span class="n">count</span>
<span class="c1">// Count all the edges where src &gt; dst</span>
<span class="n">graph</span><span class="o">.</span><span class="n">edges</span><span class="o">.</span><span class="n">filter</span><span class="o">(</span><span class="n">e</span> <span class="k">=&gt;</span> <span class="n">e</span><span class="o">.</span><span class="n">srcId</span> <span class="o">&gt;</span> <span class="n">e</span><span class="o">.</span><span class="n">dstId</span><span class="o">).</span><span class="n">count</span>
</code></pre></div>

<blockquote>
  <p>Note that <code>graph.vertices</code> returns an <code>VertexRDD[(String, String)]</code> which extends
<code>RDD[(VertexID, (String, String))]</code> and so we use the scala <code>case</code> expression to deconstruct the
tuple.  On the other hand, <code>graph.edges</code> returns an <code>EdgeRDD</code> containing <code>Edge[String]</code> objects.
We could have also used the case class type constructor as in the following:</p>

  <div class="highlight"><pre><code class="scala"><span class="n">graph</span><span class="o">.</span><span class="n">edges</span><span class="o">.</span><span class="n">filter</span> <span class="o">{</span> <span class="k">case</span> <span class="nc">Edge</span><span class="o">(</span><span class="n">src</span><span class="o">,</span> <span class="n">dst</span><span class="o">,</span> <span class="n">prop</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">src</span> <span class="o">&gt;</span> <span class="n">dst</span> <span class="o">}.</span><span class="n">count</span>
</code></pre></div>
</blockquote>

<p>In addition to the vertex and edge views of the property graph, GraphX also exposes a triplet view.
The triplet view logically joins the vertex and edge properties yielding an
<code>RDD[EdgeTriplet[VD, ED]]</code> containing instances of the <a href="api/graphx/index.html#org.apache.spark.graphx.EdgeTriplet"><code>EdgeTriplet</code></a> class. This
<em>join</em> can be expressed in the following SQL expression:</p>

<div class="highlight"><pre><code class="sql"><span class="k">SELECT</span> <span class="n">src</span><span class="p">.</span><span class="n">id</span><span class="p">,</span> <span class="n">dst</span><span class="p">.</span><span class="n">id</span><span class="p">,</span> <span class="n">src</span><span class="p">.</span><span class="n">attr</span><span class="p">,</span> <span class="n">e</span><span class="p">.</span><span class="n">attr</span><span class="p">,</span> <span class="n">dst</span><span class="p">.</span><span class="n">attr</span>
<span class="k">FROM</span> <span class="n">edges</span> <span class="k">AS</span> <span class="n">e</span> <span class="k">LEFT</span> <span class="k">JOIN</span> <span class="n">vertices</span> <span class="k">AS</span> <span class="n">src</span><span class="p">,</span> <span class="n">vertices</span> <span class="k">AS</span> <span class="n">dst</span>
<span class="k">ON</span> <span class="n">e</span><span class="p">.</span><span class="n">srcId</span> <span class="o">=</span> <span class="n">src</span><span class="p">.</span><span class="n">Id</span> <span class="k">AND</span> <span class="n">e</span><span class="p">.</span><span class="n">dstId</span> <span class="o">=</span> <span class="n">dst</span><span class="p">.</span><span class="n">Id</span>
</code></pre></div>

<p>or graphically as:</p>

<p style="text-align: center;">
  <img src="img/triplet.png" title="Edge Triplet" alt="Edge Triplet" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.EdgeTriplet"><code>EdgeTriplet</code></a> class extends the <a href="api/graphx/index.html#org.apache.spark.graphx.Edge"><code>Edge</code></a> class by adding the <code>srcAttr</code> and
<code>dstAttr</code> members which contain the source and destination properties respectively. We can use the
triplet view of a graph to render a collection of strings describing relationships between users.</p>

<div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">graph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[(</span><span class="kt">String</span>, <span class="kt">String</span><span class="o">)</span>, <span class="kt">String</span><span class="o">]</span> <span class="c1">// Constructed from above</span>
<span class="c1">// Use the triplets view to create an RDD of facts.</span>
<span class="k">val</span> <span class="n">facts</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">String</span><span class="o">]</span> <span class="k">=</span>
  <span class="n">graph</span><span class="o">.</span><span class="n">triplets</span><span class="o">.</span><span class="n">map</span><span class="o">(</span><span class="n">triplet</span> <span class="k">=&gt;</span>
    <span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span><span class="o">.</span><span class="n">_1</span> <span class="o">+</span> <span class="s">&quot; is the &quot;</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">attr</span> <span class="o">+</span> <span class="s">&quot; of &quot;</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">dstAttr</span><span class="o">.</span><span class="n">_1</span><span class="o">)</span>
<span class="n">facts</span><span class="o">.</span><span class="n">collect</span><span class="o">.</span><span class="n">foreach</span><span class="o">(</span><span class="n">println</span><span class="o">(</span><span class="k">_</span><span class="o">))</span>
</code></pre></div>

<h1 id="graph-operators">Graph Operators</h1>

<p>Just as RDDs have basic operations like <code>map</code>, <code>filter</code>, and <code>reduceByKey</code>, property graphs also
have a collection of basic operators that take user defined functions and produce new graphs with
transformed properties and structure.  The core operators that have optimized implementations are
defined in <a href="api/graphx/index.html#org.apache.spark.graphx.Graph"><code>Graph</code></a> and convenient operators that are expressed as a compositions of the
core operators are defined in <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a>.  However, thanks to Scala implicits the
operators in <code>GraphOps</code> are automatically available as members of <code>Graph</code>.  For example, we can
compute the in-degree of each vertex (defined in <code>GraphOps</code>) by the following:</p>

<div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">graph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[(</span><span class="kt">String</span>, <span class="kt">String</span><span class="o">)</span>, <span class="kt">String</span><span class="o">]</span>
<span class="c1">// Use the implicit GraphOps.inDegrees operator</span>
<span class="k">val</span> <span class="n">inDegrees</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">inDegrees</span>
</code></pre></div>

<p>The reason for differentiating between core graph operations and <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a> is to be
able to support different graph representations in the future.  Each graph representation must
provide implementations of the core operations and reuse many of the useful operations defined in
<a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a>.</p>

<h3 id="summary-list-of-operators">Summary List of Operators</h3>
<p>The following is a quick summary of the functionality defined in both <a href="api/graphx/index.html#org.apache.spark.graphx.Graph"><code>Graph</code></a> and
<a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a> but presented as members of Graph for simplicity. Note that some function
signatures have been simplified (e.g., default arguments and type constraints removed) and some more
advanced functionality has been removed so please consult the API docs for the official list of
operations.</p>

<div class="highlight"><pre><code class="scala"><span class="cm">/** Summary of the functionality in the property graph */</span>
<span class="k">class</span> <span class="nc">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="c1">// Information about the Graph ===================================================================</span>
  <span class="k">val</span> <span class="n">numEdges</span><span class="k">:</span> <span class="kt">Long</span>
  <span class="k">val</span> <span class="n">numVertices</span><span class="k">:</span> <span class="kt">Long</span>
  <span class="k">val</span> <span class="n">inDegrees</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span>
  <span class="k">val</span> <span class="n">outDegrees</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span>
  <span class="k">val</span> <span class="n">degrees</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span>
  <span class="c1">// Views of the graph as collections =============================================================</span>
  <span class="k">val</span> <span class="n">vertices</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD</span><span class="o">]</span>
  <span class="k">val</span> <span class="n">edges</span><span class="k">:</span> <span class="kt">EdgeRDD</span><span class="o">[</span><span class="kt">ED</span><span class="o">]</span>
  <span class="k">val</span> <span class="n">triplets</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]]</span>
  <span class="c1">// Functions for caching graphs ==================================================================</span>
  <span class="k">def</span> <span class="n">persist</span><span class="o">(</span><span class="n">newLevel</span><span class="k">:</span> <span class="kt">StorageLevel</span> <span class="o">=</span> <span class="nc">StorageLevel</span><span class="o">.</span><span class="nc">MEMORY_ONLY</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">cache</span><span class="o">()</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">unpersistVertices</span><span class="o">(</span><span class="n">blocking</span><span class="k">:</span> <span class="kt">Boolean</span> <span class="o">=</span> <span class="kc">true</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="c1">// Change the partitioning heuristic  ============================================================</span>
  <span class="k">def</span> <span class="n">partitionBy</span><span class="o">(</span><span class="n">partitionStrategy</span><span class="k">:</span> <span class="kt">PartitionStrategy</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="c1">// Transform vertex and edge attributes ==========================================================</span>
  <span class="k">def</span> <span class="n">mapVertices</span><span class="o">[</span><span class="kt">VD2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexID</span><span class="o">,</span> <span class="kt">VD</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapEdges</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="kt">Edge</span><span class="o">[</span><span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">ED2</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED2</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapEdges</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">PartitionID</span><span class="o">,</span> <span class="kt">Iterator</span><span class="o">[</span><span class="kt">Edge</span><span class="o">[</span><span class="kt">ED</span><span class="o">]])</span> <span class="k">=&gt;</span> <span class="nc">Iterator</span><span class="o">[</span><span class="kt">ED2</span><span class="o">])</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED2</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapTriplets</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">ED2</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED2</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapTriplets</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">PartitionID</span><span class="o">,</span> <span class="kt">Iterator</span><span class="o">[</span><span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]])</span> <span class="k">=&gt;</span> <span class="nc">Iterator</span><span class="o">[</span><span class="kt">ED2</span><span class="o">])</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED2</span><span class="o">]</span>
  <span class="c1">// Modify the graph structure ====================================================================</span>
  <span class="k">def</span> <span class="n">reverse</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">subgraph</span><span class="o">(</span>
      <span class="n">epred</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>,<span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Boolean</span> <span class="k">=</span> <span class="o">(</span><span class="n">x</span> <span class="k">=&gt;</span> <span class="kc">true</span><span class="o">),</span>
      <span class="n">vpred</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexID</span><span class="o">,</span> <span class="kt">VD</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">Boolean</span> <span class="k">=</span> <span class="o">((</span><span class="n">v</span><span class="o">,</span> <span class="n">d</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="kc">true</span><span class="o">))</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mask</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED2</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED2</span><span class="o">])</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">groupEdges</span><span class="o">(</span><span class="n">merge</span><span class="k">:</span> <span class="o">(</span><span class="kt">ED</span><span class="o">,</span> <span class="kt">ED</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">ED</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="c1">// Join RDDs with the graph ======================================================================</span>
  <span class="k">def</span> <span class="n">joinVertices</span><span class="o">[</span><span class="kt">U</span><span class="o">](</span><span class="n">table</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexID</span>, <span class="kt">U</span><span class="o">)])(</span><span class="n">mapFunc</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexID</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="n">U</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">outerJoinVertices</span><span class="o">[</span><span class="kt">U</span>, <span class="kt">VD2</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexID</span>, <span class="kt">U</span><span class="o">)])</span>
      <span class="o">(</span><span class="n">mapFunc</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexID</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="nc">Option</span><span class="o">[</span><span class="kt">U</span><span class="o">])</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="c1">// Aggregate information about adjacent triplets =================================================</span>
  <span class="k">def</span> <span class="n">collectNeighborIds</span><span class="o">(</span><span class="n">edgeDirection</span><span class="k">:</span> <span class="kt">EdgeDirection</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Array</span><span class="o">[</span><span class="kt">VertexID</span><span class="o">]]</span>
  <span class="k">def</span> <span class="n">collectNeighbors</span><span class="o">(</span><span class="n">edgeDirection</span><span class="k">:</span> <span class="kt">EdgeDirection</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Array</span><span class="o">[(</span><span class="kt">VertexID</span>, <span class="kt">VD</span><span class="o">)]]</span>
  <span class="k">def</span> <span class="n">mapReduceTriplets</span><span class="o">[</span><span class="kt">A:</span> <span class="kt">ClassTag</span><span class="o">](</span>
      <span class="n">mapFunc</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Iterator</span><span class="o">[(</span><span class="kt">VertexID</span>, <span class="kt">A</span><span class="o">)],</span>
      <span class="n">reduceFunc</span><span class="k">:</span> <span class="o">(</span><span class="kt">A</span><span class="o">,</span> <span class="kt">A</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">A</span><span class="o">,</span>
      <span class="n">activeSetOpt</span><span class="k">:</span> <span class="kt">Option</span><span class="o">[(</span><span class="kt">VertexRDD</span><span class="o">[</span><span class="k">_</span><span class="o">]</span>, <span class="kt">EdgeDirection</span><span class="o">)]</span> <span class="k">=</span> <span class="nc">None</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">A</span><span class="o">]</span>
  <span class="c1">// Iterative graph-parallel computation ==========================================================</span>
  <span class="k">def</span> <span class="n">pregel</span><span class="o">[</span><span class="kt">A</span><span class="o">](</span><span class="n">initialMsg</span><span class="k">:</span> <span class="kt">A</span><span class="o">,</span> <span class="n">maxIterations</span><span class="k">:</span> <span class="kt">Int</span><span class="o">,</span> <span class="n">activeDirection</span><span class="k">:</span> <span class="kt">EdgeDirection</span><span class="o">)(</span>
      <span class="n">vprog</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexID</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="n">A</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD</span><span class="o">,</span>
      <span class="n">sendMsg</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Iterator</span><span class="o">[(</span><span class="kt">VertexID</span>,<span class="kt">A</span><span class="o">)],</span>
      <span class="n">mergeMsg</span><span class="k">:</span> <span class="o">(</span><span class="kt">A</span><span class="o">,</span> <span class="kt">A</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">A</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="c1">// Basic graph algorithms ========================================================================</span>
  <span class="k">def</span> <span class="n">pageRank</span><span class="o">(</span><span class="n">tol</span><span class="k">:</span> <span class="kt">Double</span><span class="o">,</span> <span class="n">resetProb</span><span class="k">:</span> <span class="kt">Double</span> <span class="o">=</span> <span class="mf">0.15</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Double</span>, <span class="kt">Double</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">connectedComponents</span><span class="o">()</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VertexID</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">triangleCount</span><span class="o">()</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Int</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">stronglyConnectedComponents</span><span class="o">(</span><span class="n">numIter</span><span class="k">:</span> <span class="kt">Int</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VertexID</span>, <span class="kt">ED</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<h2 id="property-operators">Property Operators</h2>

<p>In direct analogy to the RDD <code>map</code> operator, the property
graph contains the following:</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">mapVertices</span><span class="o">[</span><span class="kt">VD2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapEdges</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="kt">Edge</span><span class="o">[</span><span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">ED2</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED2</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapTriplets</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">ED2</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED2</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p>Each of these operators yields a new graph with the vertex or edge properties modified by the user
defined <code>map</code> function.</p>

<blockquote>
  <p>Note that in all cases the graph structure is unaffected. This is a key feature of these operators
which allows the resulting graph to reuse the structural indices of the original graph. The
following snippets are logically equivalent, but the first one does not preserve the structural
indices and would not benefit from the GraphX system optimizations:</p>

  <div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">newVertices</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">map</span> <span class="o">{</span> <span class="k">case</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">attr</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">mapUdf</span><span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">attr</span><span class="o">))</span> <span class="o">}</span>
<span class="k">val</span> <span class="n">newGraph</span> <span class="k">=</span> <span class="nc">Graph</span><span class="o">(</span><span class="n">newVertices</span><span class="o">,</span> <span class="n">graph</span><span class="o">.</span><span class="n">edges</span><span class="o">)</span>
</code></pre></div>
</blockquote>

<blockquote>
  <p>Instead, use <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@mapVertices[VD2]((VertexId,VD)⇒VD2)(ClassTag[VD2]):Graph[VD2,ED]"><code>mapVertices</code></a> to preserve the indices:</p>

  <div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">newGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">mapVertices</span><span class="o">((</span><span class="n">id</span><span class="o">,</span> <span class="n">attr</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">mapUdf</span><span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">attr</span><span class="o">))</span>
</code></pre></div>
</blockquote>

<p>These operators are often used to initialize the graph for a particular computation or project away
unnecessary properties.  For example, given a graph with the out-degrees as the vertex properties
(we describe how to construct such a graph later), we initialize it for PageRank:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Given a graph where the vertex property is the out-degree</span>
<span class="k">val</span> <span class="n">inputGraph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Int</span>, <span class="kt">String</span><span class="o">]</span> <span class="k">=</span>
  <span class="n">graph</span><span class="o">.</span><span class="n">outerJoinVertices</span><span class="o">(</span><span class="n">graph</span><span class="o">.</span><span class="n">outDegrees</span><span class="o">)((</span><span class="n">vid</span><span class="o">,</span> <span class="k">_</span><span class="o">,</span> <span class="n">degOpt</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">degOpt</span><span class="o">.</span><span class="n">getOrElse</span><span class="o">(</span><span class="mi">0</span><span class="o">))</span>
<span class="c1">// Construct a graph where each edge contains the weight</span>
<span class="c1">// and each vertex is the initial PageRank</span>
<span class="k">val</span> <span class="n">outputGraph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Double</span>, <span class="kt">Double</span><span class="o">]</span> <span class="k">=</span>
  <span class="n">inputGraph</span><span class="o">.</span><span class="n">mapTriplets</span><span class="o">(</span><span class="n">triplet</span> <span class="k">=&gt;</span> <span class="mf">1.0</span> <span class="o">/</span> <span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span><span class="o">).</span><span class="n">mapVertices</span><span class="o">((</span><span class="n">id</span><span class="o">,</span> <span class="k">_</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="mf">1.0</span><span class="o">)</span>
</code></pre></div>

<h2 id="structural-operators">Structural Operators</h2>
<p><a name="structural_operators"></a></p>

<p>Currently GraphX supports only a simple set of commonly used structural operators and we expect to
add more in the future.  The following is a list of the basic structural operators.</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">reverse</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">subgraph</span><span class="o">(</span><span class="n">epred</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>,<span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Boolean</span><span class="o">,</span>
               <span class="n">vpred</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">Boolean</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mask</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED2</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED2</span><span class="o">])</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">groupEdges</span><span class="o">(</span><span class="n">merge</span><span class="k">:</span> <span class="o">(</span><span class="kt">ED</span><span class="o">,</span> <span class="kt">ED</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">ED</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>,<span class="kt">ED</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@reverse:Graph[VD,ED]"><code>reverse</code></a> operator returns a new graph with all the edge directions reversed.
This can be useful when, for example, trying to compute the inverse PageRank.  Because the reverse
operation does not modify vertex or edge properties or change the number of edges, it can be
implemented efficiently without data-movement or duplication.</p>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@subgraph((EdgeTriplet[VD,ED])⇒Boolean,(VertexId,VD)⇒Boolean):Graph[VD,ED]"><code>subgraph</code></a> operator takes vertex and edge predicates and returns the graph
containing only the vertices that satisfy the vertex predicate (evaluate to true) and edges that
satisfy the edge predicate <em>and connect vertices that satisfy the vertex predicate</em>.  The <code>subgraph</code>
operator can be used in number of situations to restrict the graph to the vertices and edges of
interest or eliminate broken links. For example in the following code we remove broken links:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Create an RDD for the vertices</span>
<span class="k">val</span> <span class="n">users</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="o">(</span><span class="kt">String</span>, <span class="kt">String</span><span class="o">))]</span> <span class="k">=</span>
  <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="nc">Array</span><span class="o">((</span><span class="mi">3L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;rxin&quot;</span><span class="o">,</span> <span class="s">&quot;student&quot;</span><span class="o">)),</span> <span class="o">(</span><span class="mi">7L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;jgonzal&quot;</span><span class="o">,</span> <span class="s">&quot;postdoc&quot;</span><span class="o">)),</span>
                       <span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;franklin&quot;</span><span class="o">,</span> <span class="s">&quot;prof&quot;</span><span class="o">)),</span> <span class="o">(</span><span class="mi">2L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;istoica&quot;</span><span class="o">,</span> <span class="s">&quot;prof&quot;</span><span class="o">)),</span>
                       <span class="o">(</span><span class="mi">4L</span><span class="o">,</span> <span class="o">(</span><span class="s">&quot;peter&quot;</span><span class="o">,</span> <span class="s">&quot;student&quot;</span><span class="o">))))</span>
<span class="c1">// Create an RDD for edges</span>
<span class="k">val</span> <span class="n">relationships</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">Edge</span><span class="o">[</span><span class="kt">String</span><span class="o">]]</span> <span class="k">=</span>
  <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="nc">Edge</span><span class="o">(</span><span class="mi">3L</span><span class="o">,</span> <span class="mi">7L</span><span class="o">,</span> <span class="s">&quot;collab&quot;</span><span class="o">),</span>    <span class="nc">Edge</span><span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="mi">3L</span><span class="o">,</span> <span class="s">&quot;advisor&quot;</span><span class="o">),</span>
                       <span class="nc">Edge</span><span class="o">(</span><span class="mi">2L</span><span class="o">,</span> <span class="mi">5L</span><span class="o">,</span> <span class="s">&quot;colleague&quot;</span><span class="o">),</span> <span class="nc">Edge</span><span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="mi">7L</span><span class="o">,</span> <span class="s">&quot;pi&quot;</span><span class="o">),</span>
                       <span class="nc">Edge</span><span class="o">(</span><span class="mi">4L</span><span class="o">,</span> <span class="mi">0L</span><span class="o">,</span> <span class="s">&quot;student&quot;</span><span class="o">),</span>   <span class="nc">Edge</span><span class="o">(</span><span class="mi">5L</span><span class="o">,</span> <span class="mi">0L</span><span class="o">,</span> <span class="s">&quot;colleague&quot;</span><span class="o">)))</span>
<span class="c1">// Define a default user in case there are relationship with missing user</span>
<span class="k">val</span> <span class="n">defaultUser</span> <span class="k">=</span> <span class="o">(</span><span class="s">&quot;John Doe&quot;</span><span class="o">,</span> <span class="s">&quot;Missing&quot;</span><span class="o">)</span>
<span class="c1">// Build the initial Graph</span>
<span class="k">val</span> <span class="n">graph</span> <span class="k">=</span> <span class="nc">Graph</span><span class="o">(</span><span class="n">users</span><span class="o">,</span> <span class="n">relationships</span><span class="o">,</span> <span class="n">defaultUser</span><span class="o">)</span>
<span class="c1">// Notice that there is a user 0 (for which we have no information) connected to users</span>
<span class="c1">// 4 (peter) and 5 (franklin).</span>
<span class="n">graph</span><span class="o">.</span><span class="n">triplets</span><span class="o">.</span><span class="n">map</span><span class="o">(</span>
    <span class="n">triplet</span> <span class="k">=&gt;</span> <span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span><span class="o">.</span><span class="n">_1</span> <span class="o">+</span> <span class="s">&quot; is the &quot;</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">attr</span> <span class="o">+</span> <span class="s">&quot; of &quot;</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">dstAttr</span><span class="o">.</span><span class="n">_1</span>
  <span class="o">).</span><span class="n">collect</span><span class="o">.</span><span class="n">foreach</span><span class="o">(</span><span class="n">println</span><span class="o">(</span><span class="k">_</span><span class="o">))</span>
<span class="c1">// Remove missing vertices as well as the edges to connected to them</span>
<span class="k">val</span> <span class="n">validGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">subgraph</span><span class="o">(</span><span class="n">vpred</span> <span class="k">=</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">attr</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">attr</span><span class="o">.</span><span class="n">_2</span> <span class="o">!=</span> <span class="s">&quot;Missing&quot;</span><span class="o">)</span>
<span class="c1">// The valid subgraph will disconnect users 4 and 5 by removing user 0</span>
<span class="n">validGraph</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">collect</span><span class="o">.</span><span class="n">foreach</span><span class="o">(</span><span class="n">println</span><span class="o">(</span><span class="k">_</span><span class="o">))</span>
<span class="n">validGraph</span><span class="o">.</span><span class="n">triplets</span><span class="o">.</span><span class="n">map</span><span class="o">(</span>
    <span class="n">triplet</span> <span class="k">=&gt;</span> <span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span><span class="o">.</span><span class="n">_1</span> <span class="o">+</span> <span class="s">&quot; is the &quot;</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">attr</span> <span class="o">+</span> <span class="s">&quot; of &quot;</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">dstAttr</span><span class="o">.</span><span class="n">_1</span>
  <span class="o">).</span><span class="n">collect</span><span class="o">.</span><span class="n">foreach</span><span class="o">(</span><span class="n">println</span><span class="o">(</span><span class="k">_</span><span class="o">))</span>
</code></pre></div>

<blockquote>
  <p>Note in the above example only the vertex predicate is provided.  The <code>subgraph</code> operator defaults
to <code>true</code> if the vertex or edge predicates are not provided.</p>
</blockquote>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@mask[VD2,ED2](Graph[VD2,ED2])(ClassTag[VD2],ClassTag[ED2]):Graph[VD,ED]"><code>mask</code></a> operator also constructs a subgraph by returning a graph that contains the
vertices and edges that are also found in the input graph.  This can be used in conjunction with the
<code>subgraph</code> operator to restrict a graph based on the properties in another related graph.  For
example, we might run connected components using the graph with missing vertices and then restrict
the answer to the valid subgraph.</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Run Connected Components</span>
<span class="k">val</span> <span class="n">ccGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">connectedComponents</span><span class="o">()</span> <span class="c1">// No longer contains missing field</span>
<span class="c1">// Remove missing vertices as well as the edges to connected to them</span>
<span class="k">val</span> <span class="n">validGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">subgraph</span><span class="o">(</span><span class="n">vpred</span> <span class="k">=</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">attr</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">attr</span><span class="o">.</span><span class="n">_2</span> <span class="o">!=</span> <span class="s">&quot;Missing&quot;</span><span class="o">)</span>
<span class="c1">// Restrict the answer to the valid subgraph</span>
<span class="k">val</span> <span class="n">validCCGraph</span> <span class="k">=</span> <span class="n">ccGraph</span><span class="o">.</span><span class="n">mask</span><span class="o">(</span><span class="n">validGraph</span><span class="o">)</span>
</code></pre></div>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@groupEdges((ED,ED)⇒ED):Graph[VD,ED]"><code>groupEdges</code></a> operator merges parallel edges (i.e., duplicate edges between
pairs of vertices) in the multigraph.  In many numerical applications, parallel edges can be <em>added</em>
(their weights combined) into a single edge thereby reducing the size of the graph.</p>

<h2 id="join-operators">Join Operators</h2>
<p><a name="join_operators"></a></p>

<p>In many cases it is necessary to join data from external collections (RDDs) with graphs.  For
example, we might have extra user properties that we want to merge with an existing graph or we
might want to pull vertex properties from one graph into another.  These tasks can be accomplished
using the <em>join</em> operators. Below we list the key join operators:</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">joinVertices</span><span class="o">[</span><span class="kt">U</span><span class="o">](</span><span class="n">table</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">U</span><span class="o">)])(</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="n">U</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">outerJoinVertices</span><span class="o">[</span><span class="kt">U</span>, <span class="kt">VD2</span><span class="o">](</span><span class="n">table</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">U</span><span class="o">)])(</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="nc">Option</span><span class="o">[</span><span class="kt">U</span><span class="o">])</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">ED</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps@joinVertices[U](RDD[(VertexId,U)])((VertexId,VD,U)⇒VD)(ClassTag[U]):Graph[VD,ED]"><code>joinVertices</code></a> operator joins the vertices with the input RDD and
returns a new graph with the vertex properties obtained by applying the user defined <code>map</code> function
to the result of the joined vertices.  Vertices without a matching value in the RDD retain their
original value.</p>

<blockquote>
  <p>Note that if the RDD contains more than one value for a given vertex only one will be used.   It
is therefore recommended that the input RDD be first made unique using the following which will
also <em>pre-index</em> the resulting values to substantially accelerate the subsequent join.</p>

  <div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">nonUniqueCosts</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexID</span>, <span class="kt">Double</span><span class="o">)]</span>
<span class="k">val</span> <span class="n">uniqueCosts</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Double</span><span class="o">]</span> <span class="k">=</span>
  <span class="n">graph</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">aggregateUsingIndex</span><span class="o">(</span><span class="n">nonUnique</span><span class="o">,</span> <span class="o">(</span><span class="n">a</span><span class="o">,</span><span class="n">b</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">a</span> <span class="o">+</span> <span class="n">b</span><span class="o">)</span>
<span class="k">val</span> <span class="n">joinedGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">joinVertices</span><span class="o">(</span><span class="n">uniqueCosts</span><span class="o">)(</span>
  <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">oldCost</span><span class="o">,</span> <span class="n">extraCost</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">oldCost</span> <span class="o">+</span> <span class="n">extraCost</span><span class="o">)</span>
</code></pre></div>
</blockquote>

<p>The more general <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@outerJoinVertices[U,VD2](RDD[(VertexId,U)])((VertexId,VD,Option[U])⇒VD2)(ClassTag[U],ClassTag[VD2]):Graph[VD2,ED]"><code>outerJoinVertices</code></a> behaves similarly to <code>joinVertices</code>
except that the user defined <code>map</code> function is applied to all vertices and can change the vertex
property type.  Because not all vertices may have a matching value in the input RDD the <code>map</code>
function takes an <code>Option</code> type.  For example, we can setup a graph for PageRank by initializing
vertex properties with their <code>outDegree</code>.</p>

<div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">outDegrees</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">outDegrees</span>
<span class="k">val</span> <span class="n">degreeGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">outerJoinVertices</span><span class="o">(</span><span class="n">outDegrees</span><span class="o">)</span> <span class="o">{</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">oldAttr</span><span class="o">,</span> <span class="n">outDegOpt</span><span class="o">)</span> <span class="k">=&gt;</span>
  <span class="n">outDegOpt</span> <span class="k">match</span> <span class="o">{</span>
    <span class="k">case</span> <span class="nc">Some</span><span class="o">(</span><span class="n">outDeg</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">outDeg</span>
    <span class="k">case</span> <span class="nc">None</span> <span class="k">=&gt;</span> <span class="mi">0</span> <span class="c1">// No outDegree means zero outDegree</span>
  <span class="o">}</span>
<span class="o">}</span>
</code></pre></div>

<blockquote>
  <p>You may have noticed the multiple parameter lists (e.g., <code>f(a)(b)</code>) curried function pattern used
in the above examples.  While we could have equally written <code>f(a)(b)</code> as <code>f(a,b)</code> this would mean
that type inference on <code>b</code> would not depend on <code>a</code>.  As a consequence, the user would need to
provide type annotation for the user defined function:</p>

  <div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">joinedGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">joinVertices</span><span class="o">(</span><span class="n">uniqueCosts</span><span class="o">,</span>
  <span class="o">(</span><span class="n">id</span><span class="k">:</span> <span class="kt">VertexID</span><span class="o">,</span> <span class="n">oldCost</span><span class="k">:</span> <span class="kt">Double</span><span class="o">,</span> <span class="n">extraCost</span><span class="k">:</span> <span class="kt">Double</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">oldCost</span> <span class="o">+</span> <span class="n">extraCost</span><span class="o">)</span>
</code></pre></div>
</blockquote>

<h2 id="neighborhood-aggregation">Neighborhood Aggregation</h2>

<p>A key part of graph computation is aggregating information about the neighborhood of each vertex.
For example we might want to know the number of followers each user has or the average age of the
the followers of each user.  Many iterative graph algorithms (e.g., PageRank, Shortest Path, and
connected components) repeatedly aggregate properties of neighboring vertices (e.g., current
PageRank Value, shortest path to the source, and smallest reachable vertex id).</p>

<h3 id="map-reduce-triplets-mapreducetriplets">Map Reduce Triplets (mapReduceTriplets)</h3>
<p><a name="mrTriplets"></a></p>

<p>The core (heavily optimized) aggregation primitive in GraphX is the
<a href="api/graphx/index.html#org.apache.spark.graphx.Graph@mapReduceTriplets[A](mapFunc:org.apache.spark.graphx.EdgeTriplet[VD,ED]=&gt;Iterator[(org.apache.spark.graphx.VertexId,A)],reduceFunc:(A,A)=&gt;A,activeSetOpt:Option[(org.apache.spark.graphx.VertexRDD[_],org.apache.spark.graphx.EdgeDirection)])(implicitevidence$10:scala.reflect.ClassTag[A]):org.apache.spark.graphx.VertexRDD[A]"><code>mapReduceTriplets</code></a> operator:</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">mapReduceTriplets</span><span class="o">[</span><span class="kt">A</span><span class="o">](</span>
      <span class="n">map</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Iterator</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">A</span><span class="o">)],</span>
      <span class="n">reduce</span><span class="k">:</span> <span class="o">(</span><span class="kt">A</span><span class="o">,</span> <span class="kt">A</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">A</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">A</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p>The <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@mapReduceTriplets[A](mapFunc:org.apache.spark.graphx.EdgeTriplet[VD,ED]=&gt;Iterator[(org.apache.spark.graphx.VertexId,A)],reduceFunc:(A,A)=&gt;A,activeSetOpt:Option[(org.apache.spark.graphx.VertexRDD[_],org.apache.spark.graphx.EdgeDirection)])(implicitevidence$10:scala.reflect.ClassTag[A]):org.apache.spark.graphx.VertexRDD[A]"><code>mapReduceTriplets</code></a> operator takes a user defined map function which
is applied to each triplet and can yield <em>messages</em> destined to either (none or both) vertices in
the triplet.  To facilitate optimized pre-aggregation, we currently only support messages destined
to the source or destination vertex of the triplet.  The user defined <code>reduce</code> function combines the
messages destined to each vertex.  The <code>mapReduceTriplets</code> operator returns a <code>VertexRDD[A]</code>
containing the aggregate message (of type <code>A</code>) destined to each vertex.  Vertices that do not
receive a message are not included in the returned <code>VertexRDD</code>.</p>

<blockquote>

<p>Note that <code>mapReduceTriplets</code> takes an additional optional <code>activeSet</code>
(not shown above see API docs for details) which restricts the map phase to edges adjacent to the
vertices in the provided <code>VertexRDD</code>: </p>


<div class="highlight"><pre><code class="scala">  <span class="n">activeSetOpt</span><span class="k">:</span> <span class="kt">Option</span><span class="o">[(</span><span class="kt">VertexRDD</span><span class="o">[</span><span class="k">_</span><span class="o">]</span>, <span class="kt">EdgeDirection</span><span class="o">)]</span> <span class="k">=</span> <span class="nc">None</span>
</code></pre></div>


<p>The EdgeDirection specifies which edges adjacent to the vertex set are included in the map
phase. If the direction is <code>In</code>, then the user defined <code>map</code> function will
only be run only on edges with the destination vertex in the active set. If the direction is
<code>Out</code>, then the <code>map</code> function will only be run only on edges originating from
vertices in the active set.  If the direction is <code>Either</code>, then the <code>map</code>
function will be run only on edges with <i>either</i> vertex in the active set.  If the direction is
<code>Both</code>, then the <code>map</code> function will be run only on edges with both vertices
in the active set.  The active set must be derived from the set of vertices in the graph.
Restricting computation to triplets adjacent to a subset of the vertices is often necessary in
incremental iterative computation and is a key part of the GraphX implementation of Pregel. </p>

</blockquote>

<p>In the following example we use the <code>mapReduceTriplets</code> operator to compute the average age of the
more senior followers of each user.</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Import random graph generation library</span>
<span class="k">import</span> <span class="nn">org.apache.spark.graphx.util.GraphGenerators</span>
<span class="c1">// Create a graph with &quot;age&quot; as the vertex property.  Here we use a random graph for simplicity.</span>
<span class="k">val</span> <span class="n">graph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Double</span>, <span class="kt">Int</span><span class="o">]</span> <span class="k">=</span>
  <span class="nc">GraphGenerators</span><span class="o">.</span><span class="n">logNormalGraph</span><span class="o">(</span><span class="n">sc</span><span class="o">,</span> <span class="n">numVertices</span> <span class="k">=</span> <span class="mi">100</span><span class="o">).</span><span class="n">mapVertices</span><span class="o">(</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="k">_</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">id</span><span class="o">.</span><span class="n">toDouble</span> <span class="o">)</span>
<span class="c1">// Compute the number of older followers and their total age</span>
<span class="k">val</span> <span class="n">olderFollowers</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Double</span><span class="o">)]</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">mapReduceTriplets</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Double</span><span class="o">)](</span>
  <span class="n">triplet</span> <span class="k">=&gt;</span> <span class="o">{</span> <span class="c1">// Map Function</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span> <span class="o">&gt;</span> <span class="n">triplet</span><span class="o">.</span><span class="n">dstAttr</span><span class="o">)</span> <span class="o">{</span>
      <span class="c1">// Send message to destination vertex containing counter and age</span>
      <span class="nc">Iterator</span><span class="o">((</span><span class="n">triplet</span><span class="o">.</span><span class="n">dstId</span><span class="o">,</span> <span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span><span class="o">)))</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
      <span class="c1">// Don&#39;t send a message for this triplet</span>
      <span class="nc">Iterator</span><span class="o">.</span><span class="n">empty</span>
    <span class="o">}</span>
  <span class="o">},</span>
  <span class="c1">// Add counter and age</span>
  <span class="o">(</span><span class="n">a</span><span class="o">,</span> <span class="n">b</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">a</span><span class="o">.</span><span class="n">_1</span> <span class="o">+</span> <span class="n">b</span><span class="o">.</span><span class="n">_1</span><span class="o">,</span> <span class="n">a</span><span class="o">.</span><span class="n">_2</span> <span class="o">+</span> <span class="n">b</span><span class="o">.</span><span class="n">_2</span><span class="o">)</span> <span class="c1">// Reduce Function</span>
<span class="o">)</span>
<span class="c1">// Divide total age by number of older followers to get average age of older followers</span>
<span class="k">val</span> <span class="n">avgAgeOfOlderFollowers</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Double</span><span class="o">]</span> <span class="k">=</span>
  <span class="n">olderFollowers</span><span class="o">.</span><span class="n">mapValues</span><span class="o">(</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">value</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">value</span> <span class="k">match</span> <span class="o">{</span> <span class="k">case</span> <span class="o">(</span><span class="n">count</span><span class="o">,</span> <span class="n">totalAge</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">totalAge</span> <span class="o">/</span> <span class="n">count</span> <span class="o">}</span> <span class="o">)</span>
<span class="c1">// Display the results</span>
<span class="n">avgAgeOfOlderFollowers</span><span class="o">.</span><span class="n">collect</span><span class="o">.</span><span class="n">foreach</span><span class="o">(</span><span class="n">println</span><span class="o">(</span><span class="k">_</span><span class="o">))</span>
</code></pre></div>

<blockquote>
  <p>Note that the <code>mapReduceTriplets</code> operation performs optimally when the messages (and the sums of
messages) are constant sized (e.g., floats and addition instead of lists and concatenation).  More
precisely, the result of <code>mapReduceTriplets</code> should ideally be sub-linear in the degree of each
vertex.</p>
</blockquote>

<h3 id="computing-degree-information">Computing Degree Information</h3>

<p>A common aggregation task is computing the degree of each vertex: the number of edges adjacent to
each vertex.  In the context of directed graphs it often necessary to know the in-degree, out-
degree, and the total degree of each vertex.  The  <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a> class contains a
collection of operators to compute the degrees of each vertex.  For example in the following we
compute the max in, out, and total degrees:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Define a reduce operation to compute the highest degree vertex</span>
<span class="k">def</span> <span class="n">max</span><span class="o">(</span><span class="n">a</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">Int</span><span class="o">),</span> <span class="n">b</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">Int</span><span class="o">))</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">Int</span><span class="o">)</span> <span class="k">=</span> <span class="o">{</span>
  <span class="k">if</span> <span class="o">(</span><span class="n">a</span><span class="o">.</span><span class="n">_2</span> <span class="o">&gt;</span> <span class="n">b</span><span class="o">.</span><span class="n">_2</span><span class="o">)</span> <span class="n">a</span> <span class="k">else</span> <span class="n">b</span>
<span class="o">}</span>
<span class="c1">// Compute the max degrees</span>
<span class="k">val</span> <span class="n">maxInDegree</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">Int</span><span class="o">)</span>  <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">inDegrees</span><span class="o">.</span><span class="n">reduce</span><span class="o">(</span><span class="n">max</span><span class="o">)</span>
<span class="k">val</span> <span class="n">maxOutDegree</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">Int</span><span class="o">)</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">outDegrees</span><span class="o">.</span><span class="n">reduce</span><span class="o">(</span><span class="n">max</span><span class="o">)</span>
<span class="k">val</span> <span class="n">maxDegrees</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">Int</span><span class="o">)</span>   <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">degrees</span><span class="o">.</span><span class="n">reduce</span><span class="o">(</span><span class="n">max</span><span class="o">)</span>
</code></pre></div>

<h3 id="collecting-neighbors">Collecting Neighbors</h3>

<p>In some cases it may be easier to express computation by collecting neighboring vertices and their
attributes at each vertex. This can be easily accomplished using the
<a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps@collectNeighborIds(EdgeDirection):VertexRDD[Array[VertexId]]"><code>collectNeighborIds</code></a> and the
<a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps@collectNeighbors(EdgeDirection):VertexRDD[Array[(VertexId,VD)]]"><code>collectNeighbors</code></a> operators.</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">GraphOps</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">collectNeighborIds</span><span class="o">(</span><span class="n">edgeDirection</span><span class="k">:</span> <span class="kt">EdgeDirection</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Array</span><span class="o">[</span><span class="kt">VertexId</span><span class="o">]]</span>
  <span class="k">def</span> <span class="n">collectNeighbors</span><span class="o">(</span><span class="n">edgeDirection</span><span class="k">:</span> <span class="kt">EdgeDirection</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span> <span class="kt">Array</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">VD</span><span class="o">)]</span> <span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<blockquote>
  <p>Note that these operators can be quite costly as they duplicate information and require
substantial communication.  If possible try expressing the same computation using the
<code>mapReduceTriplets</code> operator directly.</p>
</blockquote>

<h2 id="caching-and-uncaching">Caching and Uncaching</h2>

<p>In Spark, RDDs are not persisted in memory by default. To avoid recomputation, they must be explicitly cached when using them multiple times (see the <a href="scala-programming-guide.html#rdd-persistence">Spark Programming Guide</a>). Graphs in GraphX behave the same way. <strong>When using a graph multiple times, make sure to call <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@cache():Graph[VD,ED]"><code>Graph.cache()</code></a> on it first.</strong></p>

<p>In iterative computations, <em>uncaching</em> may also be necessary for best performance. By default, cached RDDs and graphs will remain in memory until memory pressure forces them to be evicted in LRU order. For iterative computation, intermediate results from previous iterations will fill up the cache. Though they will eventually be evicted, the unnecessary data stored in memory will slow down garbage collection. It would be more efficient to uncache intermediate results as soon as they are no longer necessary. This involves materializing (caching and forcing) a graph or RDD every iteration, uncaching all other datasets, and only using the materialized dataset in future iterations. However, because graphs are composed of multiple RDDs, it can be difficult to unpersist them correctly. <strong>For iterative computation we recommend using the Pregel API, which correctly unpersists intermediate results.</strong></p>

<h1 id="pregel-api">Pregel API</h1>
<p><a name="pregel"></a></p>

<p>Graphs are inherently recursive data-structures as properties of vertices depend on properties of
their neighbors which in turn depend on properties of <em>their</em> neighbors.  As a
consequence many important graph algorithms iteratively recompute the properties of each vertex
until a fixed-point condition is reached.  A range of graph-parallel abstractions have been proposed
to express these iterative algorithms.  GraphX exposes a Pregel-like operator which is a fusion of
the widely used Pregel and GraphLab abstractions.</p>

<p>At a high-level the Pregel operator in GraphX is a bulk-synchronous parallel messaging abstraction
<em>constrained to the topology of the graph</em>.  The Pregel operator executes in a series of super-steps
in which vertices receive the <em>sum</em> of their inbound messages from the previous super- step, compute
a new value for the vertex property, and then send messages to neighboring vertices in the next
super-step.  Unlike Pregel and instead more like GraphLab messages are computed in parallel as a
function of the edge triplet and the message computation has access to both the source and
destination vertex attributes.  Vertices that do not receive a message are skipped within a super-
step.  The Pregel operators terminates iteration and returns the final graph when there are no
messages remaining.</p>

<blockquote>
  <p>Note, unlike more standard Pregel implementations, vertices in GraphX can only send messages to
neighboring vertices and the message construction is done in parallel using a user defined
messaging function.  These constraints allow additional optimization within GraphX.</p>
</blockquote>

<p>The following is the type signature of the <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps@pregel[A](A,Int,EdgeDirection)((VertexId,VD,A)⇒VD,(EdgeTriplet[VD,ED])⇒Iterator[(VertexId,A)],(A,A)⇒A)(ClassTag[A]):Graph[VD,ED]">Pregel operator</a> as well as a <em>sketch</em>
of its implementation (note calls to graph.cache have been removed):</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">GraphOps</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">pregel</span><span class="o">[</span><span class="kt">A</span><span class="o">]</span>
      <span class="o">(</span><span class="n">initialMsg</span><span class="k">:</span> <span class="kt">A</span><span class="o">,</span>
       <span class="n">maxIter</span><span class="k">:</span> <span class="kt">Int</span> <span class="o">=</span> <span class="nc">Int</span><span class="o">.</span><span class="nc">MaxValue</span><span class="o">,</span>
       <span class="n">activeDir</span><span class="k">:</span> <span class="kt">EdgeDirection</span> <span class="o">=</span> <span class="nc">EdgeDirection</span><span class="o">.</span><span class="nc">Out</span><span class="o">)</span>
      <span class="o">(</span><span class="n">vprog</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="n">A</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD</span><span class="o">,</span>
       <span class="n">sendMsg</span><span class="k">:</span> <span class="kt">EdgeTriplet</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Iterator</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">A</span><span class="o">)],</span>
       <span class="n">mergeMsg</span><span class="k">:</span> <span class="o">(</span><span class="kt">A</span><span class="o">,</span> <span class="kt">A</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">A</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span> <span class="k">=</span> <span class="o">{</span>
    <span class="c1">// Receive the initial message at each vertex</span>
    <span class="k">var</span> <span class="n">g</span> <span class="k">=</span> <span class="n">mapVertices</span><span class="o">(</span> <span class="o">(</span><span class="n">vid</span><span class="o">,</span> <span class="n">vdata</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">vprog</span><span class="o">(</span><span class="n">vid</span><span class="o">,</span> <span class="n">vdata</span><span class="o">,</span> <span class="n">initialMsg</span><span class="o">)</span> <span class="o">).</span><span class="n">cache</span><span class="o">()</span>
    <span class="c1">// compute the messages</span>
    <span class="k">var</span> <span class="n">messages</span> <span class="k">=</span> <span class="n">g</span><span class="o">.</span><span class="n">mapReduceTriplets</span><span class="o">(</span><span class="n">sendMsg</span><span class="o">,</span> <span class="n">mergeMsg</span><span class="o">)</span>
    <span class="k">var</span> <span class="n">activeMessages</span> <span class="k">=</span> <span class="n">messages</span><span class="o">.</span><span class="n">count</span><span class="o">()</span>
    <span class="c1">// Loop until no messages remain or maxIterations is achieved</span>
    <span class="k">var</span> <span class="n">i</span> <span class="k">=</span> <span class="mi">0</span>
    <span class="k">while</span> <span class="o">(</span><span class="n">activeMessages</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">maxIterations</span><span class="o">)</span> <span class="o">{</span>
      <span class="c1">// Receive the messages: -----------------------------------------------------------------------</span>
      <span class="c1">// Run the vertex program on all vertices that receive messages</span>
      <span class="k">val</span> <span class="n">newVerts</span> <span class="k">=</span> <span class="n">g</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">innerJoin</span><span class="o">(</span><span class="n">messages</span><span class="o">)(</span><span class="n">vprog</span><span class="o">).</span><span class="n">cache</span><span class="o">()</span>
      <span class="c1">// Merge the new vertex values back into the graph</span>
      <span class="n">g</span> <span class="k">=</span> <span class="n">g</span><span class="o">.</span><span class="n">outerJoinVertices</span><span class="o">(</span><span class="n">newVerts</span><span class="o">)</span> <span class="o">{</span> <span class="o">(</span><span class="n">vid</span><span class="o">,</span> <span class="n">old</span><span class="o">,</span> <span class="n">newOpt</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">newOpt</span><span class="o">.</span><span class="n">getOrElse</span><span class="o">(</span><span class="n">old</span><span class="o">)</span> <span class="o">}.</span><span class="n">cache</span><span class="o">()</span>
      <span class="c1">// Send Messages: ------------------------------------------------------------------------------</span>
      <span class="c1">// Vertices that didn&#39;t receive a message above don&#39;t appear in newVerts and therefore don&#39;t</span>
      <span class="c1">// get to send messages.  More precisely the map phase of mapReduceTriplets is only invoked</span>
      <span class="c1">// on edges in the activeDir of vertices in newVerts</span>
      <span class="n">messages</span> <span class="k">=</span> <span class="n">g</span><span class="o">.</span><span class="n">mapReduceTriplets</span><span class="o">(</span><span class="n">sendMsg</span><span class="o">,</span> <span class="n">mergeMsg</span><span class="o">,</span> <span class="nc">Some</span><span class="o">((</span><span class="n">newVerts</span><span class="o">,</span> <span class="n">activeDir</span><span class="o">))).</span><span class="n">cache</span><span class="o">()</span>
      <span class="n">activeMessages</span> <span class="k">=</span> <span class="n">messages</span><span class="o">.</span><span class="n">count</span><span class="o">()</span>
      <span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span>
    <span class="o">}</span>
    <span class="n">g</span>
  <span class="o">}</span>
<span class="o">}</span>
</code></pre></div>

<p>Notice that Pregel takes two argument lists (i.e., <code>graph.pregel(list1)(list2)</code>).  The first
argument list contains configuration parameters including the initial message, the maximum number of
iterations, and the edge direction in which to send messages (by default along out edges).  The
second argument list contains the user defined functions for receiving messages (the vertex program
<code>vprog</code>), computing messages (<code>sendMsg</code>), and combining messages <code>mergeMsg</code>.</p>

<p>We can use the Pregel operator to express computation such as single source
shortest path in the following example.</p>

<div class="highlight"><pre><code class="scala"><span class="k">import</span> <span class="nn">org.apache.spark.graphx._</span>
<span class="c1">// Import random graph generation library</span>
<span class="k">import</span> <span class="nn">org.apache.spark.graphx.util.GraphGenerators</span>
<span class="c1">// A graph with edge attributes containing distances</span>
<span class="k">val</span> <span class="n">graph</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Int</span>, <span class="kt">Double</span><span class="o">]</span> <span class="k">=</span>
  <span class="nc">GraphGenerators</span><span class="o">.</span><span class="n">logNormalGraph</span><span class="o">(</span><span class="n">sc</span><span class="o">,</span> <span class="n">numVertices</span> <span class="k">=</span> <span class="mi">100</span><span class="o">).</span><span class="n">mapEdges</span><span class="o">(</span><span class="n">e</span> <span class="k">=&gt;</span> <span class="n">e</span><span class="o">.</span><span class="n">attr</span><span class="o">.</span><span class="n">toDouble</span><span class="o">)</span>
<span class="k">val</span> <span class="n">sourceId</span><span class="k">:</span> <span class="kt">VertexId</span> <span class="o">=</span> <span class="mi">42</span> <span class="c1">// The ultimate source</span>
<span class="c1">// Initialize the graph such that all vertices except the root have distance infinity.</span>
<span class="k">val</span> <span class="n">initialGraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">mapVertices</span><span class="o">((</span><span class="n">id</span><span class="o">,</span> <span class="k">_</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="k">if</span> <span class="o">(</span><span class="n">id</span> <span class="o">==</span> <span class="n">sourceId</span><span class="o">)</span> <span class="mf">0.0</span> <span class="k">else</span> <span class="nc">Double</span><span class="o">.</span><span class="nc">PositiveInfinity</span><span class="o">)</span>
<span class="k">val</span> <span class="n">sssp</span> <span class="k">=</span> <span class="n">initialGraph</span><span class="o">.</span><span class="n">pregel</span><span class="o">(</span><span class="nc">Double</span><span class="o">.</span><span class="nc">PositiveInfinity</span><span class="o">)(</span>
  <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">dist</span><span class="o">,</span> <span class="n">newDist</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">math</span><span class="o">.</span><span class="n">min</span><span class="o">(</span><span class="n">dist</span><span class="o">,</span> <span class="n">newDist</span><span class="o">),</span> <span class="c1">// Vertex Program</span>
  <span class="n">triplet</span> <span class="k">=&gt;</span> <span class="o">{</span>  <span class="c1">// Send Message</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">attr</span> <span class="o">&lt;</span> <span class="n">triplet</span><span class="o">.</span><span class="n">dstAttr</span><span class="o">)</span> <span class="o">{</span>
      <span class="nc">Iterator</span><span class="o">((</span><span class="n">triplet</span><span class="o">.</span><span class="n">dstId</span><span class="o">,</span> <span class="n">triplet</span><span class="o">.</span><span class="n">srcAttr</span> <span class="o">+</span> <span class="n">triplet</span><span class="o">.</span><span class="n">attr</span><span class="o">))</span>
    <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
      <span class="nc">Iterator</span><span class="o">.</span><span class="n">empty</span>
    <span class="o">}</span>
  <span class="o">},</span>
  <span class="o">(</span><span class="n">a</span><span class="o">,</span><span class="n">b</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">math</span><span class="o">.</span><span class="n">min</span><span class="o">(</span><span class="n">a</span><span class="o">,</span><span class="n">b</span><span class="o">)</span> <span class="c1">// Merge Message</span>
  <span class="o">)</span>
<span class="n">println</span><span class="o">(</span><span class="n">sssp</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">collect</span><span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;\n&quot;</span><span class="o">))</span>
</code></pre></div>

<h1 id="graph-builders">Graph Builders</h1>
<p><a name="graph_builders"></a></p>

<p>GraphX provides several ways of building a graph from a collection of vertices and edges in an RDD or on disk. None of the graph builders repartitions the graph&#8217;s edges by default; instead, edges are left in their default partitions (such as their original blocks in HDFS). <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@groupEdges((ED,ED)⇒ED):Graph[VD,ED]"><code>Graph.groupEdges</code></a> requires the graph to be repartitioned because it assumes identical edges will be colocated on the same partition, so you must call <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@partitionBy(PartitionStrategy):Graph[VD,ED]"><code>Graph.partitionBy</code></a> before calling <code>groupEdges</code>.</p>

<div class="highlight"><pre><code class="scala"><span class="k">object</span> <span class="nc">GraphLoader</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">edgeListFile</span><span class="o">(</span>
      <span class="n">sc</span><span class="k">:</span> <span class="kt">SparkContext</span><span class="o">,</span>
      <span class="n">path</span><span class="k">:</span> <span class="kt">String</span><span class="o">,</span>
      <span class="n">canonicalOrientation</span><span class="k">:</span> <span class="kt">Boolean</span> <span class="o">=</span> <span class="kc">false</span><span class="o">,</span>
      <span class="n">minEdgePartitions</span><span class="k">:</span> <span class="kt">Int</span> <span class="o">=</span> <span class="mi">1</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">Int</span>, <span class="kt">Int</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p><a href="api/graphx/index.html#org.apache.spark.graphx.GraphLoader$@edgeListFile(SparkContext,String,Boolean,Int):Graph[Int,Int]"><code>GraphLoader.edgeListFile</code></a> provides a way to load a graph from a list of edges on disk. It parses an adjacency list of (source vertex ID, destination vertex ID) pairs of the following form, skipping comment lines that begin with <code>#</code>:</p>

<pre><code># This is a comment
2 1
4 1
1 2
</code></pre>

<p>It creates a <code>Graph</code> from the specified edges, automatically creating any vertices mentioned by edges. All vertex and edge attributes default to 1. The <code>canonicalOrientation</code> argument allows reorienting edges in the positive direction (<code>srcId &lt; dstId</code>), which is required by the <a href="api/graphx/index.html#org.apache.spark.graphx.lib.ConnectedComponents$">connected components</a> algorithm. The <code>minEdgePartitions</code> argument specifies the minimum number of edge partitions to generate; there may be more edge partitions than specified if, for example, the HDFS file has more blocks.</p>

<div class="highlight"><pre><code class="scala"><span class="k">object</span> <span class="nc">Graph</span> <span class="o">{</span>
  <span class="k">def</span> <span class="n">apply</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">](</span>
      <span class="n">vertices</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">VD</span><span class="o">)],</span>
      <span class="n">edges</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">Edge</span><span class="o">[</span><span class="kt">ED</span><span class="o">]],</span>
      <span class="n">defaultVertexAttr</span><span class="k">:</span> <span class="kt">VD</span> <span class="o">=</span> <span class="kc">null</span><span class="o">)</span>
    <span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>

  <span class="k">def</span> <span class="n">fromEdges</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">](</span>
      <span class="n">edges</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">Edge</span><span class="o">[</span><span class="kt">ED</span><span class="o">]],</span>
      <span class="n">defaultValue</span><span class="k">:</span> <span class="kt">VD</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span><span class="o">]</span>

  <span class="k">def</span> <span class="n">fromEdgeTuples</span><span class="o">[</span><span class="kt">VD</span><span class="o">](</span>
      <span class="n">rawEdges</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">VertexId</span><span class="o">)],</span>
      <span class="n">defaultValue</span><span class="k">:</span> <span class="kt">VD</span><span class="o">,</span>
      <span class="n">uniqueEdges</span><span class="k">:</span> <span class="kt">Option</span><span class="o">[</span><span class="kt">PartitionStrategy</span><span class="o">]</span> <span class="k">=</span> <span class="nc">None</span><span class="o">)</span><span class="k">:</span> <span class="kt">Graph</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">Int</span><span class="o">]</span>

<span class="o">}</span>
</code></pre></div>

<p><a href="api/graphx/index.html#org.apache.spark.graphx.Graph$@apply[VD,ED](RDD[(VertexId,VD)],RDD[Edge[ED]],VD)(ClassTag[VD],ClassTag[ED]):Graph[VD,ED]"><code>Graph.apply</code></a> allows creating a graph from RDDs of vertices and edges. Duplicate vertices are picked arbitrarily and vertices found in the edge RDD but not the vertex RDD are assigned the default attribute.</p>

<p><a href="api/graphx/index.html#org.apache.spark.graphx.Graph$@fromEdges[VD,ED](RDD[Edge[ED]],VD)(ClassTag[VD],ClassTag[ED]):Graph[VD,ED]"><code>Graph.fromEdges</code></a> allows creating a graph from only an RDD of edges, automatically creating any vertices mentioned by edges and assigning them the default value.</p>

<p><a href="api/graphx/index.html#org.apache.spark.graphx.Graph$@fromEdgeTuples[VD](RDD[(VertexId,VertexId)],VD,Option[PartitionStrategy])(ClassTag[VD]):Graph[VD,Int]"><code>Graph.fromEdgeTuples</code></a> allows creating a graph from only an RDD of edge tuples, assigning the edges the value 1, and automatically creating any vertices mentioned by edges and assigning them the default value. It also supports deduplicating the edges; to deduplicate, pass <code>Some</code> of a <a href="api/graphx/index.html#org.apache.spark.graphx.PartitionStrategy"><code>PartitionStrategy</code></a> as the <code>uniqueEdges</code> parameter (for example, <code>uniqueEdges = Some(PartitionStrategy.RandomVertexCut)</code>). A partition strategy is necessary to colocate identical edges on the same partition so they can be deduplicated.</p>

<h1 id="vertex-and-edge-rdds">Vertex and Edge RDDs</h1>
<p><a name="vertex_and_edge_rdds"></a></p>

<p>GraphX exposes <code>RDD</code> views of the vertices and edges stored within the graph.  However, because
GraphX maintains the vertices and edges in optimized data-structures and these data-structures
provide additional functionality, the vertices and edges are returned as <code>VertexRDD</code> and <code>EdgeRDD</code>
respectively.  In this section we review some of the additional useful functionality in these types.</p>

<h2 id="vertexrdds">VertexRDDs</h2>

<p>The <code>VertexRDD[A]</code> extends <code>RDD[(VertexID, A)]</code> and adds the additional constraint that each
<code>VertexID</code> occurs only <em>once</em>.  Moreover, <code>VertexRDD[A]</code> represents a <em>set</em> of vertices each with an
attribute of type <code>A</code>.  Internally, this is achieved by storing the vertex attributes in a reusable
hash-map data-structure.  As a consequence if two <code>VertexRDD</code>s are derived from the same base
<code>VertexRDD</code> (e.g., by <code>filter</code> or <code>mapValues</code>) they can be joined in constant time without hash
evaluations. To leverage this indexed data-structure, the <code>VertexRDD</code> exposes the following
additional functionality:</p>

<div class="highlight"><pre><code class="scala"><span class="k">class</span> <span class="nc">VertexRDD</span><span class="o">[</span><span class="kt">VD</span><span class="o">]</span> <span class="nc">extends</span> <span class="nc">RDD</span><span class="o">[(</span><span class="kt">VertexID</span>, <span class="kt">VD</span><span class="o">)]</span> <span class="o">{</span>
  <span class="c1">// Filter the vertex set but preserves the internal index</span>
  <span class="k">def</span> <span class="n">filter</span><span class="o">(</span><span class="n">pred</span><span class="k">:</span> <span class="kt">Tuple2</span><span class="o">[</span><span class="kt">VertexId</span>, <span class="kt">VD</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">Boolean</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD</span><span class="o">]</span>
  <span class="c1">// Transform the values without changing the ids (preserves the internal index)</span>
  <span class="k">def</span> <span class="n">mapValues</span><span class="o">[</span><span class="kt">VD2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="kt">VD</span> <span class="o">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD2</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">mapValues</span><span class="o">[</span><span class="kt">VD2</span><span class="o">](</span><span class="n">map</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD2</span><span class="o">]</span>
  <span class="c1">// Remove vertices from this set that appear in the other set</span>
  <span class="k">def</span> <span class="n">diff</span><span class="o">(</span><span class="n">other</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD</span><span class="o">])</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD</span><span class="o">]</span>
  <span class="c1">// Join operators that take advantage of the internal indexing to accelerate joins (substantially)</span>
  <span class="k">def</span> <span class="n">leftJoin</span><span class="o">[</span><span class="kt">VD2</span>, <span class="kt">VD3</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">VD2</span><span class="o">)])(</span><span class="n">f</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="nc">Option</span><span class="o">[</span><span class="kt">VD2</span><span class="o">])</span> <span class="k">=&gt;</span> <span class="nc">VD3</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD3</span><span class="o">]</span>
  <span class="k">def</span> <span class="n">innerJoin</span><span class="o">[</span><span class="kt">U</span>, <span class="kt">VD2</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">U</span><span class="o">)])(</span><span class="n">f</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VD</span><span class="o">,</span> <span class="n">U</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD2</span><span class="o">]</span>
  <span class="c1">// Use the index on this RDD to accelerate a `reduceByKey` operation on the input RDD.</span>
  <span class="k">def</span> <span class="n">aggregateUsingIndex</span><span class="o">[</span><span class="kt">VD2</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">VD2</span><span class="o">)],</span> <span class="n">reduceFunc</span><span class="k">:</span> <span class="o">(</span><span class="kt">VD2</span><span class="o">,</span> <span class="kt">VD2</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">VD2</span><span class="o">)</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">VD2</span><span class="o">]</span>
<span class="o">}</span>
</code></pre></div>

<p>Notice, for example,  how the <code>filter</code> operator returns an <code>VertexRDD</code>.  Filter is actually
implemented using a <code>BitSet</code> thereby reusing the index and preserving the ability to do fast joins
with other <code>VertexRDD</code>s.  Likewise, the <code>mapValues</code> operators do not allow the <code>map</code> function to
change the <code>VertexID</code> thereby enabling the same <code>HashMap</code> data-structures to be reused.  Both the
<code>leftJoin</code> and <code>innerJoin</code> are able to identify when joining two <code>VertexRDD</code>s derived from the same
<code>HashMap</code> and implement the join by linear scan rather than costly point lookups.</p>

<p>The <code>aggregateUsingIndex</code> operator is useful for efficient construction of a new <code>VertexRDD</code> from an
<code>RDD[(VertexID, A)]</code>.  Conceptually, if I have constructed a <code>VertexRDD[B]</code> over a set of vertices,
<em>which is a super-set</em> of the vertices in some <code>RDD[(VertexID, A)]</code> then I can reuse the index to
both aggregate and then subsequently index the <code>RDD[(VertexID, A)]</code>.  For example:</p>

<div class="highlight"><pre><code class="scala"><span class="k">val</span> <span class="n">setA</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span> <span class="k">=</span> <span class="nc">VertexRDD</span><span class="o">(</span><span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="mi">0L</span> <span class="n">until</span> <span class="mi">100L</span><span class="o">).</span><span class="n">map</span><span class="o">(</span><span class="n">id</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="mi">1</span><span class="o">)))</span>
<span class="k">val</span> <span class="n">rddB</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">Double</span><span class="o">)]</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="mi">0L</span> <span class="n">until</span> <span class="mi">100L</span><span class="o">).</span><span class="n">flatMap</span><span class="o">(</span><span class="n">id</span> <span class="k">=&gt;</span> <span class="nc">List</span><span class="o">((</span><span class="n">id</span><span class="o">,</span> <span class="mf">1.0</span><span class="o">),</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="mf">2.0</span><span class="o">)))</span>
<span class="c1">// There should be 200 entries in rddB</span>
<span class="n">rddB</span><span class="o">.</span><span class="n">count</span>
<span class="k">val</span> <span class="n">setB</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Double</span><span class="o">]</span> <span class="k">=</span> <span class="n">setA</span><span class="o">.</span><span class="n">aggregateUsingIndex</span><span class="o">(</span><span class="n">rddB</span><span class="o">,</span> <span class="k">_</span> <span class="o">+</span> <span class="k">_</span><span class="o">)</span>
<span class="c1">// There should be 100 entries in setB</span>
<span class="n">setB</span><span class="o">.</span><span class="n">count</span>
<span class="c1">// Joining A and B should now be fast!</span>
<span class="k">val</span> <span class="n">setC</span><span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Double</span><span class="o">]</span> <span class="k">=</span> <span class="n">setA</span><span class="o">.</span><span class="n">innerJoin</span><span class="o">(</span><span class="n">setB</span><span class="o">)((</span><span class="n">id</span><span class="o">,</span> <span class="n">a</span><span class="o">,</span> <span class="n">b</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">a</span> <span class="o">+</span> <span class="n">b</span><span class="o">)</span>
</code></pre></div>

<h2 id="edgerdds">EdgeRDDs</h2>

<p>The <code>EdgeRDD[ED]</code>, which extends <code>RDD[Edge[ED]]</code> organizes the edges in blocks partitioned using one
of the various partitioning strategies defined in <a href="api/graphx/index.html#org.apache.spark.graphx.PartitionStrategy"><code>PartitionStrategy</code></a>.  Within
each partition, edge attributes and adjacency structure, are stored separately enabling maximum
reuse when changing attribute values.</p>

<p>The three additional functions exposed by the <code>EdgeRDD</code> are:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Transform the edge attributes while preserving the structure</span>
<span class="k">def</span> <span class="n">mapValues</span><span class="o">[</span><span class="kt">ED2</span><span class="o">](</span><span class="n">f</span><span class="k">:</span> <span class="kt">Edge</span><span class="o">[</span><span class="kt">ED</span><span class="o">]</span> <span class="k">=&gt;</span> <span class="nc">ED2</span><span class="o">)</span><span class="k">:</span> <span class="kt">EdgeRDD</span><span class="o">[</span><span class="kt">ED2</span><span class="o">]</span>
<span class="c1">// Revere the edges reusing both attributes and structure</span>
<span class="k">def</span> <span class="n">reverse</span><span class="k">:</span> <span class="kt">EdgeRDD</span><span class="o">[</span><span class="kt">ED</span><span class="o">]</span>
<span class="c1">// Join two `EdgeRDD`s partitioned using the same partitioning strategy.</span>
<span class="k">def</span> <span class="n">innerJoin</span><span class="o">[</span><span class="kt">ED2</span>, <span class="kt">ED3</span><span class="o">](</span><span class="n">other</span><span class="k">:</span> <span class="kt">EdgeRDD</span><span class="o">[</span><span class="kt">ED2</span><span class="o">])(</span><span class="n">f</span><span class="k">:</span> <span class="o">(</span><span class="kt">VertexId</span><span class="o">,</span> <span class="kt">VertexId</span><span class="o">,</span> <span class="nc">ED</span><span class="o">,</span> <span class="nc">ED2</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">ED3</span><span class="o">)</span><span class="k">:</span> <span class="kt">EdgeRDD</span><span class="o">[</span><span class="kt">ED3</span><span class="o">]</span>
</code></pre></div>

<p>In most applications we have found that operations on the <code>EdgeRDD</code> are accomplished through the
graph operators or rely on operations defined in the base <code>RDD</code> class.</p>

<h1 id="optimized-representation">Optimized Representation</h1>

<p>While a detailed description of the optimizations used in the GraphX representation of distributed
graphs is beyond the scope of this guide, some high-level understanding may aid in the design of
scalable algorithms as well as optimal use of the API.  GraphX adopts a vertex-cut approach to
distributed graph partitioning:</p>

<p style="text-align: center;">
  <img src="img/edge_cut_vs_vertex_cut.png" title="Edge Cut vs. Vertex Cut" alt="Edge Cut vs. Vertex Cut" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>Rather than splitting graphs along edges, GraphX partitions the graph along vertices which can
reduce both the communication and storage overhead.  Logically, this corresponds to assigning edges
to machines and allowing vertices to span multiple machines.  The exact method of assigning edges
depends on the <a href="api/graphx/index.html#org.apache.spark.graphx.PartitionStrategy"><code>PartitionStrategy</code></a> and there are several tradeoffs to the
various heuristics.  Users can choose between different strategies by repartitioning the graph with
the <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@partitionBy(PartitionStrategy):Graph[VD,ED]"><code>Graph.partitionBy</code></a> operator.  The default partitioning strategy is to use
the initial partitioning of the edges as provided on graph construction.  However, users can easily
switch to 2D-partitioning or other heuristics included in GraphX.</p>

<p style="text-align: center;">
  <img src="img/vertex_routing_edge_tables.png" title="RDD Graph Representation" alt="RDD Graph Representation" width="50%" />
  <!-- Images are downsized intentionally to improve quality on retina displays -->
</p>

<p>Once the edges have be partitioned the key challenge to efficient graph-parallel computation is
efficiently joining vertex attributes with the edges.  Because real-world graphs typically have more
edges than vertices, we move vertex attributes to the edges.  Because not all partitions will
contain edges adjacent to all vertices we internally maintain a routing table which identifies where
to broadcast vertices when implementing the join required for operations like <code>triplets</code> and
<code>mapReduceTriplets</code>.</p>

<h1 id="graph-algorithms">Graph Algorithms</h1>
<p><a name="graph_algorithms"></a></p>

<p>GraphX includes a set of graph algorithms to simplify analytics tasks. The algorithms are contained in the <code>org.apache.spark.graphx.lib</code> package and can be accessed directly as methods on <code>Graph</code> via <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a>. This section describes the algorithms and how they are used.</p>

<h2 id="pagerank">PageRank</h2>
<p><a name="pagerank"></a></p>

<p>PageRank measures the importance of each vertex in a graph, assuming an edge from <em>u</em> to <em>v</em> represents an endorsement of <em>v</em>&#8217;s importance by <em>u</em>. For example, if a Twitter user is followed by many others, the user will be ranked highly.</p>

<p>GraphX comes with static and dynamic implementations of PageRank as methods on the <a href="api/graphx/index.html#org.apache.spark.graphx.lib.PageRank$"><code>PageRank</code> object</a>. Static PageRank runs for a fixed number of iterations, while dynamic PageRank runs until the ranks converge (i.e., stop changing by more than a specified tolerance). <a href="api/graphx/index.html#org.apache.spark.graphx.GraphOps"><code>GraphOps</code></a> allows calling these algorithms directly as methods on <code>Graph</code>.</p>

<p>GraphX also includes an example social network dataset that we can run PageRank on. A set of users is given in <code>graphx/data/users.txt</code>, and a set of relationships between users is given in <code>graphx/data/followers.txt</code>. We compute the PageRank of each user as follows:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Load the edges as a graph</span>
<span class="k">val</span> <span class="n">graph</span> <span class="k">=</span> <span class="nc">GraphLoader</span><span class="o">.</span><span class="n">edgeListFile</span><span class="o">(</span><span class="n">sc</span><span class="o">,</span> <span class="s">&quot;graphx/data/followers.txt&quot;</span><span class="o">)</span>
<span class="c1">// Run PageRank</span>
<span class="k">val</span> <span class="n">ranks</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">pageRank</span><span class="o">(</span><span class="mf">0.0001</span><span class="o">).</span><span class="n">vertices</span>
<span class="c1">// Join the ranks with the usernames</span>
<span class="k">val</span> <span class="n">users</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">textFile</span><span class="o">(</span><span class="s">&quot;graphx/data/users.txt&quot;</span><span class="o">).</span><span class="n">map</span> <span class="o">{</span> <span class="n">line</span> <span class="k">=&gt;</span>
  <span class="k">val</span> <span class="n">fields</span> <span class="k">=</span> <span class="n">line</span><span class="o">.</span><span class="n">split</span><span class="o">(</span><span class="s">&quot;,&quot;</span><span class="o">)</span>
  <span class="o">(</span><span class="n">fields</span><span class="o">(</span><span class="mi">0</span><span class="o">).</span><span class="n">toLong</span><span class="o">,</span> <span class="n">fields</span><span class="o">(</span><span class="mi">1</span><span class="o">))</span>
<span class="o">}</span>
<span class="k">val</span> <span class="n">ranksByUsername</span> <span class="k">=</span> <span class="n">users</span><span class="o">.</span><span class="n">join</span><span class="o">(</span><span class="n">ranks</span><span class="o">).</span><span class="n">map</span> <span class="o">{</span>
  <span class="k">case</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="o">(</span><span class="n">username</span><span class="o">,</span> <span class="n">rank</span><span class="o">))</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">username</span><span class="o">,</span> <span class="n">rank</span><span class="o">)</span>
<span class="o">}</span>
<span class="c1">// Print the result</span>
<span class="n">println</span><span class="o">(</span><span class="n">ranksByUsername</span><span class="o">.</span><span class="n">collect</span><span class="o">().</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;\n&quot;</span><span class="o">))</span>
</code></pre></div>

<h2 id="connected-components">Connected Components</h2>

<p>The connected components algorithm labels each connected component of the graph with the ID of its lowest-numbered vertex. For example, in a social network, connected components can approximate clusters. GraphX contains an implementation of the algorithm in the <a href="api/graphx/index.html#org.apache.spark.graphx.lib.ConnectedComponents$"><code>ConnectedComponents</code> object</a>, and we compute the connected components of the example social network dataset from the <a href="#pagerank">PageRank section</a> as follows:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Load the graph as in the PageRank example</span>
<span class="k">val</span> <span class="n">graph</span> <span class="k">=</span> <span class="nc">GraphLoader</span><span class="o">.</span><span class="n">edgeListFile</span><span class="o">(</span><span class="n">sc</span><span class="o">,</span> <span class="s">&quot;graphx/data/followers.txt&quot;</span><span class="o">)</span>
<span class="c1">// Find the connected components</span>
<span class="k">val</span> <span class="n">cc</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">connectedComponents</span><span class="o">().</span><span class="n">vertices</span>
<span class="c1">// Join the connected components with the usernames</span>
<span class="k">val</span> <span class="n">users</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">textFile</span><span class="o">(</span><span class="s">&quot;graphx/data/users.txt&quot;</span><span class="o">).</span><span class="n">map</span> <span class="o">{</span> <span class="n">line</span> <span class="k">=&gt;</span>
  <span class="k">val</span> <span class="n">fields</span> <span class="k">=</span> <span class="n">line</span><span class="o">.</span><span class="n">split</span><span class="o">(</span><span class="s">&quot;,&quot;</span><span class="o">)</span>
  <span class="o">(</span><span class="n">fields</span><span class="o">(</span><span class="mi">0</span><span class="o">).</span><span class="n">toLong</span><span class="o">,</span> <span class="n">fields</span><span class="o">(</span><span class="mi">1</span><span class="o">))</span>
<span class="o">}</span>
<span class="k">val</span> <span class="n">ccByUsername</span> <span class="k">=</span> <span class="n">users</span><span class="o">.</span><span class="n">join</span><span class="o">(</span><span class="n">cc</span><span class="o">).</span><span class="n">map</span> <span class="o">{</span>
  <span class="k">case</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="o">(</span><span class="n">username</span><span class="o">,</span> <span class="n">cc</span><span class="o">))</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">username</span><span class="o">,</span> <span class="n">cc</span><span class="o">)</span>
<span class="o">}</span>
<span class="c1">// Print the result</span>
<span class="n">println</span><span class="o">(</span><span class="n">ccByUsername</span><span class="o">.</span><span class="n">collect</span><span class="o">().</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;\n&quot;</span><span class="o">))</span>
</code></pre></div>

<h2 id="triangle-counting">Triangle Counting</h2>

<p>A vertex is part of a triangle when it has two adjacent vertices with an edge between them. GraphX implements a triangle counting algorithm in the <a href="api/graphx/index.html#org.apache.spark.graphx.lib.TriangleCount$"><code>TriangleCount</code> object</a> that determines the number of triangles passing through each vertex, providing a measure of clustering. We compute the triangle count of the social network dataset from the <a href="#pagerank">PageRank section</a>. <em>Note that <code>TriangleCount</code> requires the edges to be in canonical orientation (<code>srcId &lt; dstId</code>) and the graph to be partitioned using <a href="api/graphx/index.html#org.apache.spark.graphx.Graph@partitionBy(PartitionStrategy):Graph[VD,ED]"><code>Graph.partitionBy</code></a>.</em></p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Load the edges in canonical order and partition the graph for triangle count</span>
<span class="k">val</span> <span class="n">graph</span> <span class="k">=</span> <span class="nc">GraphLoader</span><span class="o">.</span><span class="n">edgeListFile</span><span class="o">(</span><span class="n">sc</span><span class="o">,</span> <span class="s">&quot;graphx/data/followers.txt&quot;</span><span class="o">,</span> <span class="kc">true</span><span class="o">).</span><span class="n">partitionBy</span><span class="o">(</span><span class="nc">PartitionStrategy</span><span class="o">.</span><span class="nc">RandomVertexCut</span><span class="o">)</span>
<span class="c1">// Find the triangle count for each vertex</span>
<span class="k">val</span> <span class="n">triCounts</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">triangleCount</span><span class="o">().</span><span class="n">vertices</span>
<span class="c1">// Join the triangle counts with the usernames</span>
<span class="k">val</span> <span class="n">users</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">textFile</span><span class="o">(</span><span class="s">&quot;graphx/data/users.txt&quot;</span><span class="o">).</span><span class="n">map</span> <span class="o">{</span> <span class="n">line</span> <span class="k">=&gt;</span>
  <span class="k">val</span> <span class="n">fields</span> <span class="k">=</span> <span class="n">line</span><span class="o">.</span><span class="n">split</span><span class="o">(</span><span class="s">&quot;,&quot;</span><span class="o">)</span>
  <span class="o">(</span><span class="n">fields</span><span class="o">(</span><span class="mi">0</span><span class="o">).</span><span class="n">toLong</span><span class="o">,</span> <span class="n">fields</span><span class="o">(</span><span class="mi">1</span><span class="o">))</span>
<span class="o">}</span>
<span class="k">val</span> <span class="n">triCountByUsername</span> <span class="k">=</span> <span class="n">users</span><span class="o">.</span><span class="n">join</span><span class="o">(</span><span class="n">triCounts</span><span class="o">).</span><span class="n">map</span> <span class="o">{</span> <span class="k">case</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="o">(</span><span class="n">username</span><span class="o">,</span> <span class="n">tc</span><span class="o">))</span> <span class="k">=&gt;</span>
  <span class="o">(</span><span class="n">username</span><span class="o">,</span> <span class="n">tc</span><span class="o">)</span>
<span class="o">}</span>
<span class="c1">// Print the result</span>
<span class="n">println</span><span class="o">(</span><span class="n">triCountByUsername</span><span class="o">.</span><span class="n">collect</span><span class="o">().</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;\n&quot;</span><span class="o">))</span>
</code></pre></div>

<h1 id="examples">Examples</h1>

<p>Suppose I want to build a graph from some text files, restrict the graph
to important relationships and users, run page-rank on the sub-graph, and
then finally return attributes associated with the top users.  I can do
all of this in just a few lines with GraphX:</p>

<div class="highlight"><pre><code class="scala"><span class="c1">// Connect to the Spark cluster</span>
<span class="k">val</span> <span class="n">sc</span> <span class="k">=</span> <span class="k">new</span> <span class="nc">SparkContext</span><span class="o">(</span><span class="s">&quot;spark://master.amplab.org&quot;</span><span class="o">,</span> <span class="s">&quot;research&quot;</span><span class="o">)</span>

<span class="c1">// Load my user data and parse into tuples of user id and attribute list</span>
<span class="k">val</span> <span class="n">users</span> <span class="k">=</span> <span class="o">(</span><span class="n">sc</span><span class="o">.</span><span class="n">textFile</span><span class="o">(</span><span class="s">&quot;graphx/data/users.txt&quot;</span><span class="o">)</span>
  <span class="o">.</span><span class="n">map</span><span class="o">(</span><span class="n">line</span> <span class="k">=&gt;</span> <span class="n">line</span><span class="o">.</span><span class="n">split</span><span class="o">(</span><span class="s">&quot;,&quot;</span><span class="o">)).</span><span class="n">map</span><span class="o">(</span> <span class="n">parts</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">parts</span><span class="o">.</span><span class="n">head</span><span class="o">.</span><span class="n">toLong</span><span class="o">,</span> <span class="n">parts</span><span class="o">.</span><span class="n">tail</span><span class="o">)</span> <span class="o">))</span>

<span class="c1">// Parse the edge data which is already in userId -&gt; userId format</span>
<span class="k">val</span> <span class="n">followerGraph</span> <span class="k">=</span> <span class="nc">GraphLoader</span><span class="o">.</span><span class="n">edgeListFile</span><span class="o">(</span><span class="n">sc</span><span class="o">,</span> <span class="s">&quot;graphx/data/followers.txt&quot;</span><span class="o">)</span>

<span class="c1">// Attach the user attributes</span>
<span class="k">val</span> <span class="n">graph</span> <span class="k">=</span> <span class="n">followerGraph</span><span class="o">.</span><span class="n">outerJoinVertices</span><span class="o">(</span><span class="n">users</span><span class="o">)</span> <span class="o">{</span>
  <span class="k">case</span> <span class="o">(</span><span class="n">uid</span><span class="o">,</span> <span class="n">deg</span><span class="o">,</span> <span class="nc">Some</span><span class="o">(</span><span class="n">attrList</span><span class="o">))</span> <span class="k">=&gt;</span> <span class="n">attrList</span>
  <span class="c1">// Some users may not have attributes so we set them as empty</span>
  <span class="k">case</span> <span class="o">(</span><span class="n">uid</span><span class="o">,</span> <span class="n">deg</span><span class="o">,</span> <span class="nc">None</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="nc">Array</span><span class="o">.</span><span class="n">empty</span><span class="o">[</span><span class="kt">String</span><span class="o">]</span>
<span class="o">}</span>

<span class="c1">// Restrict the graph to users with usernames and names</span>
<span class="k">val</span> <span class="n">subgraph</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">subgraph</span><span class="o">(</span><span class="n">vpred</span> <span class="k">=</span> <span class="o">(</span><span class="n">vid</span><span class="o">,</span> <span class="n">attr</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="n">attr</span><span class="o">.</span><span class="n">size</span> <span class="o">==</span> <span class="mi">2</span><span class="o">)</span>

<span class="c1">// Compute the PageRank</span>
<span class="k">val</span> <span class="n">pagerankGraph</span> <span class="k">=</span> <span class="n">subgraph</span><span class="o">.</span><span class="n">pageRank</span><span class="o">(</span><span class="mf">0.001</span><span class="o">)</span>

<span class="c1">// Get the attributes of the top pagerank users</span>
<span class="k">val</span> <span class="n">userInfoWithPageRank</span> <span class="k">=</span> <span class="n">subgraph</span><span class="o">.</span><span class="n">outerJoinVertices</span><span class="o">(</span><span class="n">pagerankGraph</span><span class="o">.</span><span class="n">vertices</span><span class="o">)</span> <span class="o">{</span>
  <span class="k">case</span> <span class="o">(</span><span class="n">uid</span><span class="o">,</span> <span class="n">attrList</span><span class="o">,</span> <span class="nc">Some</span><span class="o">(</span><span class="n">pr</span><span class="o">))</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="n">pr</span><span class="o">,</span> <span class="n">attrList</span><span class="o">.</span><span class="n">toList</span><span class="o">)</span>
  <span class="k">case</span> <span class="o">(</span><span class="n">uid</span><span class="o">,</span> <span class="n">attrList</span><span class="o">,</span> <span class="nc">None</span><span class="o">)</span> <span class="k">=&gt;</span> <span class="o">(</span><span class="mf">0.0</span><span class="o">,</span> <span class="n">attrList</span><span class="o">.</span><span class="n">toList</span><span class="o">)</span>
<span class="o">}</span>

<span class="n">println</span><span class="o">(</span><span class="n">userInfoWithPageRank</span><span class="o">.</span><span class="n">vertices</span><span class="o">.</span><span class="n">top</span><span class="o">(</span><span class="mi">5</span><span class="o">)(</span><span class="nc">Ordering</span><span class="o">.</span><span class="n">by</span><span class="o">(</span><span class="k">_</span><span class="o">.</span><span class="n">_2</span><span class="o">.</span><span class="n">_1</span><span class="o">)).</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;\n&quot;</span><span class="o">))</span>
</code></pre></div>


            <!-- Main hero unit for a primary marketing message or call to action -->
            <!--<div class="hero-unit">
                <h1>Hello, world!</h1>
                <p>This is a template for a simple marketing or informational website. It includes a large callout called the hero unit and three supporting pieces of content. Use it as a starting point to create something more unique.</p>
                <p><a class="btn btn-primary btn-large">Learn more &raquo;</a></p>
            </div>-->

            <!-- Example row of columns -->
            <!--<div class="row">
                <div class="span4">
                    <h2>Heading</h2>
                    <p>Donec id elit non mi porta gravida at eget metus. Fusce dapibus, tellus ac cursus commodo, tortor mauris condimentum nibh, ut fermentum massa justo sit amet risus. Etiam porta sem malesuada magna mollis euismod. Donec sed odio dui. </p>
                    <p><a class="btn" href="#">View details &raquo;</a></p>
                </div>
                <div class="span4">
                    <h2>Heading</h2>
                    <p>Donec id elit non mi porta gravida at eget metus. Fusce dapibus, tellus ac cursus commodo, tortor mauris condimentum nibh, ut fermentum massa justo sit amet risus. Etiam porta sem malesuada magna mollis euismod. Donec sed odio dui. </p>
                    <p><a class="btn" href="#">View details &raquo;</a></p>
               </div>
                <div class="span4">
                    <h2>Heading</h2>
                    <p>Donec sed odio dui. Cras justo odio, dapibus ac facilisis in, egestas eget quam. Vestibulum id ligula porta felis euismod semper. Fusce dapibus, tellus ac cursus commodo, tortor mauris condimentum nibh, ut fermentum massa justo sit amet risus.</p>
                    <p><a class="btn" href="#">View details &raquo;</a></p>
                </div>
            </div>

            <hr>-->

        </div> <!-- /container -->

        <script src="js/vendor/jquery-1.8.0.min.js"></script>
        <script src="js/vendor/bootstrap.min.js"></script>
        <script src="js/main.js"></script>

        <!-- A script to fix internal hash links because we have an overlapping top bar.
             Based on https://github.com/twitter/bootstrap/issues/193#issuecomment-2281510 -->
        <script>
          $(function() {
            function maybeScrollToHash() {
              if (window.location.hash && $(window.location.hash).length) {
                var newTop = $(window.location.hash).offset().top - $('#topbar').height() - 5;
                $(window).scrollTop(newTop);
              }
            }
            $(window).bind('hashchange', function() {
              maybeScrollToHash();
            });
            // Scroll now too in case we had opened the page on a hash, but wait 1 ms because some browsers
            // will try to do *their* initial scroll after running the onReady handler.
            setTimeout(function() { maybeScrollToHash(); }, 1)
          })
        </script>

    </body>
</html>