2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Графы на C++: иерархия классов
Сообщение13.03.2011, 16:52 


08/11/09
156
Здравствуйте!

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

Так вот, проблема в том, что набор вершин в ГРАФе есть ВЕКТОР ВЕРШИН, а в МАРКИРОВАННОМ_ГРАФЕ - ВЕКТОР МАРКИРОВАННЫХ_ВЕРШИН.
Иными словами, код:
Используется синтаксис C++
class Vertice {};
class MarkedVertice : Vertice {};
class Graph {
    std::vector<Vertice*> v;
};
class MarkedGraph : Graph {
    std::vector<MarkedVertice*> v;
};
 


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

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

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

 Профиль  
                  
 
 
Сообщение14.03.2011, 02:52 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение14.03.2011, 04:11 
Заслуженный участник


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

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение14.03.2011, 10:56 
Аватара пользователя


30/07/10
254
Circiter в сообщении #422709 писал(а):
Как альтернатива сказанному участником cupuyc, думаю, здесь неплохо бы смотрелся подход с шаблонами.
Почему альтернатива? Я тоже считаю, что статический полиморфизм был бы эффективнее. Нет смысла переносить всё на real time, если можно сделать compile time. Просто, насколько я понимаю, ТС ещё плохо разобрался с самой концепцией наследования, а Вы ему уже метапрограмминг советуете.

 Профиль  
                  
 
 
Сообщение14.03.2011, 12:58 


08/11/09
156
Во-первых, спасибо, что откликнулись, а то уже 2-й курс, прогаю 5 лет, а такой вопрос странный... Молодость :)
cupuyc в сообщении #422706 писал(а):
kuraga, зачем Вам в MarkedGraph ещё раз заводить вектор указателей?

Нет! Я написал
kuraga в сообщении #422487 писал(а):
ведь если в [вставить оператор new] каждый конструктор, то создастся два вектора...

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

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

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

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

Спасибо.

 Профиль  
                  
 
 
Сообщение14.03.2011, 13:24 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
kuraga писал(а):
полиморфизм или шаблоны?
Шаблоны однозначно. Вы уже сами отметили трудности, связанные с тем, что обычный полиморфизм "не взлетает" в такой ситуации.

 Профиль  
                  
 
 Re:
Сообщение14.03.2011, 23:41 
Аватара пользователя


30/07/10
254
kuraga в сообщении #422487 писал(а):
ведь если в [вставить оператор new] каждый конструктор, то создастся два вектора...
Просто получше надо продумать иерархию классов, если всё-таки планируете делать динамический полиморфизм. Базовый класс GraphBase, в нём определён вектор и базовые операции над ним (возможно, как виртуальные методы). От него наследуются Graph и MarkedGraph, которые и инициализируют этот самый вектор. Честно говоря, инициализировать мембер в конструкторе посредством динамического полиморфизма - тот ещё гемор. Виртуальные методы в конструкторе вызывать нельзя. Нужно или третий класс создавать, который будет заниматься инициализацией или ещё какой-нибудь костыль делать, типа инициализации вектора не в конструкторе, а посредством вызова отдельного виртуального метода. А вообще, изобретать велосипед - дело неблагодарное.

 Профиль  
                  
 
 
Сообщение15.03.2011, 10:46 


04/02/06
122
СПИИРАН
А зачем шаблоны?

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

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

 Профиль  
                  
 
 
Сообщение15.03.2011, 16:19 


08/11/09
156
cupuyc в сообщении #423000 писал(а):
Базовый класс GraphBase, в нём определён вектор и базовые операции над ним (возможно, как виртуальные методы). От него наследуются Graph и MarkedGraph, которые и инициализируют этот самый вектор.

Инициализировать
Код:
vertices = new std::vector<Vertice*>;
, а вставлять уже
Код:
vertices->push_back(new MarkedVertice);
, я прав?

 Профиль  
                  
 
 
Сообщение15.03.2011, 20:31 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение15.03.2011, 21:50 


04/02/06
122
СПИИРАН
arseniiv в сообщении #423305 писал(а):
Неправильно!


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

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

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

 Профиль  
                  
 
 
Сообщение15.03.2011, 21:58 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение15.03.2011, 22:00 
Заслуженный участник


09/08/09
3438
С.Петербург
arseniiv в сообщении #423343 писал(а):
С некоторыми оговорками можно сделать $F \colon V \to 2^V$
А с неориентированными и взвешенными графами как выкручиваться будем? :)

 Профиль  
                  
 
 
Сообщение15.03.2011, 22:08 
Заслуженный участник


27/04/09
28128
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$. Мда.

 Профиль  
                  
 
 Re:
Сообщение16.03.2011, 02:11 
Аватара пользователя


30/07/10
254
kuraga в сообщении #423190 писал(а):
Инициализировать
Код:
vertices = new std::vector<Vertice*>;
, а вставлять уже
Код:
vertices->push_back(new MarkedVertice);
, я прав?
Нет. Такое даже не скомпилится.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 45 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group