http://git-wip-us.apache.org/repos/asf/spark-website/blob/d2bcf185/site/docs/2.1.0/graphx-programming-guide.html ---------------------------------------------------------------------- diff --git a/site/docs/2.1.0/graphx-programming-guide.html b/site/docs/2.1.0/graphx-programming-guide.html index 780d1ab..08b3380 100644 --- a/site/docs/2.1.0/graphx-programming-guide.html +++ b/site/docs/2.1.0/graphx-programming-guide.html @@ -129,42 +129,42 @@ <ul id="markdown-toc"> - <li><a href="#overview" id="markdown-toc-overview">Overview</a></li> - <li><a href="#getting-started" id="markdown-toc-getting-started">Getting Started</a></li> - <li><a href="#the-property-graph" id="markdown-toc-the-property-graph">The Property Graph</a> <ul> - <li><a href="#example-property-graph" id="markdown-toc-example-property-graph">Example Property Graph</a></li> + <li><a href="#overview">Overview</a></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" id="markdown-toc-graph-operators">Graph Operators</a> <ul> - <li><a href="#summary-list-of-operators" id="markdown-toc-summary-list-of-operators">Summary List of Operators</a></li> - <li><a href="#property-operators" id="markdown-toc-property-operators">Property Operators</a></li> - <li><a href="#structural-operators" id="markdown-toc-structural-operators">Structural Operators</a></li> - <li><a href="#join-operators" id="markdown-toc-join-operators">Join Operators</a></li> - <li><a href="#neighborhood-aggregation" id="markdown-toc-neighborhood-aggregation">Neighborhood Aggregation</a> <ul> - <li><a href="#aggregate-messages-aggregatemessages" id="markdown-toc-aggregate-messages-aggregatemessages">Aggregate Messages (aggregateMessages)</a></li> - <li><a href="#map-reduce-triplets-transition-guide-legacy" id="markdown-toc-map-reduce-triplets-transition-guide-legacy">Map Reduce Triplets Transition Guide (Legacy)</a></li> - <li><a href="#computing-degree-information" id="markdown-toc-computing-degree-information">Computing Degree Information</a></li> - <li><a href="#collecting-neighbors" id="markdown-toc-collecting-neighbors">Collecting Neighbors</a></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="#aggregate-messages-aggregatemessages">Aggregate Messages (aggregateMessages)</a></li> + <li><a href="#map-reduce-triplets-transition-guide-legacy">Map Reduce Triplets Transition Guide (Legacy)</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" id="markdown-toc-caching-and-uncaching">Caching and Uncaching</a></li> + <li><a href="#caching-and-uncaching">Caching and Uncaching</a></li> </ul> </li> - <li><a href="#pregel-api" id="markdown-toc-pregel-api">Pregel API</a></li> - <li><a href="#graph-builders" id="markdown-toc-graph-builders">Graph Builders</a></li> - <li><a href="#vertex-and-edge-rdds" id="markdown-toc-vertex-and-edge-rdds">Vertex and Edge RDDs</a> <ul> - <li><a href="#vertexrdds" id="markdown-toc-vertexrdds">VertexRDDs</a></li> - <li><a href="#edgerdds" id="markdown-toc-edgerdds">EdgeRDDs</a></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" id="markdown-toc-optimized-representation">Optimized Representation</a></li> - <li><a href="#graph-algorithms" id="markdown-toc-graph-algorithms">Graph Algorithms</a> <ul> - <li><a href="#pagerank" id="markdown-toc-pagerank">PageRank</a></li> - <li><a href="#connected-components" id="markdown-toc-connected-components">Connected Components</a></li> - <li><a href="#triangle-counting" id="markdown-toc-triangle-counting">Triangle Counting</a></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" id="markdown-toc-examples">Examples</a></li> + <li><a href="#examples">Examples</a></li> </ul> <!-- All the documentation links --> @@ -188,10 +188,10 @@ operators (e.g., <a href="#structural_operators">subgraph</a>, <a href="#join_op <p>To get started you first need to import Spark and GraphX into your project, as follows:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="scala"><span class="k">import</span> <span class="nn">org.apache.spark._</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> +<span class="k">import</span> <span class="nn">org.apache.spark.rdd.RDD</span></code></pre></figure> <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> @@ -222,11 +222,11 @@ arrays.</p> 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="language-scala" data-lang="scala"><span class="k">class</span> <span class="nc">VertexProperty</span><span class="o">()</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> +<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></figure> <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 @@ -239,10 +239,10 @@ RDDs, each partition of the graph can be recreated on a different machine in 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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="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> +<span class="o">}</span></code></pre></figure> <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 @@ -264,7 +264,7 @@ with a string describing the relationships between collaborators:</p> <p>The resulting graph would have the type signature:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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></figure> <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 @@ -272,7 +272,7 @@ generators and these are discussed in more detail in the section on <a href="api/scala/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="language-scala" data-lang="scala"><span class="c1">// Assume the SparkContext has already been constructed</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> @@ -285,7 +285,7 @@ code constructs a graph from a collection of RDDs:</p> <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">"John Doe"</span><span class="o">,</span> <span class="s">"Missing"</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> +<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></figure> <p>In the above example we make use of the <a href="api/scala/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> @@ -294,11 +294,11 @@ 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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">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">=></span> <span class="n">pos</span> <span class="o">==</span> <span class="s">"postdoc"</span> <span class="o">}.</span><span class="n">count</span> <span class="c1">// Count all the edges where src > 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">=></span> <span class="n">e</span><span class="o">.</span><span class="n">srcId</span> <span class="o">></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> +<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">=></span> <span class="n">e</span><span class="o">.</span><span class="n">srcId</span> <span class="o">></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></figure> <blockquote> <p>Note that <code>graph.vertices</code> returns an <code>VertexRDD[(String, String)]</code> which extends @@ -306,17 +306,17 @@ and <code>graph.edges</code> members respectively.</p> 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> + <figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="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">=></span> <span class="n">src</span> <span class="o">></span> <span class="n">dst</span> <span class="o">}.</span><span class="n">count</span></code></pre></figure> </blockquote> -<div class="highlight"><pre><code class="language-scala" data-lang="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">=></span> <span class="n">src</span> <span class="o">></span> <span class="n">dst</span> <span class="o">}.</span><span class="n">count</span></code></pre></div> <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/scala/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="language-sql" data-lang="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> +<figure class="highlight"><pre><code class="language-sql" data-lang="sql"><span></span><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> +<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></figure> <p>or graphically as:</p> @@ -329,12 +329,12 @@ The triplet view logically joins the vertex and edge properties yielding an <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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">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">=></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">" is the "</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">" of "</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> +<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></figure> <h1 id="graph-operators">Graph Operators</h1> @@ -346,9 +346,9 @@ core operators are defined in <a href="api/scala/index.html#org.apache.spark.gra 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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">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> +<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></figure> <p>The reason for differentiating between core graph operations and <a href="api/scala/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 @@ -362,7 +362,7 @@ signatures have been simplified (e.g., default arguments and type constraints re advanced functionality has been removed so please consult the API docs for the official list of operations.</p> -<div class="highlight"><pre><code class="language-scala" data-lang="scala"><span class="cm">/** Summary of the functionality in the property graph */</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> @@ -419,17 +419,17 @@ operations.</p> <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> +<span class="o">}</span></code></pre></figure> <h2 id="property-operators">Property Operators</h2> <p>Like the RDD <code>map</code> operator, the property graph contains the following:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="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">=></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">=></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">=></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> +<span class="o">}</span></code></pre></figure> <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> @@ -440,27 +440,27 @@ which allows the resulting graph to reuse the structural indices of the original 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> + <figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></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></figure> </blockquote> -<div class="highlight"><pre><code class="language-scala" data-lang="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">=></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> <p>Instead, use <a href="api/scala/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> + <figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></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></figure> </blockquote> -<div class="highlight"><pre><code class="language-scala" data-lang="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">=></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> <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="language-scala" data-lang="scala"><span class="c1">// Given a graph where the vertex property is the out degree</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></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">=></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">=></span> <span class="mf">1.0</span><span class="o">)</span></code></pre></div> + <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">=></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">=></span> <span class="mf">1.0</span><span class="o">)</span></code></pre></figure> <p><a name="structural_operators"></a></p> @@ -469,13 +469,13 @@ unnecessary properties. For example, given a graph with the out degrees as the <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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="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">=></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">=></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">=></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> +<span class="o">}</span></code></pre></figure> <p>The <a href="api/scala/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 @@ -488,7 +488,7 @@ satisfy the edge predicate <em>and connect vertices that satisfy the vertex pred 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="language-scala" data-lang="scala"><span class="c1">// Create an RDD for the vertices</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">"rxin"</span><span class="o">,</span> <span class="s">"student"</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">"jgonzal"</span><span class="o">,</span> <span class="s">"postdoc"</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">"franklin"</span><span class="o">,</span> <span class="s">"prof"</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">"istoica"</span><span class="o">,</span> <span class="s">"prof"</span><span class="o">)),</span> @@ -513,7 +513,7 @@ interest or eliminate broken links. For example in the following code we remove <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">=></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">" is the "</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">" of "</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> +<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></figure> <blockquote> <p>Note in the above example only the vertex predicate is provided. The <code>subgraph</code> operator defaults @@ -526,12 +526,12 @@ vertices and edges that are also found in the input graph. This can be used in 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="language-scala" data-lang="scala"><span class="c1">// Run Connected Components</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></span> <span class="n">attr</span><span class="o">.</span><span class="n">_2</span> <span class="o">!=</span> <span class="s">"Missing"</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> +<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></figure> <p>The <a href="api/scala/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> @@ -546,12 +546,12 @@ example, we might have extra user properties that we want to merge with an exist 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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="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">=></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">=></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> +<span class="o">}</span></code></pre></figure> <p>The <a href="api/scala/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 @@ -563,12 +563,12 @@ original value.</p> is therefore recommended that the input RDD be made unique using the following which will also <em>pre-index</em> the resulting values to substantially accelerate the subsequent join.</p> -</blockquote> -<div class="highlight"><pre><code class="language-scala" data-lang="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> + <figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></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">=></span> <span class="n">oldCost</span> <span class="o">+</span> <span class="n">extraCost</span><span class="o">)</span></code></pre></div> + <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">=></span> <span class="n">oldCost</span> <span class="o">+</span> <span class="n">extraCost</span><span class="o">)</span></code></pre></figure> +</blockquote> <p>The more general <a href="api/scala/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 @@ -576,13 +576,13 @@ property type. Because not all vertices may have a matching value in the input 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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">=</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">=></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">=></span> <span class="n">outDeg</span> <span class="k">case</span> <span class="nc">None</span> <span class="k">=></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> +<span class="o">}</span></code></pre></figure> <blockquote> <p>You may have noticed the multiple parameter lists (e.g., <code>f(a)(b)</code>) curried function pattern used @@ -590,9 +590,9 @@ in the above examples. While we could have equally written <code>f(a)(b)</code> 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> + <figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="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">=></span> <span class="n">oldCost</span> <span class="o">+</span> <span class="n">extraCost</span><span class="o">)</span></code></pre></figure> </blockquote> -<div class="highlight"><pre><code class="language-scala" data-lang="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">=></span> <span class="n">oldCost</span> <span class="o">+</span> <span class="n">extraCost</span><span class="o">)</span></code></pre></div> <blockquote> @@ -623,13 +623,13 @@ relatively small, we provide a transition guide below.</p> This operator applies a user defined <code>sendMsg</code> function to each <i>edge triplet</i> in the graph and then uses the <code>mergeMsg</code> function to aggregate those messages at their destination vertex.</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="k">def</span> <span class="n">aggregateMessages</span><span class="o">[</span><span class="kt">Msg:</span> <span class="kt">ClassTag</span><span class="o">](</span> <span class="n">sendMsg</span><span class="k">:</span> <span class="kt">EdgeContext</span><span class="o">[</span><span class="kt">VD</span>, <span class="kt">ED</span>, <span class="kt">Msg</span><span class="o">]</span> <span class="k">=></span> <span class="nc">Unit</span><span class="o">,</span> <span class="n">mergeMsg</span><span class="k">:</span> <span class="o">(</span><span class="kt">Msg</span><span class="o">,</span> <span class="kt">Msg</span><span class="o">)</span> <span class="k">=></span> <span class="nc">Msg</span><span class="o">,</span> <span class="n">tripletFields</span><span class="k">:</span> <span class="kt">TripletFields</span> <span class="o">=</span> <span class="nc">TripletFields</span><span class="o">.</span><span class="nc">All</span><span class="o">)</span> <span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Msg</span><span class="o">]</span> -<span class="o">}</span></code></pre></div> +<span class="o">}</span></code></pre></figure> <p>The user defined <code>sendMsg</code> function takes an <a href="api/scala/index.html#org.apache.spark.graphx.EdgeContext"><code>EdgeContext</code></a>, which exposes the source and destination attributes along with the edge attribute and functions @@ -669,7 +669,7 @@ slightly unreliable and instead opted for more explicit user control.</p> <p>In the following example we use the <a href="api/scala/index.html#org.apache.spark.graphx.Graph@aggregateMessages[A]((EdgeContext[VD,ED,A])âUnit,(A,A)âA,TripletFields)(ClassTag[A]):VertexRDD[A]"><code>aggregateMessages</code></a> operator to compute the average age of the more senior followers of each user.</p> -<div class="highlight"><pre><span class="k">import</span> <span class="nn">org.apache.spark.graphx.</span><span class="o">{</span><span class="nc">Graph</span><span class="o">,</span> <span class="nc">VertexRDD</span><span class="o">}</span> +<div class="highlight"><pre><span></span><span class="k">import</span> <span class="nn">org.apache.spark.graphx.</span><span class="o">{</span><span class="nc">Graph</span><span class="o">,</span> <span class="nc">VertexRDD</span><span class="o">}</span> <span class="k">import</span> <span class="nn">org.apache.spark.graphx.util.GraphGenerators</span> <span class="c1">// Create a graph with "age" as the vertex property.</span> @@ -708,12 +708,12 @@ messages) are constant sized (e.g., floats and addition instead of lists and con <p>In earlier versions of GraphX neighborhood aggregation was accomplished using the <code>mapReduceTriplets</code> operator:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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="k">def</span> <span class="n">mapReduceTriplets</span><span class="o">[</span><span class="kt">Msg</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">=></span> <span class="nc">Iterator</span><span class="o">[(</span><span class="kt">VertexId</span>, <span class="kt">Msg</span><span class="o">)],</span> <span class="n">reduce</span><span class="k">:</span> <span class="o">(</span><span class="kt">Msg</span><span class="o">,</span> <span class="kt">Msg</span><span class="o">)</span> <span class="k">=></span> <span class="nc">Msg</span><span class="o">)</span> <span class="k">:</span> <span class="kt">VertexRDD</span><span class="o">[</span><span class="kt">Msg</span><span class="o">]</span> -<span class="o">}</span></code></pre></div> +<span class="o">}</span></code></pre></figure> <p>The <code>mapReduceTriplets</code> operator takes a user defined map function which is applied to each triplet and can yield <em>messages</em> which are aggregated using the user defined @@ -727,21 +727,21 @@ in the triplet are actually required.</p> <p>The following code block using <code>mapReduceTriplets</code>:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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">Int</span>, <span class="kt">Float</span><span class="o">]</span> <span class="k">=</span> <span class="o">...</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">Float</span><span class="o">]</span> <span class="k">=</span> <span class="o">...</span> <span class="k">def</span> <span class="n">msgFun</span><span class="o">(</span><span class="n">triplet</span><span class="k">:</span> <span class="kt">Triplet</span><span class="o">[</span><span class="kt">Int</span>, <span class="kt">Float</span><span class="o">])</span><span class="k">:</span> <span class="kt">Iterator</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="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="s">"Hi"</span><span class="o">))</span> <span class="o">}</span> <span class="k">def</span> <span class="n">reduceFun</span><span class="o">(</span><span class="n">a</span><span class="k">:</span> <span class="kt">String</span><span class="o">,</span> <span class="n">b</span><span class="k">:</span> <span class="kt">String</span><span class="o">)</span><span class="k">:</span> <span class="kt">String</span> <span class="o">=</span> <span class="n">a</span> <span class="o">+</span> <span class="s">" "</span> <span class="o">+</span> <span class="n">b</span> -<span class="k">val</span> <span class="n">result</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">String</span><span class="o">](</span><span class="n">msgFun</span><span class="o">,</span> <span class="n">reduceFun</span><span class="o">)</span></code></pre></div> +<span class="k">val</span> <span class="n">result</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">String</span><span class="o">](</span><span class="n">msgFun</span><span class="o">,</span> <span class="n">reduceFun</span><span class="o">)</span></code></pre></figure> <p>can be rewritten using <code>aggregateMessages</code> as:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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">Int</span>, <span class="kt">Float</span><span class="o">]</span> <span class="k">=</span> <span class="o">...</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></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">Float</span><span class="o">]</span> <span class="k">=</span> <span class="o">...</span> <span class="k">def</span> <span class="n">msgFun</span><span class="o">(</span><span class="n">triplet</span><span class="k">:</span> <span class="kt">EdgeContext</span><span class="o">[</span><span class="kt">Int</span>, <span class="kt">Float</span>, <span class="kt">String</span><span class="o">])</span> <span class="o">{</span> <span class="n">triplet</span><span class="o">.</span><span class="n">sendToDst</span><span class="o">(</span><span class="s">"Hi"</span><span class="o">)</span> <span class="o">}</span> <span class="k">def</span> <span class="n">reduceFun</span><span class="o">(</span><span class="n">a</span><span class="k">:</span> <span class="kt">String</span><span class="o">,</span> <span class="n">b</span><span class="k">:</span> <span class="kt">String</span><span class="o">)</span><span class="k">:</span> <span class="kt">String</span> <span class="o">=</span> <span class="n">a</span> <span class="o">+</span> <span class="s">" "</span> <span class="o">+</span> <span class="n">b</span> -<span class="k">val</span> <span class="n">result</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">aggregateMessages</span><span class="o">[</span><span class="kt">String</span><span class="o">](</span><span class="n">msgFun</span><span class="o">,</span> <span class="n">reduceFun</span><span class="o">)</span></code></pre></div> +<span class="k">val</span> <span class="n">result</span> <span class="k">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">aggregateMessages</span><span class="o">[</span><span class="kt">String</span><span class="o">](</span><span class="n">msgFun</span><span class="o">,</span> <span class="n">reduceFun</span><span class="o">)</span></code></pre></figure> <h3 id="computing-degree-information">Computing Degree Information</h3> @@ -751,14 +751,14 @@ out-degree, and the total degree of each vertex. The <a href="api/scala/index. 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="language-scala" data-lang="scala"><span class="c1">// Define a reduce operation to compute the highest degree vertex</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">></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> +<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></figure> <h3 id="collecting-neighbors">Collecting Neighbors</h3> @@ -767,10 +767,10 @@ attributes at each vertex. This can be easily accomplished using the <a href="api/scala/index.html#org.apache.spark.graphx.GraphOps@collectNeighborIds(EdgeDirection):VertexRDD[Array[VertexId]]"><code>collectNeighborIds</code></a> and the <a href="api/scala/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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> +<span class="o">}</span></code></pre></figure> <blockquote> <p>These operators can be quite costly as they duplicate information and require @@ -813,7 +813,7 @@ messaging function. These constraints allow additional optimization within Grap <p>The following is the type signature of the <a href="api/scala/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="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> @@ -843,7 +843,7 @@ of its implementation (note calls to graph.cache have been removed):</p> <span class="o">}</span> <span class="n">g</span> <span class="o">}</span> -<span class="o">}</span></code></pre></div> +<span class="o">}</span></code></pre></figure> <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 @@ -854,7 +854,7 @@ second argument list contains the user defined functions for receiving messages <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><span class="k">import</span> <span class="nn">org.apache.spark.graphx.</span><span class="o">{</span><span class="nc">Graph</span><span class="o">,</span> <span class="nc">VertexId</span><span class="o">}</span> +<div class="highlight"><pre><span></span><span class="k">import</span> <span class="nn">org.apache.spark.graphx.</span><span class="o">{</span><span class="nc">Graph</span><span class="o">,</span> <span class="nc">VertexId</span><span class="o">}</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> @@ -885,14 +885,14 @@ shortest path in the following example.</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’s edges by default; instead, edges are left in their default partitions (such as their original blocks in HDFS). <a href="api/scala/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/scala/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="language-scala" data-lang="scala"><span class="k">object</span> <span class="nc">GraphLoader</span> <span class="o">{</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> +<span class="o">}</span></code></pre></figure> <p><a href="api/scala/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> @@ -904,7 +904,7 @@ shortest path in the following example.</p> <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 < dstId</code>), which is required by the <a href="api/scala/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="language-scala" data-lang="scala"><span class="k">object</span> <span class="nc">Graph</span> <span class="o">{</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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> @@ -920,7 +920,7 @@ shortest path in the following example.</p> <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> +<span class="o">}</span></code></pre></figure> <p><a href="api/scala/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> @@ -936,7 +936,7 @@ shortest path in the following example.</p> 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><a href="api/scala/index.html#org.apache.spark.graphx.VertexRDD">VertexRDD</a> and <code>EdgeRDD</code><a href="api/scala/index.html#org.apache.spark.graphx.EdgeRDD">EdgeRDD</a> respectively. In this section we review some of the additional useful functionality in these types. -Note that this is just an incomplete list, please refer to the API docs for the official list of operations.</p> +Note that this is just an incomplete list, please refer to the API docs for the official list of operations. </p> <h2 id="vertexrdds">VertexRDDs</h2> @@ -948,7 +948,7 @@ hash-map data-structure. As a consequence if two <code>VertexRDD</code>s are de evaluations. To leverage this indexed data structure, the <code>VertexRDD</code><a href="api/scala/index.html#org.apache.spark.graphx.VertexRDD">VertexRDD</a> exposes the following additional functionality:</p> -<div class="highlight"><pre><code class="language-scala" data-lang="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> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></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> @@ -963,7 +963,7 @@ additional functionality:</p> <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">=></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">=></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> +<span class="o">}</span></code></pre></figure> <p>Notice, for example, how the <code>filter</code> operator returns an <code>VertexRDD</code><a href="api/scala/index.html#org.apache.spark.graphx.VertexRDD">VertexRDD</a>. Filter is actually implemented using a <code>BitSet</code> thereby reusing the index and preserving the ability to do fast joins @@ -977,7 +977,7 @@ change the <code>VertexId</code> thereby enabling the same <code>HashMap</code> <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="language-scala" data-lang="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">=></span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="mi">1</span><span class="o">)))</span> +<figure class="highlight"><pre><code class="language-scala" data-lang="scala"><span></span><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">=></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">=></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> @@ -985
<TRUNCATED> --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@spark.apache.org For additional commands, e-mail: commits-h...@spark.apache.org
