Графы на C++: иерархия классов

[kuraga]

Здравствуйте!

Есть класс ВЕРШИНА, производный от него класс МАРКИРОВАННАЯ_ВЕРШИНА, от ребер пока отречемся, пусть граф - набор точек. Есть класс ГРАФ и производный от него класс МАРКИРОВАННЫЙ_ГРАФ.

Так вот, проблема в том, что набор вершин в ГРАФе есть ВЕКТОР ВЕРШИН, а в МАРКИРОВАННОМ_ГРАФЕ - ВЕКТОР МАРКИРОВАННЫХ_ВЕРШИН.
Иными словами, код:

Используется синтаксис C++

class Vertice {};
class MarkedVertice : Vertice {};
class Graph {
    std::vector<Vertice*> v;
};
class MarkedGraph : Graph {
    std::vector<MarkedVertice*> v;
}; 
 

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

Синтаксически такое возможно, а дальше? И куда вставлять инициализацию вектора, ведь если в каждый конструктор, то создастся два вектора...

Что-то я как-то не так придумал... Прошу помощи

[cupuyc]

kuraga, зачем Вам в MarkedGraph ещё раз заводить вектор указателей? Вам просто нужен виртуальный метод, который будет добавлять вершины и мембер v сделать protected. Для класса Graph он будет вызывать v.push(new Verticle);, для класса MarkedGraph - v.push(new MarkedVertice);.

[Circiter]

2kuraga
Ну это ещё большой вопрос, помеченный граф должен быть частным случаем непомеченного или наоборот. :)

Понятно, что в каждой версии графа хранить список вершин -- излишне. Как альтернатива сказанному участником cupuyc, думаю, здесь неплохо бы смотрелся подход с шаблонами. То есть почему-бы не создавать тип помеченного графа, скажем, как Graph<Marked>, а по-умолчанию (без указания шаблонного параметра) тогда создавался бы обычный непомеченный граф... Вроде-бы это никак не ограничивает дальнейшее написании программульки, но, следует признать, с обычным полиморфизмом здесь, видимо, не все в порядке будет...

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

То есть, переименовываем содержащийся в MarkedGraph вектор v в, скажем, labels, а MarkedVertice всюду переименовываем, ну например, в Mark. :) В результате мухи вершины будут отдельно и метки отдельно (на самом деле, это плохое решение, переваливающее слишком много ответственности на MarkedGraph).

И не могу не посоветовать глянуть на boost::graph.

P.S.: Надеюсь, вам ещё что-нибудь дельное посоветуют, самому интересно узнать правильный ответ на этот вопрос. :)

[cupuyc]

Circiter в сообщении #422709 писал(а):

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

Почему альтернатива? Я тоже считаю, что статический полиморфизм был бы эффективнее. Нет смысла переносить всё на real time, если можно сделать compile time. Просто, насколько я понимаю, ТС ещё плохо разобрался с самой концепцией наследования, а Вы ему уже метапрограмминг советуете.

[kuraga]

Во-первых, спасибо, что откликнулись, а то уже 2-й курс, прогаю 5 лет, а такой вопрос странный... Молодость :)

cupuyc в сообщении #422706 писал(а):

kuraga, зачем Вам в MarkedGraph ещё раз заводить вектор указателей?

Нет! Я написал

kuraga в сообщении #422487 писал(а):

ведь если в [вставить оператор new] каждый конструктор, то создастся два вектора...

Итак...

Circiter в сообщении #422709 писал(а):

Как альтернатива сказанному участником cupuyc, думаю, здесь неплохо бы смотрелся подход с шаблонами. То есть почему-бы не создавать тип помеченного графа, скажем, как Graph<Marked>, а по-умолчанию (без указания шаблонного параметра) тогда создавался бы обычный непомеченный граф...

Я как-то отошел от этого варианта (он был изначальным). По двум причинам: так посоветовал преподаватель, который теперь заболел, и, думаю, он не особо подумал. Вторая - я хочу сделать как бы ГРАФ независимым компонентом. Сейчас это МАРКИРОВАННЫЙ_ГРАФ, потом будет ЕЩЕ_КАКОЙ_ТО, и тогда... Или я не прав? И полиморфизм ничуть не лучше?

Circiter в сообщении #422709 писал(а):

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

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

В общем, хотелось бы услышать дискуссию: полиморфизм или шаблоны?

Спасибо.

[worm2]

kuraga писал(а):

полиморфизм или шаблоны?

Шаблоны однозначно. Вы уже сами отметили трудности, связанные с тем, что обычный полиморфизм "не взлетает" в такой ситуации.

[cupuyc]

kuraga в сообщении #422487 писал(а):

ведь если в [вставить оператор new] каждый конструктор, то создастся два вектора...

Просто получше надо продумать иерархию классов, если всё-таки планируете делать динамический полиморфизм. Базовый класс GraphBase, в нём определён вектор и базовые операции над ним (возможно, как виртуальные методы). От него наследуются Graph и MarkedGraph, которые и инициализируют этот самый вектор. Честно говоря, инициализировать мембер в конструкторе посредством динамического полиморфизма - тот ещё гемор. Виртуальные методы в конструкторе вызывать нельзя. Нужно или третий класс создавать, который будет заниматься инициализацией или ещё какой-нибудь костыль делать, типа инициализации вектора не в конструкторе, а посредством вызова отдельного виртуального метода. А вообще, изобретать велосипед - дело неблагодарное.

[OZH]

А зачем шаблоны?

-- Вт мар 15, 2011 12:12:38 --

Я не знаком с boost::graph. Могу, лишь, сказать следующее. Граф — это отображение из множества вершин в (мульти?)множество вершин. Ориентированный граф ещё проще: это — отображение множества вершин в себя.

[kuraga]

cupuyc в сообщении #423000 писал(а):

Базовый класс GraphBase, в нём определён вектор и базовые операции над ним (возможно, как виртуальные методы). От него наследуются Graph и MarkedGraph, которые и инициализируют этот самый вектор.

Инициализировать

vertices = new std::vector<Vertice*>;

, а вставлять уже

vertices->push_back(new MarkedVertice);

, я прав?

[arseniiv]

OZH в сообщении #423097 писал(а):

Граф — это отображение из множества вершин в (мульти?)множество вершин. Ориентированный граф ещё проще: это — отображение множества вершин в себя.

Неправильно! Граф (ориентированный без кратности дуг) — это пара $\langle V, E \rangle$ из множества вершин и множества рёбер дуг, притом множество дуг — это бинарное отношение на множестве вершин ($E \subset V \times V$), и это отношение не всегда отображение. Для неориентированного графа берут тоже не обязательно отображение: либо множество из неупорядоченных пар, либо симметричное отношение (кому как нравится).

[OZH]

arseniiv в сообщении #423305 писал(а):

Неправильно!

Что же неправильного? Вы привели другое, более традиционное, определение. Что нам мешает сказать, что у нас есть множество вершин $V$ и отображение $F\colon V\to V$, которое (для орграфа) означает функцию последования? (Такое отображение, правда не будет определено в концевых вершинах.)

-- Вт мар 15, 2011 22:55:36 --

Если учитывать помеченность вершин, то, наверное, нужно делать шаьлон с параметром так, чтобы по умолчанию помеченности не было, а для помеченности указывать тип пометок. Но мне пока не очень ясно, почему именно шаблоны. Почему нельзя использовать простые классы?

[arseniiv]

OZH в сообщении #423337 писал(а):

Что нам мешает сказать

Тогда нужно сделать $F \colon V \to 2^V$, но никак не $V \to V$! Отображение ставит в соответствие только один элемент, и если вы хотите много или ноль, надо сопоставлять не одну вершину, а множество вершин, которое как раз, если из этой вершины нет дуг, может быть и пустым. (И что за концевые вершины у вас в графе появились?)

[Maslov]

arseniiv в сообщении #423343 писал(а):

С некоторыми оговорками можно сделать $F \colon V \to 2^V$

А с неориентированными и взвешенными графами как выкручиваться будем? :)

[arseniiv]

Maslov в сообщении #423347 писал(а):

А с неориентированными и взвешенными графами как выкручиваться будем? :)

То есть, для орграфов-то как раз без оговорок (и я там поправил), а для неорграфов придётся навесить $\forall u, v \in V \; F(u) = v \Leftrightarrow F(v) = u$, и потому это мне не нравится, ведь условие к отношению выглядит привычнее. А взвешенность тут можно сделать, сопоставляя мультимножество, только я не знаю, как обозначается множество (или там класс?) всех мультимножеств с базой $2^V$. Хотя нет, это кратные дуги, а нам надо любые вещи для веса. Тогда нужно сопоставлять вот что: $2^{\left\{ \langle n, v \rangle \, | \, v \in W \wedge v \in V \right\}}$, где веса берутся из $W$. Мда.

[cupuyc]

kuraga в сообщении #423190 писал(а):

Инициализировать

vertices = new std::vector<Vertice*>;

, а вставлять уже

vertices->push_back(new MarkedVertice);

, я прав?

Нет. Такое даже не скомпилится.