# Core User Guide: Traverse Your Graph

Graph traversals are invoked by means of a Traverser that extends `scala.collection.Traversable` in turn. This may happen

• directly to allow fine-grained control or
• under the hood whenever you call a "high level" method like `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
```

## Traverse for a specific node, a path or a cycle

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. Searches for any (direct or indirect) successor of node `1` having `outDegree > 3` and finds `None`.
2. Searches for any successor of node `1` having `outDegree >= 3` and finds node `3`.
3. Searches for any successor of node `4` having only undirected edges and finds node `2`.
4. Successfully tests for node `4` being a predecessor of node `1`.
5. Finds an arbitrary path from node `1` to node `4`.
6. Finds a path from node `1` to an arbitrary node having `outDegree >= 3`.
7. Determines the shortest path from node `3` to node `1`.
8. Gets the path of type `g.Path`.
9. Reduces path `p` to the nodes on the path.
10. Among others, `g.Path` supports `weight` to calculate the total of the edge weights on the path.
11. Defines a custom weight function to override static edge weights. Using `float` demonstrates that the weight method may return any numeric type.
12. Calls `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.
13. Note that the weight of the returned path does not reflect the custom weights used to calculate the shortest path but just the static weights of the edges on the path.
14. Finds a path from node `4` to node `2` by restricting the traversal to a subgraph containing only nodes with value less than `4`.
15. Finds a path from node `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

1. Finds an arbitrary cycle in `g`, if any.
2. Finds an arbitrary cycle reachable from node `4`, if any. Node `4` does not necessarily lies on the path.
3. `c1` and `c2` are not equal because they start at different nodes.
4. Even so, `c1` and `c2` depict the same cycle in a semantic sense.
5. There exists no cycle containing node `1`.

Cycle detecting works for directed, undirected and mixed graphs, alike.

## Refine traversers by properties

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, edges: (EdgeT) => 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

### Ordering

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: _*)
```

## Traverse for elements

`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

1. Starts a traversal by outer nodes at `n1` to sum up the node values.
2. The same traversal as before invoked at graph level.
3. The same traversal as before but restricted up to a depth of 1.
4. Calculates the sum of weights over all edges. Here we could employ `outerEdgeTraverser` as well.
5. Traverses `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`.
6. `g.InnerNode` respectively `g.InnerEdge` extract both the inner and the outer element. </ol>

### Visit elements down and up

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])"
```

### Extend visitors

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)))
```

## Combine queries with visitors

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.

## Find components

You can search for weakly or strongly connected components. In both cases you first need to decide on where the search should start:

• Starting at graph level ensures that all components of the graph will be returned.
• If you start at a specific node you will get all components reachable from that node. This means you will not necessarily get all the components you would get if you started at graph-level.

### Find weakly connected components

```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

1. Creates a disconnected graph with two components.
2. The elements of `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
```

### Find strongly connected components

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

1. The graph is composed by two strong components connected by a simple directed edge.
2. The graph-level traverser yields the strong components that we lift to graphs.
3. Check that the strong components found equal to the expected ones.

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

1. If we start at a node of the second component, we get just that component.
2. In case you are interested in the visited elements during the search invoke the search on a traverser.

### To the type `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.

## Sort topologically

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`.

### Sort on graph level

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.

### Combine your sort with fluent properties

To combine `topologicalSort` with any of the familiar fluent properties, call `componentTraverser` first like

```graph.componentTraverser().withSubgraph(nodes = myNodeFilter).topologicalSort
```

### Sort on node level

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()
```

### Sort on component level

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.

### Exploit `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:

1. layer 0 contains all nodes having no predecessors
2. layer n contains those nodes that have only predecessors in ancestor layers with at least one of them contained in layer n - 1.

Among others, layers are usefull to

• compute several valid topological orders by altering the order of nodes within layers or
• to maintain a stable ordering over JVM instances.

To cancel a traversal

• prefer calling one of `scala.collection.Traversable`'s methods that stop the traversal as soon as the specified condition holds true such as `exists` or `collectFirst`
• you may want to refer to the exception-based `break()` as provided by `scala.util.control.Breaks`
• finally, `return` is also an option assumed you are familiar with its downside.

## Build walks and paths

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()
1. Instantiates a `PathBuilder` with the start node `1`.
2. Adds the nodes `3` and `4` consecutively.
3. Tries to add the nodes `4` and `3` consecutively...
4. ...but adding `4` gets refused since it is not a direct successor of `1`.
5. You may want to check whether an addition was accepted by calling `add` instead of calling `+=`.