2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 
Сообщение16.03.2011, 09:10 
arseniiv в сообщении #423343 писал(а):
Отображение ставит в соответствие только один элемент, и если вы хотите много или ноль, надо сопоставлять не одну вершину, а множество вершин,которое как раз, если из этой вершины нет дуг, может быть и пустым.


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

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


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

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

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

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

 
 
 
 
Сообщение16.03.2011, 15:29 

(Оффтоп)

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

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


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

 
 
 
 
Сообщение16.03.2011, 15:37 
Есть книга Роберта Седжвика "Фундаментальные алгоритмы на С++" часть 5 "Алгоритмы на графах". Там рассматриваются различные способы представления графов, в том числе и АТД для графа.

 
 
 
 
Сообщение16.03.2011, 22:53 
Аватара пользователя
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 
сириус, здесь
kuraga в сообщении #423190 писал(а):
Код:
vertices = new std::vector<Vertice*>;
, а вставлять уже
Код:
vertices->push_back(new MarkedVertice);
, очевидно, vertices - указатель на вектор, ну я прямо не настолько идиот :) Ну а все остальное - как я и писал, спасибо, матан доделаю, посмотрю, в чем отличие от моей нынешней версии. И книгу упомянутую выше гляну!

 
 
 
 
Сообщение16.03.2011, 23:43 
Аватара пользователя
kuraga в сообщении #423728 писал(а):
очевидно, vertices - указатель на вектор, ну я прямо не настолько идиот
В начале у Вас был написан не указатель, потом, вдруг, мембер стал указателем. На самом деле указатель на вектор как раз-таки здесь не нужен. Нужен обычный мембер, как я написал в примере.

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

 
 
 
 Re:
Сообщение18.03.2011, 22:20 
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 
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 
Аватара пользователя
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 
Снова упал грязью в лицо :) Я мечтал обойтись без RTTI, но по неопытности (а я его еще не использовал) не заметил, что это нужный случай... СПАСИБО!!!

 
 
 
 
Сообщение19.03.2011, 18:05 
Аватара пользователя
kuraga, а при чём здесь RTTI? static_cast и без него работает. Главное dynamic_cast не юзать и прочих приблуд, типа typeinfo или как её там...

 
 
 
 
Сообщение19.03.2011, 19:16 
У нас в учебнике это тоже RTTI, а в Страуструпе и Шилдте это еще не читал...

 
 
 
 
Сообщение19.03.2011, 19:49 
2kuraga
Цитата:
У нас в учебнике это тоже RTTI

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

 
 
 [ Сообщений: 45 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group