I wanted to calculate topological sort given a few predicates asserting that one element should be before another in a sequence. order(a, b) means that a should go before b.
I ended up implementing Kahn's algorithm:
pop_dict(Key, DictIn, Value, DictOut) :-
Value = DictIn.Key,
del_dict(Key, DictIn, _, DictOut).
pop_dict(Key, DictIn, Value, Default, DictOut) :-
get_dict(Key, DictIn, V)
->
Value = V,
del_dict(Key, DictIn, _, DictOut)
;
Value = Default,
DictOut = DictIn.
graph_init([], OutDegree, OutDegree, InEdges, InEdges).
graph_init([(A, B)|Order], OutDegree, OutDegreeOut, InEdges, InEdgesOut) :-
ANewDegree is OutDegree.get(A, 0) + 1,
BNewDegree is OutDegree.get(B, 0),
NewOutDegree = OutDegree.put(B, BNewDegree).put(A, ANewDegree),
BNewEdges = [A|InEdges.get(B, [])],
NewInEdges = InEdges.put(B, BNewEdges),
graph_init(Order, NewOutDegree, OutDegreeOut, NewInEdges, InEdgesOut).
graph_init(Order, OutDegreeOut, InEdgesOut) :-
graph_init(Order, _{}, OutDegreeOut, _{}, InEdgesOut).
outdegree_remove(OutDegree, [], OutDegree).
outdegree_remove(OutDegree, [B|Neighbours], OutDegreeOut) :-
BNewDegree is OutDegree.B - 1,
NewOutDegree = OutDegree.put(B, BNewDegree),
outdegree_remove(NewOutDegree, Neighbours, OutDegreeOut).
toposort(_{}, _{}, Items, Items).
toposort(OutDegree, InEdges, Items, ItemsOut) :-
pop_dict(A, OutDegree, 0, OutDegreeTrimmed),
pop_dict(A, InEdges, Neighbours, [], NewInEdges),
outdegree_remove(OutDegreeTrimmed, Neighbours, NewOutDegree),
NewItems = [A|Items],
toposort(NewOutDegree, NewInEdges, NewItems, ItemsOut).
toposort(Order, Items) :-
graph_init(Order, OutDegree, InEdges),
toposort(OutDegree, InEdges, [], Items).
order(1, 2).
order(3, 4).
order(5, 6).
order(5, 7).
order(5, 8).
order(5, 9).
order(2, 6).
order(8, 10).
order(9, 4).
order(10, 6).
order(10, 9).
order(11, 6).
order(11, 2).
order(11, 10).
?- bagof((A, B), order(A, B), Order), toposort(Order, Items), portray_clause(Items).
Now, I'm wondering whether it would be possible to implement topological sort more easily and with less code. I'm not very concerned about performance as long as it's still instant for the example data in the code (iterating all permutations would be too slow).
