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

[OZH]

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

Отображение ставит в соответствие только один элемент, и если вы хотите много или ноль, надо сопоставлять не одну вершину, а множество вершин,которое как раз, если из этой вершины нет дуг, может быть и пустым.

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

Цитата:

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

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

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

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

[kuraga]

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

[arseniiv]

(Оффтоп)

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

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

Вот массив таких списков и можно поставить в соответствие функции $V \to 2^V$, но никак не функции $V \to V$!

Вот зачем лепить лишнее:

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

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

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

[kolas]

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

[cupuyc]

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 
{
// ...
};

[kuraga]

сириус, здесь

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

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

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

vertices->push_back(new MarkedVertice);

, очевидно, vertices - указатель на вектор, ну я прямо не настолько идиот :) Ну а все остальное - как я и писал, спасибо, матан доделаю, посмотрю, в чем отличие от моей нынешней версии. И книгу упомянутую выше гляну!

[cupuyc]

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

очевидно, vertices - указатель на вектор, ну я прямо не настолько идиот

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

[kuraga]

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

[kuraga]

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?

[Circiter]

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 уже кто-то упоминал такое дизайнерское решением в котором фрукты являются подмножеством яблок. :)

[cupuyc]

kuraga, Вам стоит прочитать какую-нибудь книжку по С++. С самого начала, чтобы всё улеглось в голове.

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

std::vector<Vertice*> Vertices;
Vertices.push_back(new MarkedVertice(..));
std::vector<Vertice*>::iterator i = Vertices.begin();
MarkedVertice* mv = static_cast<MarkedVertice*>(*i);

[kuraga]

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

[cupuyc]

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

[kuraga]

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

[Circiter]

2kuraga

Цитата:

У нас в учебнике это тоже RTTI

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