flix
feat: add Datalog-based Ford-Fulkerson algorithm
Just a dump of functions... (note to self)
mod Graph {
use Path.Path;
enum Path {
case Path(List[Int32])
}
instance Eq[Path] {
pub def eq(x: Path, y: Path): Bool =
let Path(xs) = x;
let Path(ys) = y;
List.length(xs) == List.length(ys)
}
instance Order[Path] {
pub def compare(x: Path, y: Path): Comparison =
let Path(xs) = x;
let Path(ys) = y;
if (List.length(xs) == List.length(ys))
Comparison.EqualTo
else if (List.length(xs) <= List.length(ys))
Comparison.GreaterThan
else
Comparison.LessThan
}
instance LowerBound[Path] {
// The longest list
pub def minValue(): Path = Path(List.range(1, 100))
}
instance PartialOrder[Path] {
pub def lessEqual(x: Path, y: Path): Bool =
let Path(xs) = x;
let Path(ys) = y;
List.length(xs) >= List.length(ys)
}
instance JoinLattice[Path] {
pub def leastUpperBound(x: Path, y: Path): Path =
let Path(xs) = x;
let Path(ys) = y;
if (List.length(xs) <= List.length(ys)) x else y
}
instance MeetLattice[Path] {
pub def greatestLowerBound(x: Path, y: Path): Path = ???
}
pub def init(y: Int32, x: Int32): Path =
Path(y :: x :: Nil)
pub def cons(z: Int32, p: Path): Path = match p {
case Path(xs) => Path(z :: xs)
}
// Consider returning just Int32
// Maybe generalize Constraint and Flow to typeclass so it can be both floats and ints
type alias Constraint = Int32
type alias Flow = Int32
pub def maxFlow(g: m[(t, t, Constraint)]): Option[Flow] with Foldable[m], Order[t] = ???
def nodesWeighted(): #{ Edge(t, t, Constraint), Node(t) | r } with Order[t] = #{
Node(x) :- Edge(x, _, _).
Node(x) :- Edge(_, x, _).
}
pub def paths(src: { src = t }, dst: { dst = t }, g: m[(t, t)]): List[t] with Foldable[m], Order[t] =
let edges = inject g into Edge;
let rules = #{
Reach(x, y; init(y, x)) :- Edge(x, y).
Reach(x, z; cons(z, p)) :- Reach(x, y; p), Edge(y, z).
};
let result = query edges, rules select fn from Reach(src, dst; fn);
Vector.get(0, result)
pub def fordFulkerson(): #{ Edge(t, t, Constraint), Node(t), Flow(Flow) | r } with Order[t] = ???
pub def fordFulkersonNetwork(g: m[(t, t, Constraint)]): Set[(t, t, Flow)] with Foldable[m], Order[t] = ???
pub def flowValue(g: m[(t, t)]): Int32 with Foldable[m], Order[t] = ???
pub def source(g: m[(t, t)]): Option[t] with Foldable[m], Order[t] = ???
pub def hasSource(g: m[(t, t)]): Bool with Foldable[m], Order[t] = ???
pub def hasSink(g: m[(t, t)]): Bool with Foldable[m], Order[t] = ???
pub def sink(g: m[(t, t)]): Option[t] with Foldable[m], Order[t] = ???
pub def isSTNetwork(g: m[(t, t)]): Bool with Foldable[m], Order[t] = ???
}
@magnus-madsen maybe you should take a look at what I have so far. I have a feeling that the main loop fordFulkerson can be prettier by using datalog. Other than that I have a todo to handle the residual network properly.
Apart from restructuring and bug fixing, what do you think of this? I'm not sure it terminates currently.
The algorithm works now. I will move it to an example file, but feedback on style etc. would be nice.
My comments from earlier are still relevant they are just not in the rightplace anymore.
I should preface everything by saying that I want to use this example in a paper. So while I think this is pretty good style, I will be proposing some simplifications to make it fit :)
I just want to say this looks like a really nice example 👍
I am very happy with the attention to detail and the graphs :)
It seems the changes to Path broke everything. Maybe you want to take another look :/
Updating tests, then we are ready (forgot to update from (t, t, Int32, Int32) to (t, Int32, Int32, t)).