hopcroft-karp implemented using dataweave

max-matching.dwl

%dw 2.0
import * from dw::util::Values
var INF = pow(2, 28) //infinity constant
var ARR = (size, value) -> ((0 to size-1) as Array) map value //make it a bit easier to initialize an array

//function for while looping
var while = (conditionFn: (s: Any) -> Boolean, whileFn: (s: Any) -> Any, state = {}) ->
  if (conditionFn(state)) while(conditionFn, whileFn, whileFn(state))
  else state

//build edge map from left side to right side
var getEdges = (left: Array, right: Array, isEdgeFn: (l: Object, r: Object) -> Boolean) ->
  (left reduce ((leftItem, mAccum = { li: 0, edges: [] }) ->
    (right reduce ((rightItem, iAccum = { li: mAccum.li, ri: 0, edges: mAccum.edges }) ->
      {
        li: iAccum.li,
        ri: iAccum.ri + 1,
        edges: iAccum.edges ++ [([iAccum.li, iAccum.ri]) if (isEdgeFn(leftItem, rightItem))]
      }
    )) - "li" ++ { li: mAccum.li + 1 }
  )).edges

//initialize global state object that we will pass around.. since data is immutable
var initializeGlobalState = (left: Array, right: Array, edgeFn: (l: Object, r: Object) -> Boolean) -> do {
  var edges = getEdges(left, right, edgeFn)
  var n = sizeOf(left)
  var m = sizeOf(right)
  ---
  {
    adjN: ((0 to n-1) as Array) reduce (index, arr=[]) -> (arr << ((edges filter $[0] == index) map $[1])),
    adjM: ((0 to m-1) as Array) reduce (index, arr=[]) -> (arr << ((edges filter $[1] == index) map $[0])),
    g1: ARR(n, -1),
    g2: ARR(m, -1),
    dist: ARR(n, INF),
    toVisit: ARR(n, -1),
    dmax: INF,
    matching: 0,
    n: n,
    m: m
  }
}

//entry point function that builds matches
var bipartiteMatching = (left: Array, right: Array, isEdgeFn: (l: Object, r: Object) -> Boolean) ->
  do {
  var globalState = initializeGlobalState(left, right, isEdgeFn)
  var mainLoopResult = (while((s) -> !s.break, mainLoop, { globalState: globalState, break: false})).globalState
  ---
  (((0 to globalState.n-1) as Array) reduce ((i, s = { state: mainLoopResult, matches: []}) ->
    if (s.state.g1[i] < 0) s
    else {
      state: s.state,
      matches: s.matches << [left[i], right[s.state.g1[i]]]
    }
  )).matches
}

//main 'infinite' loop - using break key to terminate
var mainLoop = (state) -> do {
  //initialize a new loopState each time the main loop iterates - utilized by our inner loop
  var loopState = ((0 to state.globalState.n-1) as Array) reduce ((i, s = { globalState: state.globalState, count: 0 }) -> {
    globalState: {
      (s.globalState - "toVisit" - "dist"),
      dist: s.globalState.dist update index(i) with (if (s.globalState.g1[i] < 0) 0 else INF),
      toVisit: if (s.globalState.g1[i] < 0) (s.globalState.toVisit update index(s.count) with i) else s.globalState.toVisit //s.globalState.toVisit (i) if (s.globalState.g1[i] < 0)]
    },
    count: if (s.globalState.g1[i] < 0) (s.count + 1) else s.count
  })

  //inner loop, equivalent to while(ptr < count)
  var innerLoopResult = while((oS) -> oS.ptr < oS.count, (oS) -> do {
    var newPtr = oS.ptr + 1
    var v = oS.globalState.toVisit[oS.ptr]
    var dv = oS.globalState.dist[v]
    ---
    if (dv >= oS.globalState.dmax) { globalState: oS.globalState, count: oS.count, ptr: newPtr }
    else do {
      var adj = oS.globalState.adjN[v]
      ---
      ((0 to sizeOf(adj) - 1) as Array) reduce ((i, s = oS update field("ptr") with newPtr) -> do {
        var u = adj[i]
        var pu = s.globalState.g2[u]
        ---
        if (pu < 0)
          if (s.globalState.dmax == INF) s update ["globalState", field("dmax")] with (dv + 1)
          else s
        else if (s.globalState.dist[pu] == INF) {
          (s - "globalState" - "count"),
          globalState: {
            (s.globalState - "dist" - "toVisit"),
            dist: s.globalState.dist update index(pu) with (dv + 1),
            toVisit: s.globalState.toVisit update index(s.count) with pu
          },
          count: s.count + 1
        }
        else s
      })
    }
  }, (loopState - "ptr" ++ {ptr: 0}) update ["globalState", field("dmax")] with INF)
  ---
  //make sure we're using the result of our loop - this is because we are re-creating the globalState when iterating with changes - this would be easier with mutable data...
  if (innerLoopResult.globalState.dmax == INF) { globalState: innerLoopResult.globalState, break: true }
  else {
    globalState: ((0 to innerLoopResult.globalState.n-1) as Array) reduce ((i, s = innerLoopResult.globalState) -> 
      if (s.g1[i] < 0) do {
        var dfsResult = dfs(s, i)
        ---
        if (!dfsResult.return) dfsResult.globalState
        else dfsResult.globalState update field("matching") with (dfsResult.globalState.matching + 1)
      }
      else s
    ),
    break: false
  }
}

//dfs function
var dfs = (globalState, v) ->
  if (v < 0) { globalState: globalState, return: true }
  else do {
    var adj = globalState.adjN[v]
    var loopResult = while((s) -> !s.break and (s.i < s.max), (s) -> 
      do {
        var u = adj[s.i]
        var pu = s.globalState.g2[u]
        var dpu = if (pu < 0) s.globalState.dmax else s.globalState.dist[pu]
        ---
        if (dpu == (s.globalState.dist[v] + 1)) do {
          var dfsResult = dfs(s.globalState, pu)
          ---
          if (dfsResult.return) do {
            var newGlobalState = {
              (dfsResult.globalState - "g1" - "g2"),
              g1: dfsResult.globalState.g1 update index(v) with u,
              g2: dfsResult.globalState.g2 update index(u) with v
            }
            ---
            { globalState: newGlobalState, break: true, return: true }
          }
          else { globalState: dfsResult.globalState, i: (s.i + 1), max: s.max, break: false }
        }
        else s update "i" with (s.i + 1)
      }, { globalState: globalState, i: 0, max: sizeOf(adj), break: false })
    ---
    if (loopResult.break) { globalState: loopResult.globalState, return: true }
    else { globalState: loopResult.globalState update ["dist", index(v)] with INF, return: false }
  }

Hopcroft-Karp implementation

Example secret santa matching.

Input:

[
  {
    "username": "user1",
    "country": "USA",
    "international": true
  },
  {
    "username": "user2",
    "country": "USA",
    "international": false
  },
  {
    "username": "user3",
    "country": "Sweden",
    "international": true
  }
]

Function call:

bipartiteMatching(payload, payload, (l, r) -> (l.username != r.username) and (l.international or l.country == r.country))

Result:

[
  [
    {
      "username": "user1",
      "country": "USA",
      "international": true
    },
    {
      "username": "user3",
      "country": "Sweden",
      "international": true
    }
  ],
  [
    {
      "username": "user2",
      "country": "USA",
      "international": false
    },
    {
      "username": "user1",
      "country": "USA",
      "international": true
    }
  ],
  [
    {
      "username": "user3",
      "country": "Sweden",
      "international": true
    },
    {
      "username": "user2",
      "country": "USA",
      "international": false
    }
  ]
]