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

1. Необходимо обеспечить безопасное удаление элементов, чтобы при удалении объекта все его "соседи" об этом знали.
2. Допустим, есть объект a класса A, его потомками могут быть объекты классов B и C. Нужно обеспечить возможность получения клиентом от объекта a двух множеств: "потомки a, класса B" и "потомки a, класса C".
3. Не повредило бы наличие средства для локальной работы с "поддеревьями".
4. А если это всё, да ещё и попотокобезопаснее, -- это было бы более, чем замечательно.
5. Пробовал заключить информацию о родителях/потомках в сами классы -- ничего хорошего. Теперь собираюсь сделать "менеджера связей", в этой связи напрашивается использование БД, но, насколько я знаю, с рекурсивными алгоритмами (а их у меня множество) запросы БД лучше не мешать (или мешать, но как -- мне не известно), и, наконец, как же быть с пунктом 3 ?
6. Работать, видимо, придется, ограничивая доступ к узлам дерева прокси-интерфейсом в сочетании с фабриками (удаление, создание объектов). Прав ли я ?
7. И ещё один тупой вопрос: как в данном случае лучше организовывать доступ объектов-узлов к менеджеру: хранить в объекте ссылку на менеджера, полученную при создании объекта, или юзать оного глобально ?

Уважаемые знатоки, подскажите, пожалуйста способы решения.
Заранее спасибо за помощь.

Здравствуйте, der_user, Вы писали:

_>На самом деле, это "древовидный граф" (у него один корень, и он иерархичен, ... всё бы ничего, однако некоторые его узлы могут иметь по несколько родителей).
_>Проблема в том, что он на самом деле должен содержать полиморфные объекты; объекты-узлы разных типов могут иметь потомков и родителей разных типов (множество комбинаций для каждого типа определено), причем:

_>1. Необходимо обеспечить безопасное удаление элементов, чтобы при удалении объекта все его "соседи" об этом знали.

А точно обязательно соседям об этом знать? Ведь можно удалить вершину не уведомляя об этом соседей, достаточно лишь убрать связь и все. Если все-таки соседям надо знать о том что объект удалился, сделать события, и на них подписать этих соседей, а они уж пусть сами решают, что дальше делать. Но по-моему это неверный путь и мой взгляд этим должен заниматься отдельный класс, а никак не объекты в контейнере (имеется ввиду граф).

_>2. Допустим, есть объект a класса A, его потомками могут быть объекты классов B и C. Нужно обеспечить возможность получения клиентом от объекта a двух множеств: "потомки a, класса B" и "потомки a, класса C".

Создать опять же класс внешний, который будет хранить ссылку на граф или получать ее как параметр вызова метода, передать сам объект в метод, и некий идентификатор класса-фильтра (это уже зависит от языка программирования). У графа получаете коллекцию соседей, которую фильтруете по типу, и возвращаете уже отфильтрованную.

_>3. Не повредило бы наличие средства для локальной работы с "поддеревьями".

Что может быть проще, концепция субграфа. Я наследовал субграф от графа, таким образом получая все его методы, и добавлял несколько своих, разумеется методы добавления/удаления вершин и некоторые другие пришлось переопределить. Причем субграф не делал копии объектов, а имел только ссылки на уже существующие в "суперграфе", это существенно уменьшает объем используемой памяти.

_>4. А если это всё, да ещё и попотокобезопаснее, -- это было бы более, чем замечательно.

Pattern Decorator он же Wrapper, для каждого метода делаете синхронизированную обертку.

_>5. Пробовал заключить информацию о родителях/потомках в сами классы -- ничего хорошего. Теперь собираюсь сделать "менеджера связей", в этой связи напрашивается использование БД, но, насколько я знаю, с рекурсивными алгоритмами (а их у меня множество) запросы БД лучше не мешать (или мешать, но как -- мне не известно), и, наконец, как же быть с пунктом 3 ?

"Менеджер связей" еще называется инцидентором, есть несколько вариантов представлений графов, но с инцидентором самый правильный
Я бы не стал такую логику пихать в базу данных, но в Oracle и SapDB есть специальные функции для обхода дерева представленного таблицей, можете попробовать.

_>6. Работать, видимо, придется, ограничивая доступ к узлам дерева прокси-интерфейсом в сочетании с фабриками (удаление, создание объектов). Прав ли я ?

Насчет фабрики, лучше создание объектов разрешить исключительно самому дереву или графу, это правильно уже с логической точки зрения: ребро и вершина, не рассматриваются в теории графов отдельно вне контекста какого-то графа. Лучше всего установить графу необходимые фабрики, а затем вызывать метод типа createNone (если типов вершин несколько — придется передавать и тип).

_>7. И ещё один тупой вопрос: как в данном случае лучше организовывать доступ объектов-узлов к менеджеру: хранить в объекте ссылку на менеджера, полученную при создании объекта, или юзать оного глобально ?

Объекты узлы ИМХО не должны знать от контейнере или менеджере, а еще лучше чтобы и контейнер не знал типов объектов и их внутреннего устройства. Этого всегда можно избежать. Вообще, я на архитектуру подобной библиотеки потратил месяца 2, зато на данный момент меня все устраивает.

Здравствуйте, Trean, Вы писали:

_>>1. Необходимо обеспечить безопасное удаление элементов, чтобы при удалении объекта все его "соседи" об этом знали.

T>А точно обязательно соседям об этом знать? Ведь можно удалить вершину не уведомляя об этом соседей, достаточно лишь убрать связь и все. Если все-таки соседям надо знать о том что объект удалился, сделать события, и на них подписать этих соседей, а они уж пусть сами решают, что дальше делать. Но по-моему это неверный путь и мой взгляд этим должен заниматься отдельный класс, а никак не объекты в контейнере (имеется ввиду граф).

У меня ситуация весьма интересная, когда удаление одного элемента из графа может сильно повлиять на судьбу других его элементоа (не обязательно соседей)

_>>5. Пробовал заключить информацию о родителях/потомках в сами классы -- ничего хорошего. Теперь собираюсь сделать "менеджера связей", в этой связи напрашивается использование БД, но, насколько я знаю, с рекурсивными алгоритмами (а их у меня множество) запросы БД лучше не мешать (или мешать, но как -- мне не известно), и, наконец, как же быть с пунктом 3 ?

T>"Менеджер связей" еще называется инцидентором, есть несколько вариантов представлений графов, но с инцидентором самый правильный
T>Я бы не стал такую логику пихать в базу данных, но в Oracle и SapDB есть специальные функции для обхода дерева представленного таблицей, можете попробовать.

Про "инцидентор" буду знать, — спасибо

_>>7. И ещё один тупой вопрос: как в данном случае лучше организовывать доступ объектов-узлов к менеджеру: хранить в объекте ссылку на менеджера, полученную при создании объекта, или юзать оного глобально ?

T>Объекты узлы ИМХО не должны знать от контейнере или менеджере, а еще лучше чтобы и контейнер не знал типов объектов и их внутреннего устройства. Этого всегда можно избежать. Вообще, я на архитектуру подобной библиотеки потратил месяца 2, зато на данный момент меня все устраивает.

Это всё понятно, но я сейчас решаю, на что уйдёт меньше времени — на разработку действительно хорошей архитектуры или на традиционный "тяп-ляп", приводящий к приемлемым результатам

Здравствуйте, der_user, Вы писали:

_>У меня ситуация весьма интересная, когда удаление одного элемента из графа может сильно повлиять на судьбу других его элементоа (не обязательно соседей)

В таком случае я бы все-таки сделал отдельный класс, который бы реализовывал данную логику, а на изменение графа сделал бы listener'а. Тут главное в бесконечную рекурсию не уйти Прописывать эту логику в элементе на мой взгляд не самая удачная идея.

_>Это всё понятно, но я сейчас решаю, на что уйдёт меньше времени — на разработку действительно хорошей архитектуры или на традиционный "тяп-ляп", приводящий к приемлемым результатам

На тяп-ляп хватит наверное недели две я сначала сделал почти тяп-ляп, а потом когда в целом уже представлял как и что должно быть, переписал наново как reusable библиотечку.

Спасибо, Trean, всё будет учтено

Здравствуйте, Trean, Вы писали:

T>Создать опять же класс внешний, который будет хранить ссылку на граф или получать ее как параметр вызова метода, передать сам объект в метод, и некий идентификатор класса-фильтра (это уже зависит от языка программирования). У графа получаете коллекцию соседей, которую фильтруете по типу, и возвращаете уже отфильтрованную.

Не могли бы Вы привести конкретный пример "передачи идентификатора класса-фильтра" и, что более интересно, способ фильтрации. Если я правильно Вас понимаю, в примитивном случае "идентификатор класса-фильтра" это простая строка (или например объект Type в С#), которая влечет за собой немедленный switch или else if конструкции для разбора этого идентификатора. Что делать в случае, если заранее не знаешь тип объекта, а фильтровать приходится по конкретному, при чем без использования шаблонов?

T>Насчет фабрики, лучше создание объектов разрешить исключительно самому дереву или графу, это правильно уже с логической точки зрения: ребро и вершина, не рассматриваются в теории графов отдельно вне контекста какого-то графа. Лучше всего установить графу необходимые фабрики, а затем вызывать метод типа createNone (если типов вершин несколько — придется передавать и тип).

Здесь тоже не совсем понятно в каком виде передавать тип и что делать, если внутри createNode надо делать больше, чем простое использование фабричных методов объекта-типа (например набор типов вершин не фиксирован)? То есть, насколько я понимаю, можно передавать строку-идентификатор, по которой искать фабрику в списке зарегистрированных фабрик и затем вызывать ее создающий метод. Но что делать в случае, если целью является не только создание, но и выполнение действий специфичных для типа, которые нельзя уложить в общий интерфейс?

То есть, короче говоря, мои вопросы следующие:
Как правильно передавать информацию о типе без использования шаблонов?
Как сделать так, чтобы при добавлении новых поддерживаемых типов, не менялся интерфейс компонента?
Имеют ли смысл мои вопросы? Возможно, для их решения следует вообще отказаться от идеи универсальной поддержки любых типов?

Спасибо.

Здравствуйте, Сергей Щ., Вы писали:

СЩ>Здравствуйте, Trean, Вы писали:

T>>Создать опять же класс внешний, который будет хранить ссылку на граф или получать ее как параметр вызова метода, передать сам объект в метод, и некий идентификатор класса-фильтра (это уже зависит от языка программирования). У графа получаете коллекцию соседей, которую фильтруете по типу, и возвращаете уже отфильтрованную.

СЩ>Не могли бы Вы привести конкретный пример "передачи идентификатора класса-фильтра" и, что более интересно, способ фильтрации. Если я правильно Вас понимаю, в примитивном случае "идентификатор класса-фильтра" это простая строка (или например объект Type в С#), которая влечет за собой немедленный switch или else if конструкции для разбора этого идентификатора. Что делать в случае, если заранее не знаешь тип объекта, а фильтровать приходится по конкретному, при чем без использования шаблонов?

class TypeFilter {

public static Collection getTypeObjects(Collection nv, Class filterType) {
   
   Collection fv = new ArrayList();
   for(Vertex v : nv) {
     if(v.getClass().equals(filterType)) {
        fv.add(v);
     }
   }
}

}

Вызов может выглядеть так:

TypeFilter.getTypeObjects(graph.getNeighbourVertices(/* вершина типа инт */new Integer(1234)), /*тип некоего объекта*/ obj.getClass() );

T>>Насчет фабрики, лучше создание объектов разрешить исключительно самому дереву или графу, это правильно уже с логической точки зрения: ребро и вершина, не рассматриваются в теории графов отдельно вне контекста какого-то графа. Лучше всего установить графу необходимые фабрики, а затем вызывать метод типа createNone (если типов вершин несколько — придется передавать и тип).

СЩ>Здесь тоже не совсем понятно в каком виде передавать тип и что делать, если внутри createNode надо делать больше, чем простое использование фабричных методов объекта-типа (например набор типов вершин не фиксирован)? То есть, насколько я понимаю, можно передавать строку-идентификатор, по которой искать фабрику в списке зарегистрированных фабрик и затем вызывать ее создающий метод.

Тип можно передавать в любом виде, какой удобен: число целое, строка, RTTI информация в каком-то виде. Главное, чтобы граф знал, что с ними дальше делать.

СЩ>Но что делать в случае, если целью является не только создание, но и выполнение действий специфичных для типа, которые нельзя уложить в общий интерфейс?

Дело в том, что я не делал интрузивный контейнер-граф, и вообще считаю что это не есть хорошо. Граф не должен знать ничего о типах объектов, если вам что-то надо сделать специфическое для каждого типа элемента, нет имхо смысла эту логику реализовывать внутри контейнера.

СЩ>То есть, короче говоря, мои вопросы следующие:
СЩ>Как правильно передавать информацию о типе без использования шаблонов?
СЩ>Как сделать так, чтобы при добавлении новых поддерживаемых типов, не менялся интерфейс компонента?
СЩ>Имеют ли смысл мои вопросы? Возможно, для их решения следует вообще отказаться от идеи универсальной поддержки любых типов?

На все вопросы, у меня один ответ — делать неинтрузивный контейнер (используйте либо шаблоны либо общий базовый класс, пусть даже пустышку). Даже не обязательно фабрики в граф включать, можно создавать вершины и ребра и вне графа, что упрощает создание графа с разным типом элементов, но ответственность за правильность создания вершин и связей уже тогда ложиться на вызывающую логику, а не сам граф. Но по-возможности конечно надо делать так, чтобы можно было использовать абстрактную фабрику. Специфическую, дополнительную инициализацию вершин или ребер уже делать через вызов set методов вне графа, а не через конструктор. На самом деле для построения самого графа (множества вершин и связей между ними) надо не так много информации, и без знания конкретных типов вполне можно обойтись.

СЩ>Спасибо.

Надеюсь понятно объяснил

Здравствуйте, Trean, Вы писали:

T>Надеюсь понятно объяснил

Да, спасибо
Я сейчас бьюсь над другой задачей, не связанной с графами, а спросил в этом топике, потому что некоторые аспекты мне показались перекликающимися с моей проблемой (я безуспешно спрашивал недавно в этом же под-форуме).

Спасибо за ответ.
Выводы, которые я для себя сделал:
1) передавать информацию о типе в виде строки, целого, объекта мета-класса отображения не всегда есть совсем плохая стратегия, от которой нужно отказываться;
2) использование базового "класса-пустышки" бывает полезно.

Здравствуйте, Сергей Щ., Вы писали:

СЩ>Здравствуйте, Trean, Вы писали:

T>>Надеюсь понятно объяснил

СЩ>Да, спасибо
СЩ>Я сейчас бьюсь над другой задачей, не связанной с графами, а спросил в этом топике, потому что некоторые аспекты мне показались перекликающимися с моей проблемой (я безуспешно спрашивал недавно в этом же под-форуме).

СЩ>Спасибо за ответ.
СЩ>Выводы, которые я для себя сделал:
СЩ>1) передавать информацию о типе в виде строки, целого, объекта мета-класса отображения не всегда есть совсем плохая стратегия, от которой нужно отказываться;
СЩ>2) использование базового "класса-пустышки" бывает полезно.

В Java, например, это уже by design, Object класс базовый для всех есть, всего лишь требуется правильно прописать equals и hashСode методы.