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

3. nodes of the type NodeSetT returns the node set of the graph.
4. edges of the type EdgeSetT returns the edge set of the graph.
5. 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

2. Searches for and finds the inner node wrapping the outer node 1 in constant time.
3. Searches for the inner node wrapping the outer node 3 but cannot find it.
4. 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.
5. Searches for but does not find any inner node that wraps 3 so NoSuchElementException is thrown.
6. Searches for and finds the inner edge wrapping the outer edge 1 ~ 2. Looking up edges works in the same manner as for nodes.
7. Not a real lookup since it searches over all nodes stopping at the first node with the predicate _ == 1 in linear time.
8. 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

2. _1 and _2 provide access to the first and second node of an edge.
3. ends allows for iterating over all connected nodes.
4. The endpoints of edges may also be extracted by means of pattern matching.
10. When dealing with directed edges, you will prefer the accessors source and target that are synonyms for _1 and _2.
11. Both unDiEdge and diEdge have an arity of 2.
18. 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

• edges of type Flight
• labeled edges ff
• labeled hyperedges and labeled directed hyperedges ff.

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

3. Looks up the inner node for a given outer node.
5. Node n(0) is independent so the set of direct successor nodes is empty.
6. Node n(2) is reachable but has no direct successor so the set of its out-neighbors is empty, too.
7. From node n(3), 1 and 2 are reachable.
8. The only direct predecessor of node n(3) is node 1.
9. 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.edges.filter(_.adjacents.isEmpty) // Set[g.EdgeT] = Set()

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

3. Filters the node set by (n: NodeT) => n.outer > 2.
4. Filters nodes by the predicate _.degree > 1 where degree is a method of inner nodes.
5. Filters edges by not having any adjacent edges.
7. 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].
12. 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].
14. InnerNode extracts both the inner and the corresponding outer node. We need the inner node to be able to call degree.
15. 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.

Measure your 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

3. The order of (number of nodes in) g.
4. The size of (number of edges in) g.
5. The number of all contained elements (nodes and edges) of g.
6. The total degree (sum of degrees over all nodes).
7. The distinct, decreasing set of degrees over all nodes of g.
8. The non-decreasing sequence of in-degrees over all nodes in g with inner node references.
9. A map of degrees over all nodes in g with nodes having the degree of key.
10. 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.

Classify your graph

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