Как будет выглядеть алгоритм?

Question

[pashulke]

Скажем, есть подобная таблица задолженности:

Её можно представить в виде ориентированного графа:

У каждой вершины свой индекс. Их можно представить в виде двудольного графа:

В итоге получается граф с тремя рёбрами:

То есть получается вот такая таблица:


Собственно, вопрос: как это можно представить на веб-языке, какой будет алгоритм?

Answer 1

[Андрей]

Цикл
- Счетчик измененных связей = 0
- Цикл по всем вершинам
- - Если в вершину входит связь и выходит связь (должен он и одновременно должны ему), то заменить ее на две (или одну) прямые связи, разорвав цепочку и увеличить счетчик измененных связей.
Выход из цикла, если счетчик измененных связей = 0

Comments

[pashulke]

"заменить ее на две (или одну) прямые связи" - это как?
Счётчик, получается, только увеличивается? А как он станет равным нулю?
Можете представить алгоритм на псевдокоде, чтобы было понятнее?

[Андрей]

Это и был псевдокод.
В нуль он сбрасывается в начале внешнего цикла.
DO
- CNT = 0
- FOR I=1 TO NODES DO NODE_ANALYSIS(...)
WHILE CNT==0

Если в процессе анализа узла было хотя бы одно изменение, то счетчик увеличивается и внешний цикл запуститься снова.

Цепочка
A---(1000)--->B----(5000)---->C
заменяется на две прямые связи :
A---(1000)---->C
B---(4000)---->C
Если при создании новой связи (в данном случае A->C) она уже есть то сумма прибавляется или вычитается из нее в зависимости от направления долга.

[Андрей]

опечатка :
WHILE CNT!=0

[Андрей]

0->1 : 5000
1->4 : 2000
4->3 : 2000
3->2 : 1000
0->2 : 3000
цепочка при узле 1, модифицируем :
0->1 : 3000
0->4 : 2000
4->3 : 2000
3->2 : 1000
0->2 : 3000
цепочка при узле 4, модифицируем :
0->1 : 3000
0->3 : 2000
3->2 : 1000
0->2 : 3000
цепочка при узле 3, модифицируем :
0->1 : 3000
0->3 : 1000
0->2 : 1000
0->2 : 3000
но из-за того, что 0->2 уже есть, складываем :
0->1 : 3000
0->3 : 1000
0->2 : 4000