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 = _.toOuter == 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. Call get with caution. It is ok in test code if you know that the node exists.
  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.

Adding and Subtracting

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
h.addLEdge(3,4)("red") // true

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

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 <~?
Neighbor and Incident Methods.

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

Querying by Function

val g = Graph(2 ~> 3, 3 ~ 1, 5)
g.nodes filter (_.toOuter > 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 = _.toOuter >= 3, edge = _.isDirected) // Int = 3

As to

  1. Filters the node set by (NodeT) => _.toOuter > 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 matching 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(_.toOuter == 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.