Graph traversals are explicitly or implicitly invoked by means of a
Traverser
that extends scala.collection.Traversable
in turn. You determine the
type parameter of Traversable
by selecting a Traverser
factory
method such as innerNodeTraverser
.
Needless to say, all methods relying on recursion are tail recursive.
Often you are solely interested in the result of a graph traversal such as
a specific node, a path, cycle or subgraph rather than tracking the visited elements.
Chances are good that you'll find a method that directly your requirement
and that a Traverser
will be provided transparently for you.
import scalax.collection.edge.WDiEdge import scalax.collection.edge.Implicits._ val g = Graph(1~2 % 4, 2~3 % 2, 1~>3 % 5, 1~5 % 3, 3~5 % 2, 3~4 % 1, 4~>4 % 1, 4~>5 % 0) def n(outer: Int): g.NodeT = g get outer // look up 'outer' that is known to be contained n(1) findSuccessor (_.outDegree > 3) // Option[g.NodeT] = None n(1) findSuccessor (_.outDegree >= 3) // Option[g.NodeT] = Some(3) n(4) findSuccessor (_.edges forall (_.undirected)) // Some(2) n(4) isPredecessorOf n(1) // true n(1) pathTo n(4) // Some(Path(1, 1~>3 %5, 3, 3~4 %1, 4)) n(1) pathUntil (_.outDegree >= 3) // Some(Path(1, 1~>3 %5, 3)) val spO = n(3) shortestPathTo n(1) // Path(3, 3~4 %1, 4, 4~>5 %0, 5, 1~5 %3, 1) val sp = spO.get // here we know spO is defined sp.nodes // List[g.NodeT] = Nodes(3, 4, 5, 1) sp.weight // Double = 4.0 def negWeight(e: g.EdgeT): Float = 5.5f  e.weight val spNO = n(3) shortestPathTo (n(1), negWeight) // Path(3, 2~3 %2, 2, 1~2 %4, 1) val spN = spNO.get // here we know spNO is defined spN.weight // Double = 6.0 val pO1 = n(4).withSubgraph(nodes = _ < 4) pathTo n(2) // Some(Path(4, 3~4 %1, 3, 2~3 %2, 2)) pO1.map(_.nodes) // Some(Nodes(4, 3, 2)) val pO2 = n(4).withSubgraph(edges = _.weight != 2) pathTo n(2) // Some(Path(4, 4~>5 %0, 5, 1~5 %3, 1, 1~2 %4, 2)) pO2.map(_.nodes) // Some(Nodes(4, 5, 1, 2))
As to
1
having outDegree > 3
and finds None
.
1
having outDegree
>= 3
and finds node 3
. This also means that there
exists a path from node 1
to node 3
. To get the full
path call findPath
.
4
having only
undirected edges and finds node 2
.
4
being a predecessor
of node 1
.
1
to node 4
.
1
to an arbitrary node having
outDegree >= 3
.
3
to node
1
and get
s the result from Option
.
Calling get
is okay in this example because we know that
there must exist a path.
p
to the List of nodes on the path.
The returned path is an instance of the inner class Path
facilitating further functionality...
weight
to calculate the
total of the edge weights on this path.
float
to demonstrate that the weight method
may be of any numeric type.
shortestPathTo
with the custom weight method
negWeight
. The returned path is the longest one in terms of
static edge weights as 5.5f
exceeds the maximum static weight.
4
to node 2
restricting the traversal to a subgraph containing only nodes with value
less than 4
.
4
to node 2
restricting the traversal to a subgraph containing only edges with weight
of 2
.
val g = Graph(1~>2, 1~>3, 2~>3, 3~>4, 4~>2) val fc1 = g.findCycle // Some(Cycle(3, 3~>4, 4, 4~>2, 2, 2~>3, 3)) val fc2 = (g get 4).findCycle // Some(Cycle(4, 4~>2, 2, 2~>3, 3, 3~>4, 4)) for (c1 < fc1; c2 < fc2) yield c1 == c2 // false for (c1 < fc1; c2 < fc2) yield c1 sameAs c2 // true g.findCycleContaining(g get 1) // None
As to
g
, if any.
4
,
if any.
c1
and c2
are not equal because they
start at different nodes.
c1
and c2
depict the same cycle in a semantic sense.
1
.
Cycle detecting works for directed, undirected and mixed graphs, alike.
If you have to ensure that your Graph
instance is acyclic on
any operation consider utilizing the Acyclic
constraint in
the Constrained module.
Except for withSubgraph
, we did not make use of properties in the above examples.
Properties, all prefixed by with
, encourage a fluent way of method calls,
hence we refer to them as fluent properties.
You may refine any Traverser
by means of the following properties:
Property  Factory method  Sample Value  Described at 
kind: Kind 
withKind 
DepthFirst 
members of Parameters

direction: Direction 
withDirection 
Successors 
members of Parameters

maxDepth: Int 
withMaxDepth 
30 
members of Parameters

maxWeight: MaxWeight 
withMaxWeight 
125.3 
members of FluentProperties
andsubclasses of Properties

nodes: (NodeT) => Boolean, 
withSubgraph 
_.inDegree < 10 
members of FluentProperties
andsubclasses of Properties

ordering: GraphTraversal.ElemOrdering 
withOrdering 
myOrdering 
members of FluentProperties
andsubclasses of ElemOrdering

For instance, to exclude a specific node from the traversal in a lazy manner
you'd call withSubgraph
like
(g get 1).withSubgraph(nodes = _ != 2) pathTo (g get 4)
For more examples on how to make use of properties search for the above factory methods in TTraversal.scala
As a special case, assume you want to control the order of edges to be traversed.
You can do so by setting the ordering
property.
Since ordering has been tricky in general let's look at an example ensuring that
edges are traversed in reverse order of their weights:
import edge.WDiEdge val root = 1 val g = Graph(root~>4 % 2, root~>2 % 5, root~>3 % 4, 3~>6 % 4, 3~>5 % 5, 3~>7 % 2) def edgeOrdering = g.EdgeOrdering(g.Edge.WeightOrdering.reverse.compare) val traverser = (g get root).outerNodeTraverser.withOrdering(edgeOrdering) traverser.toList // List(1,2,3,4,5,6,7)
Note that node and edge ordering are limited compared with a priority queue.
Traverser
s also enable to inspect graph elements (nodes and/or edges)
during the traversal. By doing so they ensure that the passed visitor method is called
once for each visited element. As a side note, DownUpTraverser
s are
different in that they call the visitor twice.
Depending on what graph elements you're interested in, select one of the following
Traverser
factory methods:
Factory Method  Type of Visitor 
innerNodeTraverser 
path dependent NodeT

outerNodeTraverser 
N type parameter of the graph 
innerEdgeTraverser 
path dependent EdgeT

outerEdgeTraverser 
E[N] based on the type parameters of the graph 
innerElemTraverser 
InnerElem , the common base of NodeT and EdgeT

outerElemTraverser 
OuterElem[N,E] , the common base of N and E[N]

innerNodeDownUpTraverser 
(Boolean, NodeT) 
outerNodeDownUpTraverser 
(Boolean, N) 
While inner elements provide graph functionality at your fingertips, outer elements feel more natural since they're exactly what you passed to the graph.
The above factory methods are available both at node and graph level. At node level
root
, the node to start the traversal at, is set to the specific node
you are invoking the method on; at graph level root
must be passed explicitly.
In addition you may pass any traverser property to override the default values:
import scalax.collection.edge.WDiEdge import scalax.collection.edge.Implicits._ val g = Graph(1~>2 % 1, 1~>3 % 2, 2~>3 % 3, 3~>4 % 1) val n1 = g get 1 n1.outerNodeTraverser.sum // 10 g.outerNodeTraverser(n1).sum // 10 n1.outerNodeTraverser.withMaxDepth(1).sum // 6 n1.innerEdgeTraverser.map(_.weight).sum // 7.0 n1.innerElemTraverser.filter(_ match { case g.InnerNode(n) => n.degree > 1 case g.InnerEdge(e) => e.weight > 1 }) // Traversable(1, 2, 3, 1~>3 % 2, 2~>3 % 3)
As to
n1
to sum up the node values.
sum
is provided by scala.colllection.Traversable
.
outerEdgeTraverser
as well.
g
for all its elements reachable from
n1
to return a set of InnerElem
containing nodes
with a degree greater than 2
and edges with a weight greater
than 1
.
Assume you'd like to traverse a graph, especially a tree, in a
stacklike manner i.e. you need to carry out one action when touching
a node the first time and another, related action when touching the
same node the second time in course of traversing up in the imaginary tree.
For this purpose you may utilize innerNodeDownUpTraverser
:
import scala.collection.mutable.ArrayBuffer val root = "A" val g = Graph(root~>"B1", root~>"B2") val innerRoot = g get root val result = (ArrayBuffer.empty[String] /: innerRoot.innerNodeDownUpTraverser) { (buf, param) => param match { case (down, node) => if (down) buf += (if (node eq innerRoot) "(" else "[") += node.toString else buf += (if (node eq innerRoot) ")" else "]") } } ("" /: result)(_+_) // "(A[B1][B2])"
In case you need to process the internal state of a traversal including the count of visited nodes, the current search depth, the internal stack etc. you may switch to extended visitors. Beware that these are implementation specific:
val g = Graph(1~>2, 1~>3, 2~>3, 3~>4, 4~>2) import g.ExtendedNodeVisitor import scalax.collection.GraphTraversal._ import scalax.collection.GraphTraversalImpl._ type ValDepth = (Int,Int) var info = List.empty[ValDepth] (g get 1).innerNodeTraverser.withKind(DepthFirst).foreach { ExtendedNodeVisitor((node, count, depth, informer) => { info :+= (node.value, depth) }) } info.sortWith((a: ValDepth, b: ValDepth) => a._1 < b._1  a._1 == b._1 && a._2 < b._2) // info = List((1,0), (2,1), (3,1), (4,2))
Further, when traversing for a result, it is also possible to append a visitor for additional side effects like:
val g = Graph(1~>2, 1~>3, 2~>3, 3~>4, 4~>2) var center: Option[g.NodeT] = None (g get 4).findCycle( n => center = center match { case s @ Some(c) => if (n.degree > c.degree) Some(n) else s case None => Some(n) } )
The above expression evaluates to an Option[Path]
.
In course of the traversal the appended visitor also calculates the node
with the maximum degree among those visited. The resulting center
need not be part of the cycle.
You may search for weakly or strongly connected components. In both cases you first need to decide on where the computation should start:
val componentEdges = { def edges(i: Int) = List(i ~> (i + 1), i ~> (i + 2), (i + 1) ~> (i + 2)) (edges(1), edges(5)) } val disconnected = Graph.from(edges = componentEdges._1 ++ componentEdges._2) val sums = for (component < disconnected.componentTraverser()) yield (0 /: component.nodes)((cum, n) => cum + n.toOuter) // List(6, 18)
As to
sums
correspond to the sums of the integer node values
in both components.
Here is how to search for the weak comopnent containing a specific node:
val anyNode = disconnected.nodes.draw(new util.Random) anyNode.weakComponent.nodes // componentEdges._1.size = 3
Strongly connected components are computed based on a tailrecursive version of Tarjan's algorithm.
Let us refer to the sample graph on Wikipedia:
val sccExpected = ( Graph('a ~> 'b, 'b ~> 'c, 'c ~> 'd, 'd ~> 'a, 'd ~> 'e, 'c ~> 'e, 'e ~> 'c), Graph('f ~> 'g, 'g ~> 'f, 'g ~> 'h, 'h ~> 'j, 'j ~> 'i, 'i ~> 'g, 'i ~> 'f, 'f ~> 'i) ) val connected = (sccExpected._1 union sccExpected._2) + 'e ~> 'f val scc = connected.strongComponentTraverser().map(_.toGraph) scc.toSet == Set(sccExpected._1, sccExpected._2) // true
As to
To limit the scope of the search to nodes reachable from a give node, start the search at that node like
val startAt = sccExpected._2.nodes.head startAt.strongComponents.size // 1 startAt.innerNodeTraverser.strongComponents(println)
As to
Component
What about the type returned by a component search?
Component
is a strict set of the contained nodes
and a lazy set of the contained edges
.
Further you may invoke toGraph
on a component.
Graph for Scala comes with three flavors of topological sorting
along with a remarkably informative result type.
For the following examples, assume graph
is a value of type Graph
and root
is a value of type graph.NodeT
.
As a matter of course you can call topologicalSort
directly on your graph instance:
graph.topologicalSort.fold( cycleNode => ???, order => ??? )
The result is of type CycleNodeOrTopologicalOrder
,
a type alias for Either[NodeT, TopologicalOrder[NodeT]]
.
Left
will wrap an inner node being on a cycle in case there exists no topological order.
On success, Right
contains the calculated TopologicalOrder
.
When called at graph level, this will include nodes irrespective of
whether they are connected or they are members of different components.
Calling componentTraverser
first, you may combine topologicalSort
with any of the familiar fluent properties like
graph.componentTraverser().withSubgraph(nodes = myNodeFilter).topologicalSort
Whenever starting at a concrete inner node, topologicalSort()
will only include
nodes within the comopnent spanned by the given node.
In reverse, if you know your graph is connected you need not call TopologicalOrder
at node level. It suffices to call it at graph level.
Note that nodelevel topologicalSort()
also has a boolean argument
allowing you to exclude predecessors from the result. Therefore you need to place the paranthesis:
root.topologicalSort()
Further, if you are interested in the topological order of the components of your graph, simply call
graph.componentTraverser().topologicalSortByComponent
that yiels a Traversable[CycleNodeOrTopologicalOrder]
one for each component.
TopologicalOrder
TopologicalOrder
is more than just a list of nodes. Most interestingly,
you can call toLayered to lift this result type into a layered representation of the topological order:
graph.topologicalSort.fold( cycleNode => yourCycleErrorHandler, _.toLayered foreach println // prints topo order layer by layer )
The layers of a topological sort can roughly be defined as follows:
Among others, layers are usefull to
To cancel a traversal prefer calling one of scala.collection.Traversable
's
methods that finish the traversal as soon as the specified condition holds true such as
exists
or collectFirst
.
Otherwise you are free to invoke break()
as provided by
scala.util.control.Breaks
at any point.
WalkBuilder and
PathBuilder
allow to build a
Walk respectively
Path
in terms of the underlying graph.
This proves usefull whenever you have some results computed outside the library and
would like to represent them by Graph for Scala pathdependent types.
Since WalkBuilder
and PathBuilder
enforce proper walk/path
semantics they are also well suited for testing usercomputed paths.
Let's look at how to create a path in the sample graph g
by means of a PathBuilder
:
val builder = g.newPathBuilder(n(1)) builder += n(3) += n(4) builder.result // Path(1, 1~>3 %5, 3, 3~4 %1, 4) builder.clear builder += n(4) += n(3) builder.result // Path(1, 1~>3 %5, 3) builder.clear builder add n(4) // false
As to
PathBuilder
with the start node 1
.
3
and 4
consecutively.
4
and 3
consecutively...
4
has been refused since it is not a direct successor
of 1
.
add
instead of +=
.
Note that it is also possible to create walk and paths by adding edges and, for multigraphs, to define an edge selector.