TypeScript implementation of finding greatest element in partially ordered set.

findGreatestElement.ts

export type Relation = [string, string]

function makeGraph(relations: Relation[]): Record<string, string[]> {
    const result: Record<string, string[]> = {}
    relations.forEach(([u, v]) => {
        (result[u] ??= []).push(v)
        result[v] ??= []
    })
    return result
}

export function findGreatest(relations: Relation[]): string | null {
    const graph = makeGraph(relations)
    const nodes = Object.keys(graph)
    const zeroOutNodes = nodes.filter(u => graph[u].length === 0)

    if (zeroOutNodes.length !== 1) return null
    
    const dup: Record<string, 'analyzing' | 'resolved'> = {}
    
    function isLoopExists(node: string): boolean {
        if (dup[node] === 'analyzing') return true
        if (dup[node] === 'resolved') return false
        dup[node] = 'analyzing'
        const isLoop = graph[node].reduce((isLoop, child) => isLoop || isLoopExists(child), false)
        dup[node] = 'resolved'
        return isLoop
    }

    if (nodes.reduce((isLoop, node) => isLoop || isLoopExists(node), false)) return null
    
    return zeroOutNodes[0]
}

Find unique greatest element in partially ordered set. If there is no such element, it returns null.

Example

For example, let's assume some inequalities between variables.

a < b
b < c
a < d
c < e
d < e

In this example, the maximum variable is e.

Time Complexity

It's just simple DFS, so O(V + E)