[[tq:ug:tq]]

Temporal quantities

Besides the presence/absence of nodes and links also their properties can change through time. To describe the changes we introduce the notion of a temporal quantity a with the activity set Ta ⊆ T

a'(t) = a(t) when t ∈ Ta, and a'(t) = ⌘ otherwise.

where a(t) is the value of a at an instant t, and ⌘ denotes the value undefined. In the following we will assume that a temporal quantity is extended in this way and we will use simply a to denote it.

We assume that the values of temporal quantities belong to a set A which is a semiring (A,⊕,⊙,0,1) for binary operations ⊕ : A✕A ⇢ A and ⊙ : A✕A ⇢ A \citep{GoMi,semi}. This means that (A,⊕,0) is an Abelian monoid - the addition ⊕ is associative and commutative, and has 0 as its neutral element; and (A,⊙,1) is a monoid - the multiplication ⊙ is associative and has 1 as its neutral element. Also, multiplication distributes from both sides over the addition.

Note that 0 and 1 denote the two elements of A that satisfy the required properties. In expressions the precedence of the multiplication ⊙ over the addition ⊕ is assumed. We can extend both operations to the set A = A ⋃ { ⌘ } by requiring that for all a ∈ A it holds

a ⊕ ⌘ = ⌘ ⊕ a = a and a ⊙ ⌘ = ⌘ ⊙ a = ⌘ .

The structure (A, ⊕, ⊙, ⌘, 1) is also a semiring.

The standard references on semirings are \cite{GaN} and \cite{GoMi}.

Basic semirings

Combinatorial semiring

The “default” semiring is the combinatorial semiring (ℝ0+, +, ∙, 0, 1) where + and ∙ are the usual addition and multiplication of real numbers.

In applications of semirings in the analysis of graphs and networks the addition ⊕ describes the composition of values on parallel walks and the multiplication ⊙ describes the composition of values on sequential walks

For the combinatorial semiring these two schemes correspond to basic principles of combinatorics: the Rule of Sum and the Rule of Product \citep{comb}.

In some applications other semirings are useful.

Shortest paths semiring

The semiring (ℝ*, min, +, ∞, 0), where ℝ* = ℝ0+ ⋃ {∞}, is suitable to deal with the shortest paths problem in networks.

Reachability semiring

The semiring ({0, 1}, ⋁, ⋀, 0, 1) is used in solving reachability problems.

Max-min semiring

The semiring (ℝ, max, min, -∞, ∞)

In the following we shall use also the PathFinder semiring and geodetic semiring.

Basic semirings in the TQ library

A default basic semiring is the combinatorial semiring. The current basic semiring operations ⊕ and ⊙ are in the TQ library available as functions sAdd(a,b) and sMul(a,b). The current basic semiring is changed by one of the functions combinatorial(), path(), maxmin(), reach(), PFsemi() and geodetic(). Data about the current semiring are displayed using the function report().

>>> TQ.report()

semiring =  combinatorial
mult  =  mul
sZero =  0
sOne  =  1
sN    =  []
sE    =  [(1, inf, 1)]
rPF   =  2

7
>>> TQ.sMul(3,4)
12
>>> TQ.PFsemi()
3
>>> TQ.sMul(3,4)
5.0
>>> TQ.report()

semiring =  PFsemi
mult  =  pitagora
sZero =  inf
sOne  =  0
sN    =  []
sE    =  [(1, inf, 0)]
rPF   =  2

>>> TQ.semiring
<function TQ.PFsemi at 0x00000000036F1730>
>>> TQ.sZero
inf
>>> TQ.inf+7
inf
>>> TQ.inf*TQ.inf
inf
>>>

Semiring of temporal quantities

Let A(T) denote the set of all temporal quantities over A in the time T. To extend the operations to networks and their matrices we first define the sum a ⊕ b (parallel links) as

(a ⊕ b)(t) = a(t) ⊕ b(t) and Ta⊕b = Ta ⋃ Tb;

and the product a ⊙ b (sequential links) as

(a ⊙ b)(t) = a(t) ⊙ b(t) and Ta⊙b = Ta ⋂ Tb.

In these definitions and also in the following text, to avoid the `pollution' with many different symbols, we use the symbols ⊕ and ⊙ to denote the semiring operations. The appropriate semiring can be determined from the context. For example, in the definition of addition of temporal quantities the symbol ⊕ on the left hand side of the equation operates on temporal quantities and the symbol ⊕ on the right hand side denotes the addition in the basic semiring A.

Let us define the temporal quantities 0 and 1 with requirements 0(t) = ⌘ and 1(t) = 1 for all t ∈ T. It is a routine task to verify that the structure (A(T), ⊕, ⊙, 0, 1) is also a semiring, and therefore so is the set of square matrices of order n over it for the addition AB = S

sij = aij ⊕ bij

and multiplication AB = P

pij = ⊕{k∈1:n : aik ⊙ bkj} .

Again, the symbols ⊕ and ⊙ on the left hand side operate on matrices and on the right hand side in the semiring of temporal quantities.

The matrix multiplication is closely related to traveling on networks. Consider an entry pij in an instant t

pij(t) = ⊕{k∈1:n : aik(t) ⊙ bkj(t)} .

For a value pij to be defined (different from ⌘) there should exist in the instant t at least one node k such that both the link (i,k) and the link (k,j) exist - the transition from the node i to the node j through a node k is possible. Its contribution is aik(t) ⊙ bkj(t). This means that the matrix multiplication is taking into account only the links inside the time slice N(t).

Operationalization

In the following we shall limit our discussion to temporal quantities that can be described in the form of time-interval/value sequences

a = ( (Ii, vi) )i∈1:k

where Ii is a time-interval and vi is a value of a on this interval. In general, the intervals can be of different types: 1 - [si, fi]; 2 - [si, fi); 3 - (si, fi]; 4 - (si, fi). Also the value vi can be structured. For example vi = (wi, ci, τi) - weight, capacity and transition time, or vi = (di, ni) - the length of geodesics and the number of geodesics, etc. We require si ≤ fi, for i∈1:k and si-1 < si, for i∈2:k.

To simplify the exposition we will assume in the following that all the intervals in our descriptions of temporal quantities are of type 2 - [si, fi) and fi-1 ≤ si, for i∈2:k. Therefore we can describe the temporal quantities with sequences of triples

a = ( (si, fi, vi) )i∈1:k .

In the examples we will also assume that T = [tmin, tmax] ⊆ ℕ.

To provide a computational support for the proposed approach we are developing in Python a library TQ (Temporal Quantities). In the examples we will use the Python notation for temporal quantities.

The following are two temporal quantities a and b represented in Python as a list of triples

a = [(1, 5, 2), (6, 8, 1), (11, 12, 3), (14, 16, 2), (17, 18, 5), (19, 20, 1)]
b = [(2, 3, 4), (4, 7, 3), (9, 10, 2), (13, 15, 5), (16, 21, 1)]

The temporal quantity a has on the interval [1,5) value 2, on the interval [6,8) value 1, on the interval [11,12) value 3, etc. Outside the specified intervals its value is undefined, ⌘.

The temporal quantities can also be visualized as it is shown for a and b at the top half of the following figure:

Addition and multiplication of temporal quantities.

For the simplified version of temporal quantities we wrote procedures sum for the addition and prod for the multiplication of temporal quantities over the selected semiring. Because, by assumption, the triples in a description of a temporal quantity are ordered by their starting times, we can base both procedures on the ordered lists merging scheme. The basic semiring operations of addition and multiplication are provided by functions sAdd and sMul.

The following are the sum s and the product p of temporal quantities a and b.

s = [(1, 2, 2), (2, 3, 6), (3, 4, 2), (4, 5, 5), (5, 6, 3),
(6, 7, 4), (7, 8, 1), (9, 10, 2), (11, 12, 3), (13, 14, 5),
(14, 15, 7), (15, 16, 2), (16, 17, 1), (17, 18, 6),
(18, 19, 1), (19, 20, 2), (20, 21, 1)]
p = [(2, 3, 8), (4, 5, 6), (6, 7, 3), (14, 15, 10), (17, 18, 5),
(19, 20, 1)]

They are visually displayed at the bottom half of the figure.

The function len(a) returns the length (number of items) of the list a. The function standard(a) joins, in the list a, adjacent time intervals with the same value into a single interval.

>>> TQ.combinatorial()
>>> a = [(1, 5, 2), (6, 8, 1), (11, 12, 3), (14, 16, 2), (17, 18, 5), (19, 20, 1)]
>>> b = [(2, 3, 4), (4, 7, 3), (9, 10, 2), (13, 15, 5), (16, 21, 1)]
>>> s = TQ.sum(a,b)
>>> s
[(1, 2, 2), (2, 3, 6), (3, 4, 2), (4, 5, 5), (5, 6, 3), (6, 7, 4),
(7, 8, 1), (9, 10, 2), (11, 12, 3), (13, 14, 5), (14, 15, 7), (15, 16, 2),
(16, 17, 1), (17, 18, 6), (18, 19, 1), (19, 20, 2), (20, 21, 1)]
>>> p = TQ.prod(a,b)
>>> p
[(2, 3, 8), (4, 5, 6), (6, 7, 3), (14, 15, 10), (17, 18, 5), (19, 20, 1)]
>>> len(p)
6
>>> c = [(1, 2, 2), (2, 3, 2), (4, 6, 2), (6, 8, 2)]
>>> TQ.standard(c)
[(1, 3, 2), (4, 8, 2)]
>>>

Growth of the size of temporal quantities

Let la = len(a) and lb = len(b). Then, assuming that the semiring operations take constant time each, the time complexity of both algorithms is O(la+lb). The following example

shows that in extreme cases the sum can be almost 4 times longer than each of its arguments, and the product almost twice as long as the arguments. If T = [tmin, tmax] ⊆ ℕ the length of a list describing a temporal quantity can not exceed L = tmax - tmin.

The aggregated value

In some applications over the combinatorial semiring we shall use the aggregated value of a temporal quantity a = ( (si, fi, vi) )i∈1:k . It is defined as

∑a = ∑{i∈1:k : (fi-si) ∙ vi }

and is computed using the procedure total. For example ∑a = 23 and ∑b = 30. Note that ∑a + ∑b = ∑(a+b).

>>> a = [(1, 5, 2), (6, 8, 1), (11, 12, 3), (14, 16, 2), (17, 18, 5), (19, 20, 1)]
>>> TQ.total(a)
23
>>>

Temporal networks and partitions

We obtain a more adequate description of temporal networks by using vectors of temporal quantities (temporal vectors and temporal partitions) for describing properties of nodes and making also link weights into temporal quantities. In the current version of the library TQ we use a representation of a network N with its matrix A = [auv]

auv = w(u,v) if (u,v) ∈ L; and ⌘ otherwise

where w(u,v) is a temporal weight attached to a link (u,v).

The description of temporal partitions has the same form as the description of temporal quantities a = ( (si, fi, vi) )i∈1:k. They differ only in the interpretation of values vi ∈ ℕ. In case of partitions vi = j means that the unit described with a belongs to a class j in the time interval [si,fi). We shall use temporal partitions to describe connectivity components in Section~\ref{conn}.

TQ User guide <<< >>> 