Execution Result is different from racket datalog engine

[IWANABETHATGUY]

datalog code

#lang datalog
edge(0, 1). edge(1, 2). edge(2, 3).
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

exec path(A, B)?
I get

path(2, 3).
path(1, 2).
path(0, 1).
path(0, 2).
path(0, 3).
path(1, 3).

rust code

use datafrog::Iteration;

fn main() {
    // Prepare initial values, ..
    let path: Vec<(u32, u32)> = vec![
        (0, 1),
        (1, 2),
        (2, 3), // ..
    ];
    let edges: Vec<(u32, u32)> = vec![
        (0, 1),
        (1, 2),
        (2, 3), // ..
    ];

    // Create a new iteration context, ..
    let mut iteration = Iteration::new();

    // .. some variables, ..
    let path_var = iteration.variable::<(u32, u32)>("path");
    let edges_var = iteration.variable::<(u32, u32)>("edges");

    // .. load them with some initial values, ..
    path_var.insert(path.into());
    edges_var.insert(edges.into());

    // .. and then start iterating rules!
    while iteration.changed() {
        // b: k, a: v1, c: v2 
        // path(a,c)  <-  edges(a,b), path(b,c)
        path_var.from_join(&edges_var, &path_var, |_b, &a, &c| (a, c));
    }

    // extract the final results.
    let reachable = path_var.complete();
    for (a, b) in reachable.iter() {
        println!("({}, {})", a, b);
    }
}

I get

(0, 1)
(1, 1)
(1, 2)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)

[IWANABETHATGUY]

What i did wrong?

[ecstatic-morse]

Variable::from_join takes two inputs, the first is a Variable that holds tuples of type (K, V1), and the second is a Relation that holds tuples of type (K, V2). A join looks for all pairs of tuples in both inputs that share a "key" (a value of type K) and calls the closure for each pair (whose values are of type V1 and V2 respectively).

In your case, the key is the source node for both edges and paths, so your join isn't doing what you want. For example, at the first iteration, it sees that the (0, 1) in path_var and the (0, 1) in edges_var have a shared key (0), and your closure produces the combination of their values (1, 1). Repeating this process will give the same result as datafrog does.

What you actually want is to make the shared key the source of one of the lists and the target of the other. You'll need to reverse one of the relations, probably edges, to get this behavior.

[IWANABETHATGUY]

Variable::from_join takes two inputs, the first is a Variable that holds tuples of type (K, V1), and the second is a Relation that holds tuples of type (K, V2). A join looks for all pairs of tuples in both inputs that share a "key" (a value of type K) and calls the closure for each pair (whose values are of type V1 and V2 respectively).

In your case, the key is the source node for both edges and paths, so your join isn't doing what you want. For example, at the first iteration, it sees that the (0, 1) in path_var and the (0, 1) in edges_var have a shared key (0), and your closure produces the combination of their values (1, 1). Repeating this process will give the same result as datafrog does.

What you actually want is to make the shared key the source of one of the lists and the target of the other. You'll need to reverse one of the relations, probably edges, to get this behavior.

Thanks!