Graph traversals are invoked by means of a Traverser
that extends scala.collection.Traversable
in turn. This may happen
findCycle
.
Needless to say, all methods relying on recursion are tail recursive.
The examples below make use of
import scalax.collection.edges._ import scalax.collection.edges.labeled._ import scalax.collection.generic.AnyEdge import scalax.collection.OuterImplicits._ import scalax.collection.immutable.Graph // or mutable
Mostly you are solely interested in the result of a graph traversal such as a specific node, a path or cycle rather than in tracking visited elements. Chances are good that you will find a method that meets your requirement out of the box.
Playing around with the weighted mixed graph along with a lookup function
val g = Graph[Int, AnyEdge]( 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
you can do
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 maybeP = n(3) shortestPathTo n(1) // Some(Path(3, 3 ~ 4 % 1, 4, 4 ~> 5 % 0, 5, 1 ~ 5 % 3, 1)) val p = maybeSp.get // here we know that maybeP is defined p.nodes // List[g.NodeT] = Nodes(3, 4, 5, 1) p.weight // Double = 4.0 def negWeight(e: g.EdgeT): Float = 5.5f - e.weight val maybeNegP = n(3) shortestPathTo (n(1), negWeight) // Some(Path(3, 2 ~ 3 % 2, 2, 1 ~ 2 % 4, 1)) maybeNegP.map(_.nodes.toList) // Option[List[g.NodeT]] = Some(List(3, 2, 1)) maybeNegP.map(_.weight) // Option[Double] = Some(6.0) val maybeSubgraphP1 = n(4).withSubgraph(nodes = _ < 4) pathTo n(2) // Some(Path(4, 3 ~ 4 % 1, 3, 2 ~ 3 % 2, 2)) maybeSubgraphP1.map(_.nodes.toList) // Option[List[g.NodeT]] = Some(List(4, 3, 2)) val maybeSubgraphP2 = n(4).withSubgraph(edges = _.weight != 2) pathTo n(2) // Some(Path(4, 4 ~> 5 % 0, 5, 1 ~ 5 % 3, 1, 1 ~ 2 % 4, 2)) maybeSubgraphP2.map(_.nodes.toList) // Some(Nodes(4, 5, 1, 2))
As to
1
having outDegree > 3
and finds None
.
1
having outDegree >= 3
and finds node
3
.
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
.
g.Path
.
p
to the nodes on the path.
g.Path
supports weight
to calculate the total of the edge weights on the
path.
float
demonstrates that the weight method may return any numeric type.
shortestPathTo
with the above custom weight function 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
by restricting the traversal to a subgraph containing only nodes with value less than 4
.
4
to node 2
by 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.
Node 4
does not necessarily lies on the path.
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.
You may have noticed a call of withSubgraph
above.
We also refer to such methods, all prefixed by with
, as fluent traverser properties
since they encourage a fluent way of method calls.
You can refine any Traverser
by means of the following properties:
Property | Factory method | Sample Value | See |
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, check out TraversalSpec.scala
As a special case, assume you want to control the order of edges during traversal.
You can do so by setting the ordering
property.
Let's look at an example where we ensure that edges are traversed in reverse order of their weights:
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.BaseInnerEdge.WeightOrdering.reverse.compare _) val traverser = (g get root).outerNodeTraverser.withOrdering(edgeOrdering) traverser.toList // List(1 to 7: _*)
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 and only 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:
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 n1.innerElemTraverser .filter { case g.InnerNode(n, _) => n.degree > 1 case g.InnerEdge(_, e) => e.weight > 1 } .map { case g.InnerNode(_, n) => n case g.InnerEdge(_, e) => e } .toSet // Set(1, 2, 3, 1 ~> 3 % 2, 2 ~> 3 % 3)
As to
n1
to sum up the node values.
outerEdgeTraverser
as well.
g
for all its elements reachable from n1
to return a set of InnerElem
s with nodes having a degree greater than 2
and
edges having a weight greater than 1
.
g.InnerNode
respectively g.InnerEdge
extract
both the inner and the outer element.
</ol>
Assume you'd like to traverse a graph, especially a tree, in a stack-like manner
because you need to carry out one action when touching a node the first time and another action when touching the
same node the second time in course of traversing up in an 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 = innerRoot.innerNodeDownUpTraverser.foldLeft(ArrayBuffer.empty[String]) { (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.fold("")(_ + _) // "(A[B1][B2])" or "(A[B2][B1])"
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. extended visitors come in handy. Beware that these are implementation specific:
val g = Graph(1 ~> 2, 1 ~> 3, 2 ~> 3, 3 ~> 4, 4 ~> 2) import g.ExtendedNodeVisitor type ValDepth = (Int, Int) var info = List.empty[ValDepth] (g get 1).innerNodeTraverser.foreach { ExtendedNodeVisitor((node, _, depth, _) => info :+= (node.outer, depth)) } info.sortWith((a: ValDepth, b: ValDepth) => a._1 < b._1 || a._1 == b._1 && a._2 < b._2 ) // List((1, 0), (2, 1), (3, 1), (4, 2)))
You can also append a visitor to any traversal for a result like a path or cycle like:
val g = Graph(1 ~> 2, 1 ~> 3, 2 ~> 3, 3 ~> 4, 4 ~> 2) var center: Option[g.NodeT] = None val maybeCycle = (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) } ) maybeCycle.map(_.sameElements(List(2, 2 ~> 3, 3, 3 ~> 4, 4, 4 ~> 2, 2))) // Some(true) center // Some(2)
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 can search for weakly or strongly connected components. In both cases you first need to decide on where the search 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 component.nodes.foldLeft(0)((cum, n) => cum + n.outer) // List(6, 18)
As to
sums
correspond to the sums of the integer node values per component.
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 tail-recursive version of Tarjan's algorithm.
Let us refer to the sample graph on Wikipedia:
type G = Graph[Char, DiEdge[Char]] val sccExpected: (G, G) = ( 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) concat List('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 nodes
and a lazy set of the contained edges
.
Also, 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 of type Graph
and root
is of type graph.NodeT
.
As a matter of course, you can call topologicalSort
directly on your graph instance:
graph.topologicalSort.fold( failure => ???, order => ??? )
The result is of type TopologicalSort
being a type alias for
Either[TopologicalSortFailure, TopologicalOrder[NodeT]]
.
On failure, using the content of Left
you have specific support to get a causing cycle.
On success, Right
contains the calculated TopologicalOrder
represented by layers.
When called at graph level, this will include all nodes irrespective of whether they are connected or
they live in different components.
To combine topologicalSort
with any of the familiar fluent properties,
call componentTraverser
first like
graph.componentTraverser().withSubgraph(nodes = myNodeFilter).topologicalSort
Whenever starting at a concrete inner node, topologicalSort()
will only include nodes
within the comopnent spanned by that 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 node-level topologicalSort()
also has a boolean argument
allowing you to exclude predecessors from the result. Therefore, you always need to provide 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 yields a Traversable[TopologicalSort]
, 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( failure => yourFailureHandler, _.toLayered foreach println // prints topological 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
scala.collection.Traversable
's methods that stop the traversal
as soon as the specified condition holds true such as exists
or collectFirst
break()
as provided by
scala.util.control.Breaks
return
is also an option assumed you are familiar with its downside.
WalkBuilder and
PathBuilder allow you to build a
Walk respectively
Path
in terms of the underlying graph.
This comes in handy whenever you have some results computed outside the library and would like to represent them
by Graph for Scala path-dependent types.
Since WalkBuilder
and PathBuilder
enforce proper walk/path semantics
they are also well suited for checking user-supplied paths.
Here is how you can create a path in the sample graph above step by step
by means of a PathBuilder
:
val builder = g.newPathBuilder(n(1)) builder += n(3) += n(4) builder.result().toOuterElems.toList // List[Outer](1, 1 ~> 3 % 5, 3, 3 ~ 4 % 1, 4) builder.clear builder += n(4) += n(3) builder.result().toOuterElems.toList // List[Outer](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
gets refused since it is not a direct successor of 1
.
add
instead of calling +=
.
Note that it is also possible to create walks and paths by adding edges and, for multi-graphs, to define an edge selector.