Граф, но не дерево???

← →
pasha_golub © (2006-02-24 19:02) [0]

Ребят, не могу ясно сформулировать в терминах графов задачу, чтобы начать поиски. Велосипед изобретать не хочеться.

Предметная область: есть набор объектов, каждый объект может быть потомком одного или нескольких объектов (множественное наследование).
а) необходимо проверить правильность наследования
б) для каждого объекта найти список допустимых предков
в) отсортировать объекты по порядку создания, сначала предки, потом все потомки.

Закодировано:
TEntity = class ... public property ObjectID: integer ...; //уникальный ИД объекта property Inherited: TList ...; //Список ИД предков ... end;

Я сначала подумал, что можно попробовать сделать это все через дерево. Просто для случаев когда у объекта несколько потомков, добавлять несколько листьев к каждому предку.

Например, такое дерево:

1 -> 2 -> 4 -> 3 -> 4
В данном случае, объект 1 общий предок, 2 и 3 его прямые потомки, а объект 4 потомок и 2, и 3.

Однако, потом отказался от этой идеи, ибо она мне показалась черезчур громоздкой и требующей доп. вычислений.

Что я помню из теории графов по этому поводу:
1. Это не дерево.
2. Это однонаправленный граф.
3. Мне нужно найти, есть ли в нем циклы???
4. Его (граф) можно представить в виде матрицы инцидентности, так как он однонаправленный, то это будет треугольная матрица.

Пока, то что искал на http://manual.algolist.ru & http://ru.wikipedia.org/wiki не особо вдохновило.

Что прошу:
1. подтвердить мои догадки или опровергнуть
2. предложить ключевые слова для поиска
3. ну уж если алгоритм вдруг дадите, то с меня бутыль сала и пляшка горилки

Спасибо.

← →
jack128 © (2006-02-24 19:12) [1]

pasha_golub © (24.02.06 19:02)
а) необходимо проверить правильность наследования
А в чем проблема? Ищешь среди предков самого себя, если нету - значит иерархия допустима.

pasha_golub © (24.02.06 19:02)
б) для каждого объекта найти список допустимых предков
Все объекты вычесть все недопустимые объеты = допустимые объекты
pasha_golub © (24.02.06 19:02)
в) отсортировать объекты по порядку создания, сначала предки, потом все потомки.
не совсем понятно:

1 -> 2 -> 4

-> 3 -> 5

кто в отсортированном списке "выше" , насленик (2 и 5) или насленик (3 и 4) ??

← →
pasha_golub © (2006-02-24 19:14) [2]

Не знаю как "однонаправленный", но то, что ориентированный - это точно.

← →
pasha_golub © (2006-02-24 19:17) [3]

> 1 -> 2 -> 4
>
> -> 3 -> 5
>
> кто в отсортированном списке "выше" , насленик (2 и 5)
> или насленик (3 и 4) ??

Жень, это я так понимаю 1 - общий, 2 и 3 потомки от 1, далее 4 потомок 2, а 5 потомок 3?

Если так, то
1
(2,3)
(4,5)

То есть смысл таков, пока не будет создан предок, не может быть создан потомок.

Уф, чего-то бошк не варит совсем.

← →
jack128 © (2006-02-24 19:24) [4]

pasha_golub © (24.02.06 19:17) [3]
Жень, это я так понимаю 1 - общий, 2 и 3 потомки от 1, далее 4 потомок 2, а 5 потомок 3?
Да.
pasha_golub © (24.02.06 19:17) [3]
То есть смысл таков, пока не будет создан предок, не может быть создан потомок.

Ну тогда 2 = 5 поскольку они никак не пересекаются в иерархии.

← →
palva © (2006-02-24 20:39) [5]

http://algolist.ncstu.ru/sort/top_sort.php

← →
palva © (2006-02-24 21:00) [6]

С картинками!
http://www.cs.fsu.edu/~cop4531/slideshow/chapter23/23-4.html

← →
TUser © (2006-02-25 10:41) [7]

> 3. Мне нужно найти, есть ли в нем циклы???

Примерно так

var Vs: array of TVertex;
begin
// "топологическая сортировка"
for j:=low(Vs) to high(Vs) do
for i:=low(Vs) to high(Vs) do
for each Child of Vs[i] do begin
if Child.Index < i then
Swap (i, Child.Index);

// поиск циклов
for i:=low(Vs) to High(Vs) do
for each Child of Vs[i] do
if Child.Index < i then
return циклы есть

return циклов нет
end;

Также есть хорошие алгоритмы поиска кратчайших путей, которые возвращают результат "циклы есть, не могу ничего найти", если в графе есть циклы.

ИМХО пункт А следует из пункта Б. При создании объект должен знать список допустимых предков. Если тебя создает не тот кто может - райзимся в конструкторе...

> Rouse_ © (25.02.06 15:33) [9]

Это не ООП... Это SQL для Postgres"a: http://www.postgresql.org/docs/8.1/interactive/tutorial-inheritance.html

Граф, но не дерево??? Найти похожие ветки