2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение16.03.2011, 09:10 


04/02/06
122
СПИИРАН
arseniiv в сообщении #423343 писал(а):
Отображение ставит в соответствие только один элемент, и если вы хотите много или ноль, надо сопоставлять не одну вершину, а множество вершин,которое как раз, если из этой вершины нет дуг, может быть и пустым.


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

Цитата:
(И что за концевые вершины у вас в графе появились?)


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

На самом деле есть книжка, где использовались такие отображения.

Просто для орграфов было бы лучше использовать (одно)связные списки.

 Профиль  
                  
 
 
Сообщение16.03.2011, 14:11 


08/11/09
156
cupuyc
Во-во, вспомнил, поэтому и обратился, что не компилится :D
А в каком месте различие между не- и маркированной вершине при вставке (в случае полиморфизма) в коде будет?

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


27/04/09
28128

(Оффтоп)

OZH в сообщении #423444 писал(а):
Просто для орграфов было бы лучше использовать (одно)связные списки.
Вот массив таких списков и можно поставить в соответствие функции $V \to 2^V$, но никак не функции $V \to V$!

Вот зачем лепить лишнее:
OZH в сообщении #423444 писал(а):
В орграфе есть вершины, куда можно придти (по "стрелкам"), но нельзя выйти. Это не проблема. Просто говорим, что область определения отображения не совпадает с множеством всех вершин. И всё.


С вашей функцией можно будет изобразить только несвязные цепочки и циклы, ведь это же видно!

 Профиль  
                  
 
 
Сообщение16.03.2011, 15:37 


18/11/10
381
Мюнхен
Есть книга Роберта Седжвика "Фундаментальные алгоритмы на С++" часть 5 "Алгоритмы на графах". Там рассматриваются различные способы представления графов, в том числе и АТД для графа.

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


30/07/10
254
kuraga, видимо начинать нужно с самого начала. Оператор new выделяет память, вызывает конструкторы объекта и возвращает адрес который можно присвоить переменной типа "указатель":
Код:
int* a = new int;
std::vector<int>* b = new std::vector<int>();
но адрес нельзя присвоить самой переменной (как это делаете Вы):
Код:
int a = new int; // error: types mismatch
std::vector<int> b = new std::vector<int>; // error: types mismatch

В Вашем случае нужно сделать так:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
class BaseGraph
{
protected:
  std::vector<BaseVertice*> m_vertives;
  // ...
public:
  virtual void add_vertice() = 0;
};

class Graph :
  public BaseGraph
{
public:
  virtual void add_vertice()
  {
    m_vertices.push_back(new Vertice());
  }  
};

class MarkedGraph :
  public BaseGraph
{
public:
  virtual void add_vertice()
  {
    m_vertices.push_back(new MarkedVertice());
  }
};

class Vertice :
  public BaseVertice
{
// ...
};

class MarkedVertice :
  public BaseVertice
{
// ...
};

 Профиль  
                  
 
 Re:
Сообщение16.03.2011, 23:31 


08/11/09
156
сириус, здесь
kuraga в сообщении #423190 писал(а):
Код:
vertices = new std::vector<Vertice*>;
, а вставлять уже
Код:
vertices->push_back(new MarkedVertice);
, очевидно, vertices - указатель на вектор, ну я прямо не настолько идиот :) Ну а все остальное - как я и писал, спасибо, матан доделаю, посмотрю, в чем отличие от моей нынешней версии. И книгу упомянутую выше гляну!

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


30/07/10
254
kuraga в сообщении #423728 писал(а):
очевидно, vertices - указатель на вектор, ну я прямо не настолько идиот
В начале у Вас был написан не указатель, потом, вдруг, мембер стал указателем. На самом деле указатель на вектор как раз-таки здесь не нужен. Нужен обычный мембер, как я написал в примере.

 Профиль  
                  
 
 
Сообщение16.03.2011, 23:49 


08/11/09
156
cupuyc, Вы правы, я вовсе не указывал тип переменной, а раньше говорил как о векторе...
P.S. А вообще - летом имел неосторожность посмотреть Java. То, чего я там ожидал увидеть, я не увидел (но затем нашел в Ruby), зато поимел привычку хранить везде не объекты, а указатели на них...

 Профиль  
                  
 
 Re:
Сообщение18.03.2011, 22:20 


08/11/09
156
cupuyc в сообщении #423721 писал(а):
В Вашем случае нужно сделать так:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
class BaseGraph
{
protected:
  std::vector<BaseVertice*> m_vertives;
  // ...
public:
  virtual void add_vertice() = 0;
};

class Graph :
  public BaseGraph
{
public:
  virtual void add_vertice()
  {
    m_vertices.push_back(new Vertice());
  }  
};

class MarkedGraph :
  public BaseGraph
{
public:
  virtual void add_vertice()
  {
    m_vertices.push_back(new MarkedVertice());
  }
};

class Vertice :
  public BaseVertice
{
// ...
};

class MarkedVertice :
  public BaseVertice
{
// ...
};


Но все равно придется заводить в производном классе свой вектор вершин, типа std::vector<MarkedVertice*>, иначе в MarkedVertice нельзя будет заводить собственных элементов (обращаться к ним), ведь элементом вектора будет Vertice?

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


26/07/09
1559
Алматы
2kuraga
Цитата:
ведь элементом вектора будет Vertice?

Да, но ненастоящий. Приведением типов вы к такой вершине сможете обращаться как к помеченной. Это и называется полиморфизм!

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

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

Вот ваш оригинальный фрагмент:
Используется синтаксис C++
class Vertice {};
class MarkedVertice : Vertice {};
class Graph {
    std::vector<Vertice*> v;
};
class MarkedGraph : Graph {
    std::vector<MarkedVertice*> v;
};
 

Я предлагал его изменить так:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
class Vertex { ... };
class Mark {int VertexLabel; ... };

class Graph
{
    std::vector<Vertex*> Vertices;
    ...
};

class MarkedGraph: public Graph
{
    std::vector<Mark*> Labels;
    ...
    void AddVertex(...)
    {
        Vertices.push_back(...);
        Labels.push_back(...);
        ...
    }
}
 

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

P.S.: И снова обращаю ваше внимание на некоторое несоответствие модели и предметной области; на dxdy уже кто-то упоминал такое дизайнерское решением в котором фрукты являются подмножеством яблок. :)

 Профиль  
                  
 
 
Сообщение19.03.2011, 15:13 
Аватара пользователя


30/07/10
254
kuraga, Вам стоит прочитать какую-нибудь книжку по С++. С самого начала, чтобы всё улеглось в голове.
Используется синтаксис C++
std::vector<Vertice*> Vertices;
Vertices.push_back(new MarkedVertice(..));
std::vector<Vertice*>::iterator i = Vertices.begin();
MarkedVertice* mv = static_cast<MarkedVertice*>(*i);

 Профиль  
                  
 
 
Сообщение19.03.2011, 15:50 


08/11/09
156
Снова упал грязью в лицо :) Я мечтал обойтись без RTTI, но по неопытности (а я его еще не использовал) не заметил, что это нужный случай... СПАСИБО!!!

 Профиль  
                  
 
 
Сообщение19.03.2011, 18:05 
Аватара пользователя


30/07/10
254
kuraga, а при чём здесь RTTI? static_cast и без него работает. Главное dynamic_cast не юзать и прочих приблуд, типа typeinfo или как её там...

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


08/11/09
156
У нас в учебнике это тоже RTTI, а в Страуструпе и Шилдте это еще не читал...

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


26/07/09
1559
Алматы
2kuraga
Цитата:
У нас в учебнике это тоже RTTI

Странно, static_cast<MarkedVertice*>(*i) это (почти) тоже самое, что и (MarkedVertice*)(*i), но безопаснее. Может быть в учебнике просто предупреждали о принципиально возможном run-time оверхеде при преобразовании типов?

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

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



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

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


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

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