Package it.unimi.dsi.webgraph.labelling

Interface LabelSemiring

public interface LabelSemiring
A semiring used to compose labels.

When composing two labelled graphs, we need a way to combine labels along a path, and a way to combine labels from different paths connecting two nodes. These two operations are implemented by multiply(Label, Label) and add(Label, Label). The name of the two methods are due to the fact that their operations must define a semiring for which you must also provide a zero() and a one(). For instance, if a graph is labelled with weights, a semiring implementing multiply(Label, Label) by a standard sum and add(Label, Label) using the minimum operator will give a composition strategy that computes the shortest path connecting two nodes.

Usually, strategies require that the two labels provided are of the same kind (i.e., instances of the same Label class). Moreover, some strategies only accept label of a certain type, and throw an IllegalArgumentException if the type is wrong.

  • Method Details

    • multiply

      Label multiply​(Label first, Label second)
      Multiply two given labels; either label may be null, but not both. Implementing classes may decide to throw an IllegalArgumentException if the labels provided are not of the same type, or not of a specific type.
      Parameters:
      first - the first label to be multiplied.
      second - the second label to be multiplied.
      Returns:
      the resulting label (note that the returned label may be reused by the implementing class, so users are invited to make a Label.copy() of it if they need to keep the label in between calls).

    • add

      Label add​(Label first, Label second)
      Adds two given labels; either label may be null, but not both. Implementing classes may decide to throw an IllegalArgumentException if the labels provided are not of the same type, or not of a specific type.
      Parameters:
      first - the first label to be added.
      second - the second label to be added.
      Returns:
      the resulting label (note that the returned label may be reused by the implementing class, so users are invited to make a Label.copy() of it if they need to keep the label in between calls).

    • zero

      Label zero()
      Returns the zero of add(Label, Label).
      Returns:
      the zero of add(Label, Label).

    • one

      Label one()
      Returns the one of multiply(Label, Label).
      Returns:
      the one of multiply(Label, Label).