2
\$\begingroup\$

I've just started to learn Scala and decided to implement small graph library to train.
Here is the basic version, that describes graph and nodes structure and also provides implementation of DFS to find some path from one node to other.

class Graph[A] {

  var nodes = Set.empty[Node[A]]

  def addNode(n: Node[A]) = nodes = nodes + n

  def DFS(from: Node[A], to: Node[A]): List[Node[A]] = {
    var visited = Set.empty[Node[A]]
    @tailrec
    def _DFS(from: Node[A], to: Node[A], path: List[Node[A]]): List[Node[A]] = {
      visited = visited + from
      if (from.equals(to)) path
      else {
        from.outgoing.find(n => !visited.contains(n)) match {
          case Some(n) => _DFS(n, to, n :: path)
          case None => path match {
            case n :: Nil => List.empty[Node[A]]
            case _ :: n :: ns => _DFS(n, to, n :: ns)
          }
        }
      }
    }
    _DFS(from, to, List(from)).reverse
  }

}

class Node[A](val i: A) {
  var incoming = Set.empty[Node[A]]
  var outgoing = Set.empty[Node[A]]

  def addIncoming(n: Node[A]) = incoming = incoming + n
  def addOutgoing(n: Node[A]) = outgoing = outgoing + n
}

I'm actively writing code in Java, so my primary goal is to not write Java code in Scala syntax. Hence, first and main question is: does my code looks like typical Scala code? If not, what should I change?

Next thing bothering me, is that my Node is too loosely coupled with Graph. I could invoke DFS only on instance of Graph, but apart from this, I don't really use Graph abstraction: I could just create instances of Node and link them.
That leads me to another problem. Suppose now I want to define weighted graph. For Graph itself I could define Weighted trait, but then I need to replace inner Node with NodeWithWeightedEdges, and I don't understand how.

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

One of the important traits of Scala is that it very well supports the functional programming, and of the advantages of functional programming is that is makes the reasoning of the functions easier. This is easier if the functions do not have side effects and if the used data structures are immutable.

Immutable data structures and pure functions are not always the best option, but in a graph library I thing they might be suitable.

So in your code I'd change the Graph to be an immutable class (see sample below).

Another problem with your code you have notices yourself. It is the strange coupling of the graph and the node classes. A graph is a structure that contains the nodes and the edges. In your code however the graph does not have any information about the edges itself, the nodes are responsible for holding the information about the edges. This could become problematic if you add only the node a to the graph and the node a has edges to other nodes, not known to the graph. Also, with the current design, you cannot reuse the same node object in multiple graphs. Also in your code there is no guarantee that when the node a has an outgoing edge to b that there is a corresponding edge on b incoming from a.

Here a sample of immutable classes for the Node and the Graph. Note that this structure is not optimal at all, as the information about the incoming and outgoing edges is not stored efficiently, but this can be done easily with some maps, depending on the algorithms you want to develop. Another note: The graph in my sample stores the nodes and the edges a bit redundantly. It would be enough to store just the edges, if isolated nodes are not needed.

case class Node[+T](i: T)

class Graph[N <: Node[T], +T](someNodes:Set[N], val edges:Set[(N,N)]) {

  // someNodes does not necessarily contains all nodes from the edges, nodes does
  val nodes: Set[N] = someNodes ++ edges.map(_._1) ++ edges.map(_._2)

  def addVortex(node:N) = new Graph(nodes + node, edges)

  def addEdge(edge: (N, N)) = new Graph(nodes + edge._1 + edge._2, edges + edge)

  // Redundant, but more efficient data structure for the outgoing edges
  lazy val outgoingEdges: Map[N, Set[N]] = edges.groupBy(_._1).mapValues(s => s.map(_._2))

  // Here come your algorithms
}
\$\endgroup\$
2
  • \$\begingroup\$ May I know what does N <: Node[T] mean? Thanks \$\endgroup\$ Commented Dec 7, 2016 at 10:38
  • \$\begingroup\$ N <: Node[T] means that N is a subclass of Node[T] \$\endgroup\$ Commented Dec 8, 2016 at 13:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.