1
$\begingroup$

TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of other unusual weights.

I also considered to ask this question on Mathematics Stack Exchange since it also contains significant portion of abstract algebraic aspect, but I decided to just post it here.

I've once tried solving a programming problem where, given a list of is-a and has-a relationships in an object-oriented program, one should determine what relationships given pairs of classes are in. According to the problem statement, for every triplet of classes A, B, and C:

  • Is-a is transitive: A is-a C if A is-a B and B is-a C.
  • Has-a is transitive: A has-a C if A has-a B and B has-a C.
  • Is-a is reflexive: A is-a A always holds.
  • A has-a C if A is-a B and B has-a C, or A has-a B and B is-a C.
  • No cycles of is-a relationship exist. We'll ignore this restriction for the purpose of this question.

My solution involved a modified Floyd-Warshall algorithm where:

  • There are four possible edge weights: only is-a, only has-a, both is-a and has-a, and neither is-a nor has-a (written as $i$, $h$, $ih$, $0$, respectively, from now on).
    • These "weights" are partially ordered: $0$ is greater than both $i$ and $h$, which are in turn greater than $ih$; $i$ is not comparable to $h$.
  • dist[i][j] is initialized with $0$ (instead of infinity) if i != j, or $i$ (instead of zero) otherwise.
  • The "inherit" and order-theoretic "meet" operator replaces addition and minimum, respectively.

The "inherit" operator can be thought to encapsulate the preceding transitivity properties, and is defined by the following table:

$0$ $i$ $h$ $ih$
$0$ $0$ $0$ $0$ $0$
$i$ $0$ $i$ $h$ $ih$
$h$ $0$ $h$ $h$ $h$
$ih$ $0$ $ih$ $h$ $ih$

As you can see, this algorithm handles weights that are non-numerical, and not even totally ordered; yet it seems like it runs just fine, and it got my submission accepted! Since then, I always wondered why these unusual weights didn't invalidate the algorithm, and moreover, what kind of weight sets are acceptable.

More specifically, when it comes to regular integers and real numbers, Floyd-Warshall algorithm is known to handle all graphs with nonnegative weights, and even some graphs that contains negative weight, but not those with negative cycles. This is what I am interested in: which sets of mathematical objects and operators disallow something that correspond to "negative cycles", thus compatible with the algorithm?

Currently I assume that they should be at least meet-semilattices, which generalizes the notion and minimum operator and shortest paths, and also monoids, which generalizes the notion of adding multiple segments of paths together.

I've thought of a number of additional hypotheses, but I couldn't verify any of them correct:

  • No elements compare less than additional identity.
    • Counterexample: In the above example, $i$ is the "inheritancial identity", with $ih$ less than it. We've already seen that this one works nevertheless.
  • No "infinite descent" sequence $A$ exists, where $A_1 > A_1 + A_2 > A_1 + A_2 + A_3 > \cdots$.
  • For every pair of elements $a$ and $b$, $a + b \ge min(a, b)$.
  • There exists a greatest lower bound for every set of elements.

Partial order especially makes the analysis harder, because the result of minimum operator is no longer necessarily equal to any of its operands, thus "splitting" the path. Again with the above example, if A is-a B, A has-a C, B is-a D, and C is-a D, then according to the properties of these relationships, both A is-a D and A has-a D holds; the paths A-B-D and A-C-D both contribute to this shortest path length $ih$, and if we were to cut any of these, the "length" between A and D would be farther.

$\endgroup$

2 Answers 2

0
$\begingroup$

I'm not an expert on this, so I recommend you double-check my conclusions, but I believe you can compute all-pairs shortest paths using a generalization of the Floyd Warshall algorithm, for any objects and operators that form a closed semiring (also known as a star semiring). See, e.g., the following papers:

Semiring Frameworks and Algorithms for Shortest-Distance Problems. Mehryar Mohri. Journal of Automata, Languages and Combinatorics, 7(3):321-350, 2002.

A Systolic Array Algorithm for the Algebraic Path Problem (Shortest Paths; Matrix Inversion). Computing 34 (1985), pp. 191-219.

Path Problems in Graphs, Günter Rote. Computing Supplementum 7 (1990), pp. 155-189.

Transitive closure and related semiring properties via eliminants. S. Kamal Abdali, B. David Saunders. Theoretical Computer Science 40 (1985): 257-274.

Algebraic Structures for Transitive Closure. Daniel J. Lehmann. Theoretical Computer Science, 4 (1977), pp. 59–76.

It's possible you might find more references under the names "algebraic path problem" or "algebraic shortest paths".

$\endgroup$
0
$\begingroup$

Self-answer: after a follow-up research on my own, I discovered that, while my is-a & has-a weights do form a star semiring with idempotent meet operator, Floyd-Warshall algorithm does not work because it does not take cycles into account.

If I understood it correctly, Floyd-Warshall algorithm is only valid if paths with cycles are never shorter than ones without them: in other words, $x \le x^*$. In my case, there was a counterexample to this, namely $h \nleq h^* = ih$.

I've currently requested an additional test case to the original problem page; if the request is accepted, my submissions will be rejected as expected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.