Алгоритм подготовки, обработки и преобразования данных для потоковых задач

Представлением сети называется набор констант, списков и матриц для отображения сети и всех ее параметров. Имеется два способа представления сети:

1)  на основании списка дуг

2)   на основании списка узлов

 Первый

О=[O_k], T=[t_k]-два множества. Легко определить начальные и конечные узлы как к- элементы  в списках  O и T, а параметры определяются  как f_k и C_k.

Рисунок 19. Пример сети

Для списка дуг составляют таблицу

Вводится дополнительный список длиной n, который является списком начальных указателей. Элементы будут нумероваться так- R₀=[p₀[i]].

Элемент p₀[0] содержит индекс дуги, обладающей наименьшим номером среди дуг исходящих из вершины i. Если из вершины i ничего не выходит, то p₀[i]=p₀[i+1]. Таким образом список дуг будет упорядочен следующим образом: если О(k₁)<O(k₂), то k₁<k₂, если О(к₁)=О(к₂), то порядок следования дуг произволен.

p₀[i]=1, p₀(n+1)=m+1

p₀(i)={k/O(k)>_i,O(k-1)<i},1<i<n

M_Oi={k/p₀[i]<k<p₀[i+1]}-массив M_Oi, p₀(i)=p₀(i+1)

узел 1 2 3 4 5 6

r₀   1 3 5 6 6 8 Дуги выходят из узлов.

Изменение сети( 2 дополнительных массива) для определения конечных дуг, кончающихся в данном узле.

1) список M_ti  m и n. L_t={l_t(i)} содержит номера дуг упорядоченных по возрастанию их конечных узлов. Если k_w- индекс дуги k_w в списке L_t, то следование элементов в списке определяется по правилу: если t(k_w)<t(k_y),то k_w<k_y. Если t(k_w)=t(k_y), то порядок k_w и k_y произволен.

2) список P_t={p_t(i)} указывает индекс первой дуги из списка L_t,  оканчивающейся в вершине i. Для массива P_t справедливы формулы:

P_t(1)=1

P_t(n+1)=m+1

P_t(i)={k/t(l_t(k)>=,t(l_t(k-1)<i}  ,1<i<n

Тогда множество М_t(i) имеет следующий вид:

M_ti={l_t(k)/P_t(i)<=k<=P_t(i+1)}

k 1 2 3 4 5 6 7    узел 1 2 3 4 5 6

L_t7 1 6 2 3 4 5     P_t  1 2 4 6 8 8