# Core User Guide: Inspect Your Graph

Import the following for the examples below:

```import scalax.collection.edges._
import scalax.collection.hyperedges._
import scalax.collection.generic.AnyEdge
import scalax.collection.{OneOrMore, Several}
import scalax.collection.OuterImplicits._
import scalax.collection.mutable.Graph
```

Note that all the demonstrated features also work for immutable graphs unless commented to the contrary.

## Iterate over elements

```val g = Graph(2 ~ 3, 3 ~ 1)
g.toString            // "Graph(NodeSet(1, 2, 3), EdgeSet(2 ~ 3, 3 ~ 1))"
g.nodes mkString ", " // "1, 2, 3"
g.edges mkString ", " // "2 ~ 3, 3 ~ 1"
g.outerIterator
.map {
case g.OuterNode(n) => n.toString
case g.OuterEdge(e) => e.toString
}
.mkString(", ")     // 1, 2, 3, 2 ~ 3, 3 ~ 1
```

As to

1. `nodes` of the type `NodeSetT` returns the node set of the graph.
2. `edges` of the type `EdgeSetT` returns the edge set of the graph.
3. You can use `iterator` or `outerIterator` to iterate over nodes and edges in one go.

`NodeSetT` and `EdgeSetT` are inner classes that extend `scala.collection.Set` by also adding a few methods like `draw` for picking a random element.

## Look up nodes and edges

```val g = Graph(1 ~ 2)
g find 1              // Option[g.NodeT] = Some(1)
g find 3              // Option[g.NodeT] = None
g get 1               // g.NodeT = 1
g get 3               // NoSuchElementException
g find 1 ~ 2          // Option[g.EdgeT] = Some(1 ~ 2)
g.nodes find (_ == 1) // Option[g.NodeT] = 1
g addAndGet 3         // g.NodeT = 3
```

As to

1. Searches for and finds the inner node wrapping the outer node `1` in constant time.
2. Searches for the inner node wrapping the outer node 3 but cannot find it.
3. Searches for, finds and gets the inner node wrapping the outer node `1` in constant time. Call `get` with caution. It is fine especially in test code if you know that the node exists.
4. Searches for but does not find any inner node that wraps `3` so `NoSuchElementException` is thrown.
5. Searches for and finds the inner edge wrapping the outer edge `1 ~ 2`. Looking up edges works in the same manner as for nodes.
6. Not a real lookup since it searches over all nodes stopping at the first node with the predicate ```_ == 1``` in linear time.
7. Available only for mutable graphs, adds `3` to the node set and returns the new inner node.

You need to look up nodes and edges to invoke traversals starting at a specific element. With respect to traversals we also call the starting inner node the "root node". Look-ups are implemented in terms of `hashCode` and `equals`.

## Inspect edge ends

```val unDiEdge = 3 ~ 4           // UnDiEdge[Int]
unDiEdge._1 * unDiEdge._2      // Int = 12
unDiEdge.ends.iterator.product // Int = 12
unDiEdge match {
case n ~ m => n * m          // Int = 12
}

val diEdge = 1 ~> 2            // DiEdge[Int]
unDiEdge.arity == diEdge.arity // true
diEdge.source - diEdge.target  // Int = -1
diEdge match {
case s ~> t => s - t         // Int = -1
}

val hyperEdge = 1 ~~ 2 ~~ 11 ~~ 12            // HyperEdge[Int]
hyperEdge.ends.get(hyperEdge.arity - 1)       // Int = 12
hyperEdge.ends.iterator.sum                   // Int = 26
hyperEdge match {
case ~~(Several.Seq(n1, n2, _*)) => n1 - n2 // Int = -1
}

val diHyperEdge = OneOrMore(1, 2) ~~> OneOrMore(5, 6)           // DiHyperEdge[Int]
diHyperEdge.sources.iterator.sum                                // Int = 3
diHyperEdge.targets.iterator.sum                                // Int = 11
diHyperEdge match {
case OneOrMore.Seq(_, s2, _*) ~~> OneOrMore(t1, _) => s2 * t1 // Int = 10
}
```

As to

1. `_1` and `_2` provide access to the first and second node of an edge.
2. `ends` allows for iterating over all connected nodes.
3. The endpoints of edges may also be extracted by means of pattern matching.
4. When dealing with directed edges, you will prefer the accessors `source` and `target` that are synonyms for `_1` and `_2`.
5. Both `unDiEdge` and `diEdge` have an `arity` of 2.
6. `get` allows for direct access by index. Here we access the last node of `hyperEdge`.

## Pattern match labeled edges

Besides how to add infix edge extractors, please refer to any of the numerous examples in the test code base like

## Inspect neighbors and incident edges

```val g = Graph[Int, AnyEdge](0, 1 ~ 3, 3 ~> 2)

def n(outer: Int): g.NodeT = g get outer

n(0).diSuccessors   // Set[g.NodeT] = Set()
n(2).diSuccessors   // Set[g.NodeT] = Set()
n(3).diSuccessors   // Set[g.NodeT] = Set(1, 2)
n(3).diPredecessors // Set[g.NodeT] = Set(1)
n(2).incoming       // Set[g.EdgeT] = Set(3 ~> 2)
```

As to

1. Looks up the inner node for a given outer node.
2. Node `n(0)` is independent so the set of direct successor nodes is empty.
3. Node `n(2)` is reachable but has no direct successor so the set of its out-neighbors is empty, too.
4. From node `n(3)`, `1` and `2` are reachable.
5. The only direct predecessor of node `n(3)` is node `1`.
6. From the perspective of `n(2)` there is only one incoming edge namely `3 ~> 2`.

All in all, given a specific node, the following methods are available to inspect incident edges and neighbors:

 Result Type Method name Synonym `Set[NodeT]` `diSuccessors` `outNeighbors` `diPredecessors` `inNeighbors` `neighbors` `Set[EdgeT]` `outgoing` `outgoingTo` `incoming` `incomingFrom` `Option[EdgeT]` `findOutgoingTo` `findIncomingFrom`

For "inspecting" elements that need not be connected directly, see Traverse Your Graph.

## Query the node or edge set

```val g = Graph[Int, AnyEdge](2 ~> 3, 3 ~ 1, 5)

g.nodes.filter(_.outer > 2)         // Set[g.NodeT] = Set(3, 5)
g.nodes.filter(_.degree > 1)        // Set[g.NodeT] = Set(3)

g.outerIterator
.filter {
case g.OuterNode(n)               => n > 1
case g.OuterEdge(AnyEdge(n1, n2)) => n1 > 1 && n2 > 1
}
.map {
case g.OuterNode(n) => n
case g.OuterEdge(e) => e
}
.toList // List[Any] = List(2, 3, 5, 2 ~> 3)

g.iterator
.filter {
case g.InnerNode(innerN, _) => innerN.degree > 1
case g.InnerEdge(_, outerE) => outerE.isDirected
}
.mkString // String = 3, 2 ~> 3
```

As to

1. Filters the node set by `(n: NodeT) => n.outer > 2`.
2. Filters nodes by the predicate `_.degree > 1` where `degree` is a method of inner nodes.
3. Filters edges by not having any adjacent edges.
4. Filters all outer elements to be either a node with a value greater than 1 or an edge with ends that have a value greater than 1. `outerIterator` has the type `Iterator[OuterElem]`.
5. Filters all inner elements to be either a nodes with a degree greater than 1 or a directed edge. `iterator` has the type `Iterator[g.InnerElem]`.
6. `InnerNode` extracts both the inner and the corresponding outer node. We need the inner node to be able to call `degree`.
7. `InnerEdge` extracts both the inner and the corresponding outer edge. Here we just need the outer edge.

## Compute union, difference and intersection

```val g = Graph(1~2, 2~3, 2~4, 3~5, 4~5)
val h = Graph(3 ~ 4, 3 ~ 5, 4 ~ 6, 5 ~ 6)
g union h      // Graph(1 ~ 2, 2 ~ 3, 2 ~ 4, 3 ~ 5, 4 ~ 5, 3 ~ 4, 4 ~ 6, 5 ~ 6)
g diff h       // Graph(1 ~ 2)
g intersect h  // Graph(4, 3 ~ 5)
g &= h         // Graph(4, 3 ~ 5), mutated instance
```

`union`, same as operator `++`, `diff`, same as `--`, and `intersec`, same as `&`, work in compliance with graph theory definitions.

Use any of the above operators followed by `=` to mutate your mutable graph.

Assume `g` being the mixed graph in chapter Traverse Your Graph. Then

```import scalax.collection.edge.Implicits._
val g = Graph[Int, AnyEdge](1 ~ 2, 2 ~ 3, 1 ~> 3, 1 ~ 5, 3 ~ 5, 3 ~ 4, 4 ~> 4, 4 ~> 5)

g.order                                // Int = 5
g.size                                 // Int = 8
g.elementCount                         // Int = 13
g.totalDegree                          // Int = 16
g.degreeSet                            // TreeSet(4, 3, 2)
g.degreeNodeSeq(g.InDegree)            // List((4, 3), (3, 5), (2, 1), (2, 2), (2, 4))
g.degreeNodesMap                       // Map(2->Set(2), 3->Set(5, 1), 4->Set(3, 4))
g.degreeNodesMap(degreeFilter = _ > 3) // Map(4 -> Set(3, 4))
```

As to

1. The order of (number of nodes in) `g`.
2. The size of (number of edges in) `g`.
3. The number of all contained elements (nodes and edges) of `g`.
4. The total degree (sum of degrees over all nodes).
5. The distinct, decreasing set of degrees over all nodes of `g`.
6. The non-decreasing sequence of in-degrees over all nodes in `g` with inner node references.
7. A map of degrees over all nodes in `g` with nodes having the degree of key.
8. The same map as on line 9 restricted to degrees greater than `3`.

Degree methods come with implicit parameters to choose in- or out-degrees and optionally filter them.

```val g = Graph(1, 2 ~> 3)

g.isConnected                                                  // false
(g addOne 2 ~> 1).isConnected                                  // true
(g get 2).findConnected(_.outer == 3)                          // Some(3)
g.isCyclic                                                     // false
(g addOne 3 ~> 2).isCyclic                                     // true
g.isComplete                                                   // false
(g ++ List(1 ~> 2, 1 ~> 3, 2 ~> 1, 3 ~> 1, 3 ~> 2)).isComplete // true
g.isDirected                                                   // true
g.isHyper                                                      // false
g.isMulti                                                      // false
```