Traverse and Modify an Heterogeneous Directed Acyclic Graph in Scala
Good morning everybody.
I have the following directed acyclic graph data structure, implemented in Scala as follows:
abstract class Node // Generic abstract node
/** Various kind of leaf nodes */
case class LeafNodeA(x: String) extends Node
case class LeafNodeB(x: Int) extends Node
/** Various kind of inner nodes */
case class InnerNode1(x: String, depRoleA: Node) extends Node
case class InnerNode2(x: String, y: Double, depRoleX: Node, depRoleY: Node) extends Node
case class InnerNode3(x: List[Int], depRoleA: Node, y: Int,
depRoleB: Node, depRoleG: Node) extends Node
In this structure a node can be a dependency of multiple nodes, therefore it is not a Tree but a Directed Acyclic Graph. In addition the structure is not even balanced (nodes have different numbers of dependencies).
The problem of traversal
Notice that I have called the various dependency fields of the case classes with different names since they represents different roles in the dependencies (for example, depRoleX
has a different role than depRoleY
in an InnerNode2
type node). For this reason I don't think it is possible to store the dependencies of each node in a List[Node]
like in any trivial tree/dag implementation you can find out there, because the meaning of each dependency field is different.
Of course when I traverse this structure I have to do pattern matching in order to understand the type of node I am dealing with at the current recursion step:
// Random function which returns the list of all the String attributes of the nodes
def getAllStrings(dag: Node): List[String] = {
dag match {
case LeafNodeA(x) => List(x)
case LeafNodeB => List()
case InnerNode1(x, dr) => List(x) ::: getAllStrings(dr)
case InnerNode2(x, _, dX, dY) => List(x) ::: getAllStrings(dX) :: getAllStrings(dY)
case InnerNode3(_, dA, _, dB, dG) => getAllStrings(dA) ::: getAllStrings(dB) ::: getAllStrings(dG)
}
}
Now suppose that instead of these 5 relatively simple node types I have around 20 types of node. The previous function would become extremely long and repetitive (a case
statement for each node type). Even worse: every time I want to do a traversal I have to do the same thing.
Thinking about this problem I came up with two solutions.
External method for traversal
The first (obvious) way to deal with this is to modularize the previous method defining a generic DAG traversal function
object DAGManipulator {
def getDependencies(dag: Node): List[Node] = {
dag match {
case LeafNodeA => List()
case LeafNodeB => List()
case InnerNode1(_, dr) => List(dr)
case InnerNode2(_, _, dX, dY) => List(dX, dY)
case InnerNode3(_, dA, _, dB, dG) => List(dA, dB, dG)
}
}
}
In this way, every time I need the dependencies of a node I can rely on this static function.
Abstract class method for getting the dependencies
The second solution I came up with is to give to every node an additional method in the following way:
abstract class Node {
def getDependencies : List[Node]
}
case class LeafNodeA(x: String) extends Node = {
override def getDependencies : List[Node] = List()
}
case class LeafNodeB(x: Int) extends Node = {
override def getDependencies : List[Node] = List()
}
/** Various kind of inner nodes */
case class InnerNode1(x: String, depRoleA: Node) extends Node = {
override def getDependencies : List[Node] = List()
}
case class InnerNode2(x: String, y: Double, depRoleX: Node, depRoleY: Node) extends Node = {
override def getDependencies : List[Node] = List(depRoleX, depRoleY)
}
case class InnerNode3(x: List[Int], depRoleA: Node, y: Int,
depRoleB: Node, depRoleG: Node) extends Node = {
override def getDependencies : List[Node] = List(depRoleA, depRoleB, depRoleG)
}
I don't like any of the previous solutions:
The first one must be updated every time a new node type is added to the hierarchy. In addition to this, it delegates a fundamental feature of the DAG structure (traversal) to an external object, which I find very unpleasant from the software engineering point of view.
The second solution in my opinion is even worse because every node type basically has to redundantly state its dependencies (once in its fields and once in the
getDependencies
method. I find this very ugly and prone to programming errors.
Do you have a better solution to this problem ?
The problem of updating
The second problem I have to deal with is the updating/modification of the data structure.
Suppose that I have a DAG defined in the following way.
val l1 = LeafNodeB(1)
val dag =
InnerNode3(List(1, 2, 3),
InnerNode1("InnerNode1", LeafNodeA("leafA1")),
1, l1, InnerNode2("InnerNode2", 2, l1, LeafNodeA("leafA2")))
corresponding to this structure.
Suppose that I want to change the LeafNodeA("leafA1")
(which is a dependency of the InnerNode1
) to, for example, l1
, which is a LeafNodeB
.
This is the kind of operation that I need to do:
def modify(dag: Node): Node = {
dag match {
case x: InnerNode1 => if(x.x == "InnerNode1") x.copy(depRoleA = l1) else x
case x: LeafNodeB => x
case x: LeafNodeA => x
case x: InnerNode2 => x.copy(depRoleX = modify(x.depRoleX), depRoleY = modify(x.depRoleY))
case x: InnerNode3 => x.copy(depRoleA = modify(x.depRoleA), depRoleB = modify(x.depRoleB), depRoleG = modify(x.depRoleG))
}
}
Again, consider the possibility of having more than 20 node types...Again this update method would become not practical, and this counts for every other possible update method that I can think of.
In addition to this...this time I did not come up with a different strategy for factorizing/modularize this "recursive traversal update" of the nested structure. I have to check for every possible node type in order to understand how to use the copy
method of the various case classes.
Do you have a better solution / design for this update strategy ?
getAllStrings
looks like you are implementingTraverse
for the specific case of anApplicative
generated from(List, :::, Nil)
-monoid. – Andrey Tyukin Jul 30 '18 at 11:46