Creating a type-safe DAG object

[Sam De Meyer]

Hi,

I attempted to make a type safe directed acyclic graph using the code below:

import scala.language.higherKinds
import scala.reflect.ClassTag
import scala.collection.mutable.Builder

import scalax.collection.GraphEdge._
import scalax.collection.GraphPredef._

import scalax.collection.constrained._
import scalax.collection.constrained.generic.GraphConstrainedCompanion
import scalax.collection.constrained.config.ConstrainedConfig
import scalax.collection.constrained.{Graph => CGraph, GraphLike => CGraphLike}
import scalax.collection.constrained.constraints.Acyclic


import scalax.collection.constrained.Graph
import scalax.collection.constrained.CompanionAlias
import scalax.collection.constrained.constraints.Acyclic

class CycleException(msg: String) extends IllegalArgumentException(msg)

/**
 * A strongly typed DAG that throws an exception on illegal edge addition.
 */
final class TypedDAG
  // Getting the types right here is black magic
  [ N
  , E[X] <: DiEdge[X]
  , +G[NN,EE[Y]<:EdgeLikeIn[Y]] <: CGraph[NN,EE] with CGraphLike[NN,EE,G] ]
  (graphCompanion: GraphConstrainedCompanion[G])
  (implicit edgeT: ClassTag[E[N]]) {

  protected object AcyclicConstrainedCompanion extends ConstraintCompanion[Constraint] {
    def apply[N0, E0[X] <: EdgeLikeIn[X]] (self: Graph[N0,E0]): Constraint[N0,E0] =
      new Acyclic(self.asInstanceOf[G[N,E]]){
        override def onAdditionRefused( refusedNodes: Traversable[N],
                                        refusedEdges: Traversable[E[N]],
                                        graph:        Graph[N,E]) =
        { throw new CycleException(
            "Addition refused: " +
            "nodes = " + refusedNodes.toString.take(64) + "... , " +
            "edges = " + refusedEdges.toString.take(64) + "..."
          )
        }
      }.asInstanceOf[Constraint[N0,E0]]
  }
  protected implicit val config: Config = AcyclicConstrainedCompanion.withStringPrefix("DAG")
 
  object DAG {
    def empty: G[N,E] = graphCompanion.empty
    def newBuilder: Builder[Param[N,E], G[N,E]] = graphCompanion.newBuilder
    def apply(elems: Param[N,E]*): G[N,E] = (newBuilder ++= elems).result
  }
}

object test_1 {
  val typedDAG = new TypedDAG[Int,DiEdge,Graph](Graph)
  import typedDAG.DAG
 
  val ga = DAG(1 ~> 2, 1 ~> 3, 2 ~> 4, 3 ~> 4)
  println(ga)
  println(ga.get(1).pathTo(ga.get(4)))
  // This works!
  // DAG(1 ~> 2, 1 ~> 3, 2 ~> 4, 3 ~> 4)
  // Some(Path(1, 1~>2, 2, 2~>4, 4))

  def foo(g: DAG[Int]): Unit = ()
  foo(DAG(1 ~> 2))

  // Perfect!
  //val gb = DAG(1.0 ~> 2.0) // type mismatch; found: Double(2.0)   required: Int
  //val gc = DAG(1 ~ 2)      // type mismatch; found: UnDiEdge[Int] required: Param[Int,DiEdge]
 
  // Throws a CycleException, excellent!
  val gd = DAG(1 ~> 2, 2 ~> 1)
}

object test_2 {
  import scalax.collection.edge.LDiEdge
  val typedDAG = new TypedDAG[Int,LDiEdge,Graph](Graph)
  import typedDAG.DAG
 
// Nooooooo!
// DAG.scala:79: type arguments [Int,scalax.collection.edge.LDiEdge,scalax.collection.constrained.Graph] do not conform to class TypedDAG's type parameter bounds [N,E[X] <: scalax.collection.GraphEdge.DiEdge[X],+G[NN, EE[Y] <: scalax.collection.GraphPredef.EdgeLikeIn[Y]] <: scalax.collection.constrained.Graph[NN,EE] with scalax.collection.constrained.GraphLike[NN,EE,G]]
//   val typedDAG = new TypedDAG[Int,LDiEdge,Graph](Graph)
//       ^
// /home/samey/Local/pingov2/sbtfiddle/src/main/scala/fiddle/graphs/GoDAG.scala:79: type arguments [Int,scalax.collection.edge.LDiEdge,scalax.collection.constrained.Graph] do not conform to class TypedDAG's type parameter bounds [N,E[X] <: scalax.collection.GraphEdge.DiEdge[X],+G[NN, EE[Y] <: scalax.collection.GraphPredef.EdgeLikeIn[Y]] <: scalax.collection.constrained.Graph[NN,EE] with scalax.collection.constrained.GraphLike[NN,EE,G]]
//   val typedDAG = new TypedDAG[Int,LDiEdge,Graph](Graph)
//                      ^
}

This with some help from this post: https://groups.google.com/forum/?fromgroups#!searchin/scala-graph/DAG|sort:relevance/scala-graph/TK2uZbY-mRM/TwFeg-vgCAAJ

It seems to work fine for plain undirected edges (see test_1 in the code above), but it fails on labelled undirected edges. This surprises me since looking at the class hierarchy diagram in http://www.scala-graph.org/guides/core-initializing.html I would think that a labelled directed edge is a subtype of a plain directed edge.

So my question is, what do I need to do in order to have a general purpose type-safe DAG that works with all kinds of directed edges?

If at all possible, I would like to express in my function signature the requirement for a DAG with some edge type 'E1' and node some node type 'N1', such that in the body of the function I have 100% certainty that the graph is acyclic, directed, has edges of type 'E1' and nodes of type 'N1'. As a bonus, a type-safe edge label would also be nice.

By the way, if I am asking for too much, please tell me. The above will be good enough for my use case. And I could get around the label issue by implementing my own edge class with some field that acts as a label. I am just curious if it is at all possible.
Also, I'm quite new to scala, so if the solution is obvious and I don't see it please forgive me :)

Thanks in advance for your help.

For the sake of being complete, here are the versions I'm using:

scalaVersion := "2.12.2"
libraryDependencies += "org.scala-graph" %% "graph-core" % "1.11.5",
libraryDependencies += "org.scala-graph" %% "graph-constrained" % "1.11.0",

[Peter Empen]

Hi Sam,

unfortunately, the inheritance diagram turns out to be outdated: LDiEdge does not inherit from DiEdge but from DiEdgeLike.
The next surprise could be that replacing the upper bound of the type parameter E in TypedDAG by DiEdgeLikeIn (a slightly other type that is defined for such situations) won't help in this special case, either.
So, as you suspect, your friend is a custom edge extending DiEdge.

I think the root cause is that class Acyclic's E[X] has the upper bound EdgeLikeIn[X]. On one hand, this is meaningful because Graph for Scala allows for cycles in mixed graphs, too. On the other hand, it is annoying in your case. What about playing with a modified Acyclic having the upper bound DiEdgeLikeIn[X] instead?

Last, type-safe edge labeles at graph level would require to add a label type parameter to Graph, a possible but rather expensive undertaking.

Peter

[Sam De Meyer]

Dear Peter,

Thank you for your reply.
By playing with `Acyclic` with an Upper bound `DiEdgeLike`, do you mean anything like this?

object BuildDAG {  
  import scala.language.higherKinds

  import scala.reflect.ClassTag
  import scala.collection.Set
  import scala.collection.mutable.Builder

  import scalax.collection.GraphPredef.{EdgeLikeIn, DiEdgeLikeIn, Param}
  import scalax.collection.constrained.{Graph => CGraph, GraphLike => CGraphLike,
    ConstraintCompanion, Constraint, Config}
  import scalax.collection.constrained.generic.GraphConstrainedCompanion

  import scalax.collection.constrained.constraints.Acyclic

  class CycleException(msg: String) extends IllegalArgumentException(msg)

  class DAcyclic
    [ N
    , E[X] <: DiEdgeLikeIn[X] ]
    (override val self: CGraph[N,E])
    extends Acyclic[N, E](self)

  {
    override def onAdditionRefused( refusedNodes: Traversable[N],
                                    refusedEdges: Traversable[E[N]],

                                    graph:        CGraph[N,E]) =

    { throw new CycleException(
        "Addition refused: " +
        "nodes = " + refusedNodes.toString.take(64) + "... , " +
        "edges = " + refusedEdges.toString.take(64) + "..."
      )
    }
  }

  class TypedDAG

    // Getting the types right here is black magic
    [

N
    , E[X] <: DiEdgeLikeIn[X]

    , +G[NN,EE[Y]<:EdgeLikeIn[Y]] <: CGraph[NN,EE] with CGraphLike[NN,EE,G] ]
    (graphCompanion: GraphConstrainedCompanion[G])
    (implicit edgeT: ClassTag[E[N]])
  {

   
    protected object DAcyclicConstrainedCompanion
      extends ConstraintCompanion[Constraint]
    {
      def apply[N0, E0[X] <: EdgeLikeIn[X]] (self: CGraph[N0,E0]): Constraint[N0,E0] =
        new DAcyclic(self.asInstanceOf[G[N,E]]).asInstanceOf[Constraint[N0,E0]]
    }

    protected implicit val config: Config = DAcyclicConstrainedCompanion.withStringPrefix("DAG")

 
    object DAG {
      def empty: G[N,E] = graphCompanion.empty
      def newBuilder: Builder[Param[N,E], G[N,E]] = graphCompanion.newBuilder
      def apply(elems: Param[N,E]*): G[N,E] = (newBuilder ++= elems).result
    }
   
  }

}

Also, I might be wrong here, but could it be that `LDiEdge` is not at all a subtype of `DiEdgeLikeIn`? For example:

import scalax.collection.GraphEdge._
import scalax.collection.GraphPredef._
import scalax.collection.edge.LDiEdge
import scala.language.higherKinds

def foo[N, E[N] <: DiEdgeLikeIn[N]](e: E[N]) = e
val e1:DiEdge[Int] = DiEdge(1,2)
foo(DiEdge(1,2))  // Ok
val e2:LDiEdge[Int] = LDiEdge(1,2)("foo")
//foo(e2) // Not ok, type error

In addition, I noticed that the `DAG[N]` type in the `test_1.foo` function argument of my previous post is just an alias for `Graph[N,DiEdge]`, which means it easy to create a graph with cycles that conforms to `DAG[N]`. I was wondering if it is somehow possible to define a type such that only graphs created by the `DAG` object of a `TypedDAG` are accepted. E.g. something along the lines of:

def bar(g: DAG[Int, DiEdge]):Unit = ()

[Peter Empen]

Sam,

as told, your friend is a custom edge extending DiEdge. For instance, Flight.scala works out of the box.

Yes, those edges defined in

package scalax.collection.edge are special cases thus not complying to DiEdgeLike. So I'd discourage you from investigating into any generic solution covering LDiEdge.

Conceringn DAG[N], good catch! Being just a type alias, it is kinda type leakage. I'll examine how to make it type-safe.

Peter