# 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 addAndGet 5                     // g.NodeT = 5
g find (g having (node = _ == 1)) // g.NodeT = 1
```

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. In case of a mutable `Graph,` adds `5` to the node set and returns the added inner node. This method enables you to couple adding and getting the same node.
7. 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.

Looking up nodes and edges is necessary to invoke graph functionality on a specific element - also called root - of a given graph. This 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. The default implementation uses `hashCode` for look-ups.

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

## Adding and Subtracting

```val g = Graph(1, 2~3)  // immutable or mutable
g + 1                  // == g
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[GraphParam[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(2, 3~3)     // Graph(1, 3)
val g = scalax.collection.mutable.Graph(1, 2~3)
// Graph[Int,UnDiEdge]
// to be assigned before each example
g += 0                 // Graph(0, 1, 2, 3, 2~3)
g ...=                 // (mutated graph)
g +~= (3~>1)           // Graph(1, 2, 3, 2~3, 3~>1)
implicit val factory = scalax.collection.edge.LDiEdge
g                      // Graph(1, 2, 3, 4, 2~3, 3~>4 'red)
```

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 same mutable `Graph` instance.
15. All addition and subtraction operations valid for immutable graphs have their mutable counterparts with `=` as the last operand character.
16. `+~= `is an edge creation operator with its counterpart methods `addEdge` and `addAndGetEdge`.
17. `addLEdge` (same as `+~+=`) adds a labeled edge to a mutable graph specifying its nodes and label. This class of methods (operators) doesn't require outer edge parameters but has an `implicit `edge factory parameters, instead.

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 = 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(3~5, 4)
g &= h         // Graph(3~5, 4), same 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] = 3~4
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] = 1~>2
dE.source - dE.target   // Int = -1
uE.arity == dE.arity    // Boolean = true
dE match {
case s ~> t => s - t
}                       // Int = -1
val hE = 1~2~11~12      // HyperEdge[Int] = 1~2~11~12
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`.
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)
val (n0, n2, n3) = (g get 0, g get 2, g get 3)
n0 diSuccessors          // Set[g.NodeT] = Set()
n2.diSuccessors.isEmpty  // Boolean = true
n3 diSuccessors          // Set[g.NodeT] = Set(1, 2)
n3 diPredecessors        // Set[g.NodeT] = Set(1)
n2 incoming              // Set[g.EdgeT] = Set(3~>2)
n3 ~>? n2                // Option[g.EdgeT] = Some(3~>2)
```

As to

1. Node `n0` is independent so the set of direct successor nodes is empty.
2. Node `n2` is reachable but has no direct successor so the set of its out-neighbors is empty, too.
3. From node `n3`, `1` and `2` are reachable.
4. The only direct predecessor of node `n3` is node `1`.
5. From the perspective of node `n2` 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 </p>

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

```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,4), (2,2))
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 is designed for functional style programming enabling to chain method calls as you feel inclined.