Core User Guide: Inner and Outer Objects

val g = Graph(1~2)     // Graph[Int,UnDiEdge](1, 2, 1~2)
val n1 = g.nodes.head  // g.NodeT  = 1 or 2
n1.toOuter             // Int      = 1 or 2
val e1 = g.edges.head  // g.EdgeT  = 1~2
e1.toOuter             // UnDiEdge = 1~2
e1._1                  // g.NodeT  = 1
n1.diSuccessors        // Set[g.NodeT]  = Set(2) or Set(1) if n1 == 2
n1 % 2                 // Int           = 1
e1.toOuter             // UnDiEdge[Int] = 1~2

As to

  1. Int and UnDiEdge are the concrete types for the node and edge type parameters. Here they are inferred from the outer edge being passed to the Graph factory.
  2. The node set contains inner nodes of the path dependent type g.NodeT. The node set does not guarantee any specific order of the contained nodes. See 4.2 for how to look up specific nodes.
  3. toOuter, called on an inner node, returns the outer node of type Int.
  4. Elements of the edge set of the type g.EdgeT are so called inner edges.
  5. toOuter, called on an inner edge, returns the outer edge of type UnDiEdge.
  6. Remarkably, the incident nodes of inner edges are inner nodes.
  7. Inner nodes like n1 allow for calling both graph (NodeT) methods like diSuccessors...
  8. ...and any method of the outer node type, here % of Int.
  9. toOuter reconstructs the outer edge 1~2; g.edges.toEdgeInSet  would reconstruct all outer edges.

A basic understanding of inner and outer objects (nodes and edges) is essential for working with Graph efficiently. From the perspective of Graph we distinguish between

  • Outer Nodes
    Outer nodes exist outside of the context of any particular graph and must be provided by the library user. When added to a graph, they will be transparently wrapped by a corresponding inner node. Outer nodes must satisfy the upper bound of the node type parameter of the graph, being Int in the above example. Otherwise they will be rejected by the compiler.
  • Inner Nodes
    Inner nodes are objects bound to a particular graph. They are transparently created on graph instantiation or on adding nodes to a graph. Inner nodes are instances of the inner class NodeT, hence the term, and are implementing the InnerNodeLike interface. An inner node acts as a container of the corresponding outer node also providing a wealth of graph functionality such as diSuccessors or pathTo. Inner nodes always equal to the contained, user-provided outer node thus facilitating interchangeability of inner and outer nodes in many situations. Note that NodeT is a path dependent type such as g.NodeT with g denoting a single graph instance.
  • Outer Edges
    Similarly, outer edges exist outside of the context of any particular graph. Usually they will be provided by the library user by implicit edge factory methods like ~. When added to a graph, they will be transparently wrapped by a corresponding inner edge. Outer edges must satisfy the upper bound of the edge type parameter of the graph, being UnDiEdge in the above example. Otherwise they will be rejected by the compiler. Note that UnDiEdge is, in contrast to UnDiEdge[Int], a so called higher kinded type. Outer edge types must be derived from EdgeLike.
  • Inner Edges
    Last, inner edges are objects bound to a particular graph. They are transparently created on graph instantiation or on adding edges to a graph. Inner edges are instances of the inner class EdgeT and are implementing the InnerEdgeLike interface. An inner edge acts as a container of the corresponding outer edge adding graph functionality. Inner edges always equal to the contained, user-provided outer edge thus facilitating interchangeability of inner and outer edges. Note that EdgeT is a path dependent type such as g.EdgeT with g denoting a single graph instance.

See also:

object scalax.collection.Graph#InnerNodeLike
object scalax.collection.Graph#InnerEdgeLike