Floyd-Warshall

[lukem12345]

The Floyd-Warshall algorithm can be defined on the variables of a Decapode. This entails a topological ordering of those variables. A topological ordering of operations is given in turn.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 67.74194% with 30 lines in your changes missing coverage. Please review.

Project coverage is 82.49%. Comparing base (2a6269c) to head (a93295a).

Files with missing lines	Patch %	Lines
src/graph_interface.jl	64.06%	23 Missing :warning:
src/acset2symbolic.jl	75.86%	7 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## gr/acset2sym #70 +/- ## ================================================ - Coverage 84.37% 82.49% -1.89% ================================================ Files 15 15 Lines 960 1011 +51 ================================================ + Hits 810 834 +24 - Misses 150 177 +27 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[lukem12345]

Commit d46cf86 added both docstrings and introduced a multiple dispatch scheme by subtyping TraversalNode. The MD scheme can be undone depending on design constraints I’m not aware of. This results in cleaner algorithm code

[lukem12345]

It would be a fun project to investigate whether and how this can be framed in terms of an “Algebraic Path Problem”.[1,2]

[1] https://drops.dagstuhl.de/storage/00lipics/lipics-vol211-calco2021/LIPIcs.CALCO.2021.20/LIPIcs.CALCO.2021.20.pdf [2] https://edge.edx.org/asset-v1:BerkeleyX+CS188-SU16+SU16+type@asset+block/kleene_algebras_path_problems.pdf

[lukem12345]

@GeorgeR227 The overarching purpose of this PR to demonstrate how to transform Decapode into a well-known data structure, i.e. a graph, at which point we can use generic traversal algorithms. Not bespoke or manually-inlined traversal algorithms over the bespoke SummationDecapode data structure. To wit, compare the Floyd-Warshall algorithm as implemented here with the pseudocode given for it on Wikipedia. The choice of Floyd-Warshall vs. multi-start Dijkstra's vs. Kuhn's and so on is somewhat beside the point, but of course time and space complexity, weighed against the average size of our datastructures (< 1000 vertices), are to be weighed against maintainability before such a PR is merged. Treat it as a proof of concept for the time being.

[GeorgeR227]

I get your idea about make our hypergraph algorithms more generic. I think many people have wanted that and I do want to keep those parts of this PR.

What I don't get is the decision to base everything on Floyd-Warshall. If F-W can be made into a generic hypergraph algorithm, then why can't topological sort? The implementation was almost there, it just needed the concept of the generic edge (which you implemented here) plus a bit of other functionality probably.

My main idea here is that the decision to use F-W makes this code less scalable/performant, less readable (since this is no longer the standard topological sort algorithm most people are familiar with) and less maintainable (because now we have graph algorithms which depend on other graph algorithms when there's no reason they have to).

I like the push towards going generic (even though that wasn't the explicit push of the branch this is based off) and I don't even mind the inclusion of F-W but it should not be used in the topological sort.

[lukem12345]

We're on the same page

[lukem12345]

@GeorgeR227 The most recent commit needs to use git mv. We shouldn't delete files and place their contents in new files.

[GeorgeR227]

Yeah I can do that. Any thoughts on the generic HyperGraph?

[lukem12345]

We should probably just switch to using an incidence matrix. Also accommodates arguments of arbitrary arity. In Decapodes then just "dispatch"/ switch/ pattern-match on arity and name of symbol. Restricting operations to unary ops, binary ops, and sums is no longer is a necessary design constraint.

[lukem12345]

Or just use this schema, migration or otherwise. Nodes are rows in the Var table. Edges are cached calls to

(dom = d[incident(d,i,:arg_op),:arg_var], cod = d[i,:res], op = function[i])

@schema SchVariadicDecapode begin # SchHyperGraph
  Var::Ob
  (Type, VarName, Operator)::AttrType(Symbol)
  type::Attr(Var, Type)
  name::Attr(Var, Name)

  (Op, Argument)::Ob
  (Function)::AttrType(Symbol)
  function::Attr(Op, Function)
  arg_var::Hom(Argument, Var)
  arg_op::Hom(Argument, Op)
  res::Hom(Op, Var)
end