Table of Contents

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 *T*_{a} ⊆ T

a'(t) = a(t) when t ∈ *T*_{a}, 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}.

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.

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

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

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

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

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 add = add mult = mul sZero = 0 sOne = 1 sN = [] sE = [(1, inf, 1)] rPF = 2 >>> TQ.sAdd(3,4) 7 >>> TQ.sMul(3,4) 12 >>> TQ.PFsemi() >>> TQ.sAdd(3,4) 3 >>> TQ.sMul(3,4) 5.0 >>> TQ.report() semiring = PFsemi add = min 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 >>>

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 T_{a⊕b} = T_{a} ⋃ T_{b};

and the **product** a ⊙ b (sequential links) as

(a ⊙ b)(t) = a(t) ⊙ b(t) and T_{a⊙b} = T_{a} ⋂ T_{b}.

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** **A** ⊕ **B** = **S**

s_{ij} = a_{ij} ⊕ b_{ij}

and **multiplication** **A** ⊙ **B** = **P**

p_{ij} = ⊕{k∈1:n : a_{ik} ⊙ b_{kj}} .

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 p_{ij} in an instant t

p_{ij}(t) = ⊕{k∈1:n : a_{ik}(t) ⊙ b_{kj}(t)} .

For a value p_{ij} 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 a_{ik}(t) ⊙ b_{kj}(t). This means that the matrix multiplication is taking into account only the links inside the time slice **N**(t).

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

a = ( (I_{i}, v_{i}) )_{i∈1:k}

where I_{i} is a time-interval and v_{i} is a value of a on this interval. In general, the
intervals can be of different types: 1 - [s_{i}, f_{i}];
2 - [s_{i}, f_{i}); 3 - (s_{i}, f_{i}]; 4 - (s_{i}, f_{i}). Also the value v_{i} can be structured. For example v_{i} = (w_{i}, c_{i}, τ_{i}) - weight, capacity and transition time, or v_{i} = (d_{i}, n_{i}) - the length of geodesics and the number of geodesics, etc. We require s_{i} ≤ f_{i}, for i∈1:k and s_{i-1} < s_{i}, 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 - [s_{i}, f_{i}) and f_{i-1} ≤ s_{i}, for i∈2:k. Therefore we can describe the temporal quantities with sequences of triples

a = ( (s_{i}, f_{i}, v_{i}) )_{i∈1:k} .

In the examples we will also assume that **T** = [t_{min}, t_{max}] ⊆ ℕ.

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)] >>>

Let l_{a} = len(a) and l_{b} = len(b). Then, assuming that the semiring operations take constant
time each, the time complexity of both algorithms is O(l_{a}+l_{b}).
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 = [t_{min}, t_{max}] ⊆ ℕ the length of a list describing a
temporal quantity can not exceed L = t_{max} - t_{min}.

In some applications over the combinatorial semiring we shall use the **aggregated value** of a temporal
quantity a = ( (s_{i}, f_{i}, v_{i}) )_{i∈1:k} . It is defined as

∑a = ∑{i∈1:k : (f_{i}-s_{i}) ∙ v_{i} }

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 >>>

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** = [a_{uv}]

a_{uv} = 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 = ( (s_{i}, f_{i}, v_{i}) )_{i∈1:k}.
They differ only in the interpretation of values v_{i} ∈ ℕ. In case
of partitions v_{i} = j means that the unit described with a belongs
to a class j in the time interval [s_{i},f_{i}). We shall use temporal partitions
to describe connectivity components in Section~\ref{conn}.

TQ User guide <<< >>>

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported