[jira] [Updated] (SPARK-3650) Triangle Count handles reverse edges incorrectly

["Joseph E. Gonzalez (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-3650?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Joseph E. Gonzalez updated SPARK-3650:
--------------------------------------
    Description: 
The triangle count implementation assumes that edges are aligned in a canonical direction.  As stated in the documentation:

bq. Note that the input graph should have its edges in canonical direction (i.e. the `sourceId` less than `destId`)

However the TriangleCount algorithm does not verify that this condition holds and indeed even the unit tests exploits this functionality:

{code:scala}
val triangles = Array(0L -> 1L, 1L -> 2L, 2L -> 0L) ++
        Array(0L -> -1L, -1L -> -2L, -2L -> 0L)
      val rawEdges = sc.parallelize(triangles, 2)
      val graph = Graph.fromEdgeTuples(rawEdges, true).cache()
      val triangleCount = graph.triangleCount()
      val verts = triangleCount.vertices
      verts.collect().foreach { case (vid, count) =>
        if (vid == 0) {
          assert(count === 4)  // <-- Should be 2
        } else {
          assert(count === 2) // <-- Should be 1
        }
      }
{code}




  was:
The triangle count implementation assumes that edges are aligned in a canonical direction.  As stated in the documentation:

bq. Note that the input graph should have its edges in canonical direction (i.e. the `sourceId` less than `destId`)

However the TriangleCount algorithm does not verify that this condition holds and indeed even the unit tests exploits this functionality:

{code:scala}
val triangles = Array(0L -> 1L, 1L -> 2L, 2L -> 0L) ++
        Array(0L -> -1L, -1L -> -2L, -2L -> 0L)
      val rawEdges = sc.parallelize(triangles, 2)
      val graph = Graph.fromEdgeTuples(rawEdges, true).cache()
      val triangleCount = graph.triangleCount()
      val verts = triangleCount.vertices
      verts.collect().foreach { case (vid, count) =>
        if (vid == 0) {
          assert(count === 4)  // <-- Should be 2
        } else {
          assert(count === 2) // <-- Should be 1
        }
      }
{code:scala}





> Triangle Count handles reverse edges incorrectly
> ------------------------------------------------
>
>                 Key: SPARK-3650
>                 URL: https://issues.apache.org/jira/browse/SPARK-3650
>             Project: Spark
>          Issue Type: Bug
>          Components: GraphX
>    Affects Versions: 1.1.0
>            Reporter: Joseph E. Gonzalez
>
> The triangle count implementation assumes that edges are aligned in a canonical direction.  As stated in the documentation:
> bq. Note that the input graph should have its edges in canonical direction (i.e. the `sourceId` less than `destId`)
> However the TriangleCount algorithm does not verify that this condition holds and indeed even the unit tests exploits this functionality:
> {code:scala}
> val triangles = Array(0L -> 1L, 1L -> 2L, 2L -> 0L) ++
>         Array(0L -> -1L, -1L -> -2L, -2L -> 0L)
>       val rawEdges = sc.parallelize(triangles, 2)
>       val graph = Graph.fromEdgeTuples(rawEdges, true).cache()
>       val triangleCount = graph.triangleCount()
>       val verts = triangleCount.vertices
>       verts.collect().foreach { case (vid, count) =>
>         if (vid == 0) {
>           assert(count === 4)  // <-- Should be 2
>         } else {
>           assert(count === 2) // <-- Should be 1
>         }
>       }
> {code}



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org