# Core User Guide: Graph Operations

## Iterating

```val g = Graph(2~3, 3~1)
g mkString ","	             // "1,2,3,2~3,3~1"
g.nodes mkString "-"         // "1-2-3"
g.edges mkString " "         // "2~3 3~1"
```

As to

1. Iterating over a `Graph` instance you get all nodes and all edges. `Graph` extends `Set[GraphParam]`. `GraphParam` is an algebraic type for outer nodes, outer edges, inner nodes and inner edges.
2. `nodes` returns the node set which in turn is an instance of `Set[NodeT]`.
3. `edges` returns the edge set which in turn is an instance of `Set[EdgeT]`.

Both `Graph` and its inner classes `NodeSet` and `EdgeSet` extend `scala.collection.Set`. Thus, you can call the gamut of well-known `TraversableLike` methods on these such as `filter`, `foreach` etc.

## Looking 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 find (g having (node = _ == 1)) // g.NodeT = 1
val h = mutable.Graph.empty[Int,UnDiEdge] ++ g
g addAndGet 5                     // g.NodeT = 5
```

As to

1. Searches for and finds the inner node wrapping the outer node `1`.
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`.
4. Searches for but does not find an inner node wrapping the outer node `3`.
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. This is no more a direct access to a specific element, but rather a search over all nodes stopping at the first node with the predicate `_ == 1`. `having `may take a `node` and/or an `edge` argument.
7. Creates a mutable Graph equaling to `g`.
8. For a mutable `Graph`, adds `5` to the node set and returns the new inner node. This method couples adding and getting the same node.

Looking up nodes and edges is necessary to invoke graph functionality at a specific element of the graph. With respect to an operation we also call an inner node the "root node". Looking up is similar to getting a value of a `Map` entry by passing a key to the map. In case of `Graph` the "key" is an outer node or edge and the returned "value" is the inner node or edge. Look up is implemented in terms of `hashCode` and `==`.

## Equality of Inner and Outer Objects

```val g = Graph(1~2)
(g get 1) == 1	        // true
(g get 1~2) == 2~1	    // true
(g get 1~2) eq 2~1	    // false
(g get 1~2) == 2~2	    // false
```

As to

1. The inner node `1 `equals to the outer node `1`.
2. The inner edge `1~2 `equals to the outer edge `2~1`. This example also demonstrates, that in case of undirected edges the order of nodes does not influence equality.
3. `eq` fails, because an inner edge can never be the same instance as an outer edge.
4. Obviously, `1~2 `does not equal to `2~2`.

```val g = Graph(1, 2~3)  // immutable or mutable
g + 1                  // g unchanged
g + 0                  // Graph(0, 1, 2, 3, 2~3)
g + 1.2                // error: overloaded method...
g + 0~1                // Graph(0, 1, 2, 3, 0~1, 2~3)
g ++ List(1~2, 2~3)    // Graph(1, 2, 3, 1~2, 2~3)
g ++ List[Param[Int,UnDiEdge]](1~2, 2~3, 0)
// Graph(0, 1, 2, 3, 1~2, 2~3)
g - 0                  // g
g - 1                  // Graph(2, 3, 2~3)
g - 2                  // Graph(1, 3)
g -? 2                 // g
g - 2~3                // Graph(1, 2, 3)
g -! 2~3               // Graph(1)
g --  List[Param[Int,UnDiEdge]](2, 3~3)
// Graph(1, 3)
def h = mutable.Graph.empty[Int,UnDiEdge] ++ g
h += 0                 // Graph(0, 1, 2, 3, 2~3)
h += (3 ~> 1)          // Graph(1, 2, 3, 2~3, 3~>1)
implicit val factory = scalax.collection.edge.LDiEdge
```

As to

1. Node `1` is not added because it is already contained, so the same instance is returned.
2. Node 0 is added to a new `Graph` instance.
3. `Double` is incompatible with `Int` so the compiler will issue an error.
4. Edge `0~1` is added to a new `Graph` instance.
5. All edges contained in the right hand operand are added to a new `Graph` instance.
6. All edges or nodes contained in the right hand operand are added to a new `Graph` instance.
7. Node `0` is not removed because it is not contained, so the same instance is returned.
8. Node `1` is removed from a new `Graph` instance. This node was not incident with any edge.
9. Node `2` along with `2~3` is ripple removed from a new `Graph` instance. Node `2` was incident with `2~3`.
10. Node `2` is not removed because this gentle removal succeeds only if the node is not incident with any edge.
11. Edge `2~3` is removed from a new `Graph` instance leaving its incident nodes in place.
12. Edge `2~3` along with its incident nodes `2` and `3` is removed from a new `Graph` instance. Incident nodes will only be removed if they are not incident with any other edge.
13. All edges or nodes contained in the right hand operand are removed from a new `Graph` instance.
14. Node 0 is added to the a mutable `Graph` equaling to `g`.
15. `addLEdge` (same as `+~+=`) adds a labeled edge to a mutable graph passing the connected nodes and the label. This kind of method has an `implicit ` edge factory parameter.

The `Graph` operators `+`, `+=` for adding and `-`, ` -=` for subtracting may have an inner or outer node or edge at the right hand side. Graph for Scala guarantees a consistent state of the node and edge sets after any operation including duplicate node/edge prevention as demonstrated on line 5.

Both ripple and gentle removal schemas are supported. Using the standard operators `-` and `-=`, removals comply with the definition of node and edge removal in graph theory: ripple removal of nodes as on the lines 9 to 11 and gentle removal of edges as on line 13. In addition, gentle removal of nodes by `-?` and `-?=` as on line 12 as well as ripple removal of edges by `-!` and `-!=` as on line 13 are also supported.

It is also possible to add elements to or subtract elements from node and edge sets. However, these operations have less practical relevance as the result is always a decoupled immutable set.

In case of mutable graphs, two kinds of edge addition are supported:

• Standard addition is achieved by the operator ```+= ```requiring an instance of `EdgeLike` at the right hand side `–` see example d).
• Factory-based addition is achieved by special `add*` methods or the corresponding operators having the incident nodes and optionally an edge weight and label as arguments. The edge factory to be used for internal edge creation must be defined as ```implicit val``` - see example q). Factory based addition should slightly outperform standard addition.

For adding or subtracting elements of another `Graph` instance in bulk see 4.5.

## Computing Union, Difference and Intersection

```val g = mutable.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
```

Also `union` (same as `++`), difference (`diff` same as `--`) and intersection (`intersec` same as `&`) work in compliance with the corresponding definitions in graph theory. Use any of the previous operators followed by `=` for the mutable variants.

## Inspecting Endpoints

```val uE = 3~4            // UnDiEdge[Int]
uE._1 * uE._2           // Int = 12
uE.product              // Int = 12
uE match {
case n ~ m => n * m
}                       // Int = 12
val dE = 1~>2           // DiEdge[Int]
dE.source - dE.target   // Int = -1
uE.arity == dE.arity    // true
dE match {
case s ~> t => s - t
}                       // Int = -1
val hE = 1~2~11~12      // HyperEdge[Int]
hE._n(hE.arity - 1)     // Int = 12
hE.sum                  // Int = 26
```

As to

1. `_1` and `_2` provide access to the first and second node of an edge.
2. Edges are also `Iterable` with respect to the connected nodes.
3. The endpoints of edges may also be extracted by means of pattern matching.
4. The first node of a directed edge may be accessed by `_1` or `source`, the second by `_2` or `target`.
5. Both `uE` and `dE` have an `arity` of 2.
6. `_n` also enables direct access. Here we access the last node of `hE`.
7. Again, all edges including hyperedges are `Iterable`s.

## More Edge Patterns

```import scalax.collection.edge.Implicits._
val g = Graph((1 ~+> 2)("A"), (1 ~+> 1)("AB"))

import scalax.collection.edge.LBase._
object StringLabel extends LEdgeImplicits[String]
import StringLabel._

(0 /: g.edges)((sum, e) => e.edge match {
case s :~> t + (l: String) if l contains 'A' =>
sum + s.outDegree + t.outDegree
}) // Int = 6
```

Edge patterns are especially handy when extracting the attributes of weighted and/or labeled edges. The above `fold` calculates the sum of the out-degrees of edge endpoints restricted to edges with a label containing `'A'` by applying an infix operator pattern to each edge of the graph.

The constructor pattern `LDiEdge(s, t, l)` would be an alternative to `s :~> t + l`. Operator names have been selected in compliance with edge constructor shortcuts: `:~` matches undirected, `:~>` directed edges. `%`, `+` and `%+` match weighted, labeled and weighted-labeled edges, respectively.

Note that you need to dereference inner edges of type `EdgeT` by calling the accessor method `edge` to facilitate the predefined edge extractors. You'll find more edge pattern matching examples in TEdge.scala.

## Inspecting Neighbors and Incident Edges

```val g = Graph(0, 1~3, 3~>2)
def n(outer: Int): g.NodeT           = g get outer
def e(outer: UnDiEdge[Int]): g.EdgeT = g get outer
n(0).diSuccessors          // Set[g.NodeT] = Set()
n(2).diSuccessors.isEmpty  // true
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)
n(3) ~>? n2                // Option[g.EdgeT] = Some(3~>2)
```

As to

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

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

 Result Type Method name Synonyms `Set[NodeT]` `diSuccessors` `outNeighbors`, `~>|` `diPredecessors` `inNeighbors`, `<~|` `neighbors` `~|` `Set[EdgeT]` `outgoing` `~>` `outgoingTo` `~>` `incoming` `<~` `incomingFrom` `<~` `Option[EdgeT]` `findOutgoingTo` `~>?` `findIncomingFrom` `<~?`

See also: `object scalax.collection.Graph#InnerNodeLike`.

## Querying by Function

```val g = Graph(2~>3, 3~1, 5)
g.nodes filter (_ > 2)                  // Set[g.NodeT] = Set(5,3)
g.nodes filter (_.degree > 1)           // Set[g.NodeT] = Set(3)
g.edges filter (_.diSuccessors.isEmpty) // Set[g.EdgeT] = Set()
g filter ((i: Int) => i >= 2)           // Graph(2,3,5, 2~>3)
g filter g.having(node = _ >= 2)        // Graph(2,3,5, 2~>3)
g filter g.having(edge = _.directed)    // Graph(2,3, 2~>3)
g count  g.having(node = _ >= 3, edge = _.directed) // Int = 3
```

As to

1. Filters the node set by `(NodeT) => _ > 2`.
2. Filters nodes with a `degree > 1`.
3. Filters edges with no adjacent edges.
4. Creates a subgraph of `g` with nodes satisfying `_ >= 2` and their incident edges.
5. Same as d) utilizing `having`. Method `having`, returning a partial function, helps to reduce code by internally `match`ing nodes and edges.
6. Creates a subgraph of `g` consisting of `directed` edges only. Note that filtering `g.edges` is not an alternative because it would return a set of contained edges, not a subgraph.
7. Counts the number of nodes and edges satisfying either of the given predicates.

`Graph` queries may start at the node set `nodes`, the edge set `edges` or at the `Graph` instance. Filtering a graph results in a subgraph obtained by node and/or edge predicates.

## Measuring Graphs and Grouping Nodes by Degree

Assume `g` being the mixed graph in chapter Traversing Graphs. Then

```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)
g.order                                // Int = 5
g.graphSize                            // Int = 8
g.size                                 // 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) of `g`.
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 7 restricted to degrees greater than `3`.

All degree methods have implicit parameters to query in- or out-degrees and filtering degrees.

## Classifying Graphs

```val g = Graph(1, 2~>3)
g.isConnected                   // false
(g + 2~>1).isConnected          // true
(g get 2).findConnected(_ == 3) // Some(3)
g.isCyclic                      // false
(g + 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
```

As to

1. Besides determining whether `g` is connected it is also possible to call `findConnected` at a specific node.
2. See also `findCycle` on the graph instance or starting at a specific node.

## Chaining Method Calls

```g.nodes find (_.inDegree > g.order / 5) orElse g.nodes.headOption
```

Graph for Scala is designed for functional style programming meaning that you chain method calls as you feel inclined.