class MaximalIndependentSet extends Serializable with WithIntermediateStorageLevel with WithCheckpointInterval with WithLocalCheckpoints

This class implements a distributed algorithm for finding a Maximal Independent Set (MIS) in a graph.

An MIS is a set of vertices such that no two vertices in the set are adjacent (i.e., there is no edge between any two vertices in the set), and the set is maximal, meaning that adding any other vertex to the set would violate the independence property. Note that this implementation finds a maximal (but not necessarily maximum) independent set; that is, it ensures no more vertices can be added to the set, but does not guarantee that the set has the largest possible number of vertices among all possible independent sets in the graph.

The algorithm implemented here is based on the paper: Ghaffari, Mohsen. "An improved distributed algorithm for maximal independent set." Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2016.

Note: This is a randomized, non-deterministic algorithm. The result may vary between runs even if a fixed random seed is provided because how Apache Spark works.

Linear Supertypes
WithLocalCheckpoints, WithCheckpointInterval, WithIntermediateStorageLevel, Logging, Serializable, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. MaximalIndependentSet
  2. WithLocalCheckpoints
  3. WithCheckpointInterval
  4. WithIntermediateStorageLevel
  5. Logging
  6. Serializable
  7. AnyRef
  8. Any
Implicitly
  1. by any2stringadd
  2. by StringFormat
  3. by Ensuring
  4. by ArrowAssoc
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. def +(other: String): String
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toany2stringadd[MaximalIndependentSet] performed by method any2stringadd in scala.Predef.
    Definition Classes
    any2stringadd
  4. def ->[B](y: B): (MaximalIndependentSet, B)
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toArrowAssoc[MaximalIndependentSet] performed by method ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc
    Annotations
    @inline()
  5. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  6. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  7. val checkpointInterval: Int
    Attributes
    protected
    Definition Classes
    WithCheckpointInterval
  8. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @IntrinsicCandidate() @native()
  9. def ensuring(cond: (MaximalIndependentSet) => Boolean, msg: => Any): MaximalIndependentSet
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toEnsuring[MaximalIndependentSet] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  10. def ensuring(cond: (MaximalIndependentSet) => Boolean): MaximalIndependentSet
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toEnsuring[MaximalIndependentSet] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  11. def ensuring(cond: Boolean, msg: => Any): MaximalIndependentSet
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toEnsuring[MaximalIndependentSet] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  12. def ensuring(cond: Boolean): MaximalIndependentSet
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toEnsuring[MaximalIndependentSet] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  13. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  14. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  15. def getCheckpointInterval: Int

    Gets checkpoint interval.

    Gets checkpoint interval.

    Definition Classes
    WithCheckpointInterval
  16. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @IntrinsicCandidate() @native()
  17. def getIntermediateStorageLevel: StorageLevel

    Gets storage level for intermediate datasets that require multiple passes.

    Gets storage level for intermediate datasets that require multiple passes.

    Definition Classes
    WithIntermediateStorageLevel
  18. def getUseLocalCheckpoints: Boolean

    Gets whether local checkpoints are being used instead of regular checkpoints.

    Gets whether local checkpoints are being used instead of regular checkpoints.

    returns

    true if local checkpoints are enabled, false otherwise

    Definition Classes
    WithLocalCheckpoints
  19. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @IntrinsicCandidate() @native()
  20. val intermediateStorageLevel: StorageLevel
    Attributes
    protected
    Definition Classes
    WithIntermediateStorageLevel
  21. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  22. def logDebug(s: => String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  23. def logInfo(s: => String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  24. def logTrace(s: => String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  25. def logWarn(s: => String): Unit
    Attributes
    protected
    Definition Classes
    Logging
  26. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  27. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @IntrinsicCandidate() @native()
  28. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @IntrinsicCandidate() @native()
  29. def resultIsPersistent(): Unit
    Attributes
    protected
    Definition Classes
    Logging
  30. def run(seed: Long): DataFrame
  31. def setCheckpointInterval(value: Int): MaximalIndependentSet.this.type

    Sets checkpoint interval in terms of number of iterations (default: 2).

    Sets checkpoint interval in terms of number of iterations (default: 2). Checkpointing regularly helps recover from failures, clean shuffle files, shorten the lineage of the computation graph, and reduce the complexity of plan optimization. As of Spark 2.0, the complexity of plan optimization would grow exponentially without checkpointing. Hence, disabling or setting longer-than-default checkpoint intervals are not recommended. Checkpoint data is saved under org.apache.spark.SparkContext.getCheckpointDir with prefix of the algorithm name. If the checkpoint directory is not set, this throws a java.io.IOException. Set a nonpositive value to disable checkpointing. This parameter is only used when the algorithm is set to "graphframes". Its default value might change in the future.

    Definition Classes
    WithCheckpointInterval
    See also

    org.apache.spark.SparkContext.setCheckpointDir in Spark API doc

  32. def setIntermediateStorageLevel(value: StorageLevel): MaximalIndependentSet.this.type

    Sets storage level for intermediate datasets that require multiple passes (default: MEMORY_AND_DISK).

    Sets storage level for intermediate datasets that require multiple passes (default: MEMORY_AND_DISK).

    Definition Classes
    WithIntermediateStorageLevel
  33. def setUseLocalCheckpoints(value: Boolean): MaximalIndependentSet.this.type

    Sets whether to use local checkpoints instead of regular checkpoints (default: false).

    Sets whether to use local checkpoints instead of regular checkpoints (default: false). Local checkpoints are faster but less reliable as they don't survive node failures.

    value

    true to use local checkpoints, false for regular checkpoints

    returns

    this instance

    Definition Classes
    WithLocalCheckpoints
  34. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  35. def toString(): String
    Definition Classes
    AnyRef → Any
  36. val useLocalCheckpoints: Boolean
    Attributes
    protected
    Definition Classes
    WithLocalCheckpoints
  37. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  38. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  39. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated
    Deprecated

    (Since version 9)

  2. def formatted(fmtstr: String): String
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toStringFormat[MaximalIndependentSet] performed by method StringFormat in scala.Predef.
    Definition Classes
    StringFormat
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.12.16) Use formatString.format(value) instead of value.formatted(formatString), or use the f"" string interpolator. In Java 15 and later, formatted resolves to the new method in String which has reversed parameters.

  3. def →[B](y: B): (MaximalIndependentSet, B)
    Implicit
    This member is added by an implicit conversion from MaximalIndependentSet toArrowAssoc[MaximalIndependentSet] performed by method ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Use -> instead. If you still wish to display it as one character, consider using a font with programming ligatures such as Fira Code.

Inherited from WithLocalCheckpoints

Inherited from WithCheckpointInterval

Inherited from WithIntermediateStorageLevel

Inherited from Logging

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Inherited by implicit conversion any2stringadd fromMaximalIndependentSet to any2stringadd[MaximalIndependentSet]

Inherited by implicit conversion StringFormat fromMaximalIndependentSet to StringFormat[MaximalIndependentSet]

Inherited by implicit conversion Ensuring fromMaximalIndependentSet to Ensuring[MaximalIndependentSet]

Inherited by implicit conversion ArrowAssoc fromMaximalIndependentSet to ArrowAssoc[MaximalIndependentSet]

Ungrouped