Issue #7 resolved

hashtag_optimized finds a path, but not the shortest one

Pierre Carbonnelle
repo owner created an issue

Since version 0.14.1, hashtag_optimized.py finds a possible path, but not the shortest one anymore. It may also issue a MemoryError before finding a possible path.

This is due to a change of execution logic in the resolver (from breadth-first, to depth-first.

Comments (3)

  1. Pierre Carbonnelle reporter

    Before version 0.14.1, the clauses defining a predicate were evaluated in parallel, using a breadth-first resolution. A graph was thus naturally explored using Dijkstra's algorithm to find the shortest path.

    This approach created problems with clauses defining a function : to be able to implement expert systems, we want the clause defined last to be evaluated fully first, before evaluating the clause next in priority. Commit 818d6df was done to enable this, using a depth-first approach. This broke the hashtag_optimized solution.

    I have tried in the last months to mix depth-first for functional clauses and breadth-first for regular clauses, but I was not happy with the result. I now believe that a good solution would be to use second-order logic, and define special predicates like

    graph.shortest_path(from: X, to: Y, via: Path, over: Relation)
    

    "Relation" would be the name of a predicate, e.g. "link", for link(X,Y).

    The pyDatalog engine would have a library of graph predicates, and use breadth first to resolve them.

  2. Log in to comment