TypeScript implementation of GreedyFAS algorithm (Eades-Lin-Smyth Algorithm)

greedyFas.ts

import { LinkedList } from './LinkedList.ts'
import type { LinkedListNode } from './LinkedList.ts'

interface LinkedVertex<V> {
  value: V
  index: number
  incommings: Set<number>
  outgoings: Set<number>
}

/**
 * When simple directed graph `G = (V, E)` is given, this function returns
 * permutation of `V` which can be applied to approximate minimum feedback arc set.
 * It uses Eades-Lin-Smyth algorithm
 *
 * If you want to find FAS, filter original `E` which vertices counteract the order in returned array.
 *
 * If `V` is object, `edges` must point the references in `vertices`
 *
 * @see https://doi.org/10.1016/0020-0190(93)90079-O
 */
export function greedyFas<V>(vertices: Iterable<V>, edges: Iterable<[V, V]>): V[] {
  const indices: Map<V, number> = new Map()
  const linkedVertices: LinkedVertex<V>[] = []

  let index = 0
  for (const value of vertices) {
    indices.set(value, index)
    linkedVertices.push({
      value,
      index: index++,
      incommings: new Set(),
      outgoings: new Set(),
    })
  }

  // convert vertices into indices
  for (const [from, to] of edges) {
    const fromIndex = indices.get(from)!
    const toIndex = indices.get(to)!
    const fromVertex = linkedVertices[fromIndex]
    const toVertex = linkedVertices[toIndex]

    fromVertex.outgoings.add(toIndex)
    toVertex.incommings.add(fromIndex)
  }

  const sources = new LinkedList<number>()
  const sinks = new LinkedList<number>()
  const diffs = new Map<number, LinkedList<number>>()

  const bucketLinks = new Map<number, LinkedListNode<number>>()

  /**
   * @return if `v` is not source or sink, `outDegree - inDegree`. otherwise `undefined`
   */
  function allocate(v: number): number | undefined {
    const inDegree = linkedVertices[v].incommings.size
    const outDegree = linkedVertices[v].outgoings.size

    if (!inDegree) {
      bucketLinks.set(v, sources.addAfter(v))
      return outDegree
    }
    if (!outDegree) {
      bucketLinks.set(v, sinks.addAfter(v))
      return -inDegree
    }

    const diff = outDegree - inDegree
    if (!diffs.has(diff)) {
      diffs.set(diff, new LinkedList())
    }
    bucketLinks.set(v, diffs.get(diff)!.addAfter(v))
    return diff
  }

  function detachFromNeighbors(v: number): void {
    const bucketLink = bucketLinks.get(v)!
    bucketLink.list.remove(bucketLink)

    for (const u of linkedVertices[v].incommings.values()) {
      linkedVertices[u].outgoings.delete(v)
      linkedVertices[v].incommings.delete(u)

      const uBucketLink = bucketLinks.get(u)!
      uBucketLink.list.remove(uBucketLink)
      allocate(u)
    }

    for (const u of linkedVertices[v].outgoings.values()) {
      linkedVertices[v].outgoings.delete(u)
      linkedVertices[u].incommings.delete(v)

      const uBucketLink = bucketLinks.get(u)!
      uBucketLink.list.remove(uBucketLink)
      allocate(u)
    }
  }

  let maxDiff = -Infinity
  let minDiff = Infinity
  for (let i = 0; i < indices.size; i++) {
    const diff = allocate(i)

    if (diff === undefined) continue

    maxDiff = Math.max(maxDiff, diff)
    minDiff = Math.min(minDiff, diff)
  }

  let listL: number[] = []
  let listR: number[] = [] // reversed
  let vCount = linkedVertices.length

  while (vCount) {
    while (sources.size) {
      const source = sources.end!
      listL.push(source.value)
      detachFromNeighbors(source.value)
      vCount -= 1
    }

    while (sinks.size) {
      const sink = sinks.end!
      listR.push(sink.value)
      detachFromNeighbors(sink.value)
      vCount -= 1
    }

    while (minDiff <= maxDiff && !diffs.get(maxDiff)?.size) {
      maxDiff -= 1
    }

    const diffBucket = diffs.get(maxDiff)
    while (diffBucket?.size) {
      const node = diffBucket.end!
      listL.push(node.value)
      detachFromNeighbors(node.value)
      vCount -= 1
    }
  }

  return listL.concat(listR.reverse()).map((i) => linkedVertices[i].value)
}

LinkedList.ts

export interface LinkedListNode<T> {
  value: T
  prev?: LinkedListNode<T>
  next?: LinkedListNode<T>
  /**
   * Reference to the parent list
   *
   * @note this wont't be erased even detached from the list
   */
  list: LinkedList<T>
  /**
   * Whether this node is removed from the list
   */
  isDetached?: boolean
}

export class LinkedList<T> {
  begin?: LinkedListNode<T>
  end?: LinkedListNode<T>
  size = 0

  addAfter(value: T, at = this.end): LinkedListNode<T> {
    const newNode: LinkedListNode<T> = { value, list: this }

    if (at) {
      newNode.prev = at
      newNode.next = at.next

      if (at.next) {
        at.next.prev = newNode
      } else {
        this.end = newNode
      }

      at.next = newNode
    } else {
      this.begin = newNode
      this.end = newNode
    }
    this.size += 1

    return newNode
  }

  remove(node: LinkedListNode<T>): void {
    if (node.list !== this || node.isDetached) {
      throw new Error('Node does not belong to this list or is already detached')
    }

    if (node.prev) {
      node.prev.next = node.next
    } else {
      this.begin = node.next
    }

    if (node.next) {
      node.next.prev = node.prev
    } else {
      this.end = node.prev
    }

    node.prev = undefined
    node.next = undefined
    this.size -= 1
    node.isDetached = true
  }

  forward(): IterableIterator<T> {
    let current = this.begin
    return {
      [Symbol.iterator](): IterableIterator<T> {
        return this
      },
      next(): IteratorResult<T> {
        if (current) {
          const value = current.value
          current = current.next
          return { value, done: false }
        }
        return { value: undefined, done: true }
      },
    }
  }

  forwardNodes(): IterableIterator<LinkedListNode<T>> {
    let current = this.begin
    return {
      [Symbol.iterator](): IterableIterator<LinkedListNode<T>> {
        return this
      },
      next(): IteratorResult<LinkedListNode<T>> {
        if (current) {
          const value = current
          current = current.next
          return { value, done: false }
        }
        return { value: undefined, done: true }
      },
    }
  }

  backward(): IterableIterator<T> {
    let current = this.end
    return {
      [Symbol.iterator](): IterableIterator<T> {
        return this
      },
      next(): IteratorResult<T> {
        if (current) {
          const value = current.value
          current = current.prev
          return { value, done: false }
        }
        return { value: undefined, done: true }
      },
    }
  }

  backwardNodes(): IterableIterator<LinkedListNode<T>> {
    let current = this.end
    return {
      [Symbol.iterator](): IterableIterator<LinkedListNode<T>> {
        return this
      },
      next(): IteratorResult<LinkedListNode<T>> {
        if (current) {
          const value = current
          current = current.prev
          return { value, done: false }
        }
        return { value: undefined, done: true }
      },
    }
  }

  [Symbol.iterator](): IterableIterator<T> {
    return this.forward()
  }
}

This implements Eades-Lin-Smyth algorithm using double linked list. ELS algorithm approximate the solution of minimum Feedback Arc Set in O(|V| + |E|) time complexity. It guarantees to find at most |E| / 4 size of set for Cubic Graph.

But actually this implementation doesn't find such set directly, rather finds the permutation of vertices, so that it can be used for finding FAS.

Cites: A fast and effective heuristic for the feedback arc set problem

Example

The permutation for this graph is

12, 9, 3,  6, 8,  5, 7, 1, 11, 2, 10, 4

which introduces only one feedback arc (2 -> 11)