Core User Guide: Transform Your Graph

You can transform your graph by means of

1. filter, filterNot
2. foldLeft, foldLeftOuter
3. map methods and
4. flatMap methods.

The mapping functionality is provided by methods with numerous signatures to meet all possible needs. The below examples use directed and undirected graphs but, notably, hypergraph transformation is supported by methods with dedicated signatures.

The examples below make use of

import scala.concurrent.duration._
import scalax.collection.OuterImplicits._
import scalax.collection.edges._
import scalax.collection.generic.AnyEdge
import scalax.collection.immutable.Graph // or mutable

Filter your graph

val g = Graph[Int, AnyEdge](2 ~> 3, 3 ~ 1, 5)

g filter (nodeP = _ >= 2)                         // Graph(NodeSet(2, 3, 5), EdgeSet(2 ~> 3))
g filter (edgeP = _.isDirected)                   // Graph(NodeSet(1, 2, 3, 5), EdgeSet(2 ~> 3))
g filter (nodeP = _ >= 2, edgeP = _.isUndirected) // Graph(NodeSet(2, 3, 5))

Fold your graph

val g = Graph(1 ~> 2, 1 ~> 3, 4)

g.foldLeft(Graph.empty[Int, DiEdge[Int]])(
  opNode = {
    case (cum, g.InnerNode(n, _)) if n.isIsolated => cum + n
    case (cum, _)                                 => cum
  },
  opEdge = {
    case (cum, g.InnerEdge(e, _)) if cum.size % 2 == 0 => cum + e
    case (cum, _) => cum
  }
) // Graph(NodeSet(1, 2, 4), EdgeSet(1 ~> 2)) or
  // Graph(NodeSet(1, 3, 4), EdgeSet(1 ~> 3))

Map your generic graph

To recall, edges of a generic graph may be of any type. Thus mapping a generic graph is similar to mapping any collection in the Scala standard library. The only difference is that you are free to pass a mapping function for nodes and edges in separate.

Graph(1 ~ 2).map(
  fNode = _.outer + 1,
  fEdge = (n1: Int, n2: Int) => n1 ~> n2
) // Graph(NodeSet(2, 3), EdgeSet(2 ~> 3))

As to

2. Increment node values by 1.
3. Transform any edge to a directed edge.

Flat-map your generic graph

Here is an example for how you would transform directed or undirected edges to two directed edges each while incrementing node values:

Graph(1 ~ 2).flatMap(
  fNode = _.outer + 1 :: Nil,
  fEdge = (n1s: Seq[Int], n2s: Seq[Int]) =>
    (n1s, n2s) match {
      case (Seq(n1, _*), Seq(n2, _*)) => List(n1 ~> n2, n2 ~> n1)
    } // Graph(NodeSet(2, 3), EdgeSet(2 ~> 3, 3 ~> 2))

Map your typed graph

Mapping typed graphs is more complex because you cannot transform the node of a typed edge to an arbitrary type. For instance, having edges like Friends(one: Person, another: Person), you cannot replace Persons with Strings unless you also transform the edge to a type that allows for ends of type String. For this reason we distinguish between two kind of mapping:

1. mapping within your edge ADT, called mapBound, and
2. mapping that is free to escape your edge ADT, called map.

Using the example of a net of flights represented by g, assume that airport hamburg gets closed unexpectedly. Then, you could replace all flights from/to hamburg by flights from/to frankfurt by

g.mapBound((airport: g.NodeT) => if (airport == hamburg) frankfurt else airport)

You could transform the above net of flights to a Graph[String, DiEdge[String]] by

g.map(
  fNode = (airport: g.NodeT) => airport.outer.toString,
  fEdge = (from: String, to: String) => DiEdge(from, to)
)

Note that you need to mix in PartialEdgeMapper into your typed edge class and implement def map[N]: PartialFunction[(N, N), MyEdge] to define how to deal with node mapping with respect to your ADT of edges. If this partial function is not defined for some N, the library will fall back to a built-in edge type.

In the flight example, any mapped Airport yields a new Flight with labels retained by calling copy. Actually, retaining labels is not really meaningful since duration, departure etc. should reflect the new Airports.

Flat-map your typed graph

As an extension of the above mapBound example, suppose that you not only need to replace hamburg by frankfurt but also restrict flights to those having a duration of less than 1 hour:

def ham(flight: Flight): Boolean      = flight.departure == hamburg || flight.destination == hamburg
def shortHam(flight: Flight): Boolean = ham(flight) && flight.duration < 1.hour

g.flatMapBound(
  fNode = (airport: g.NodeT) =>
    (if (airport == hamburg) frankfurt else airport.outer) :: Nil,
  fEdge = (edge: g.EdgeT, newDepartures: Seq[Airport], newDestinations: Seq[Airport]) => {
    val outer = edge.outer
    if (shortHam(outer))
      outer.copy(departure = newDepartures.head, destination = newDestinations.head) :: Nil
    else if (ham(outer)) Nil
    else outer :: Nil
  }
)

To demonstrate an escaping flat map, you could also transform the above net of Flights to a Graph[String, DiEdge[String]] while maintaining the functionality of the previous flatMapBound in one step:

g.flatMap(
  fNode = (airport: g.NodeT) => {
    def existing = airport.outer.toString
    if (airport == hamburg) existing :: frankfurt.toString :: Nil
    else existing :: Nil
  },
  fEdge = (edge: g.EdgeT, from: Seq[String], to: Seq[String]) => {
    val outer = edge.outer
    if (shortHam(outer)) {
      def replaced(a: Airport) = (if (a == hamburg) frankfurt else a).toString
      DiEdge(replaced(outer.departure), replaced(outer.destination)) :: Nil
    } else if (ham(outer)) Nil
    else DiEdge(from.head, to.head) :: Nil
  }
)