Форум программистов, компьютерный форум CyberForum.ru

Подобие графа - C++

Восстановить пароль Регистрация
 
 
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
05.06.2016, 18:53     Подобие графа #1
Имеется примерно такой вот класс:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Room {
    private:
        string name;
        string story;
        vector <Room*> rooms; //указатели, куда доступен переход
    public:
        Room () {}
        Room (string name, string story) {
            this->name = name;
            this->story = story;
            }
    public:
        string getName () const { return name; }
        string getStory () const { return story; }
    };
Нужно создать некое подобие графа, элементом которого был бы класс расположенный выше. Переменная rooms содержала бы указатели на все доступные соседние элементы. И вот всё голову ломаю и придумать не могу, как это всё грамотно организовать. А именно, в каком формате будет ввод (но обязательно из файла) и как это всё дело потом создать и связать опираясь на ввод. Буду рад любым пинкам в правильном направлении.

Добавлено через 5 часов 24 минуты
UPD:
Необязательно себя утруждать и писать код, приму любую помощь. Достаточно просто объяснить, как это возможно реализовать, либо не возможно и свой вариант решения задачи.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
05.06.2016, 19:00     Подобие графа #2
Я думал как раз код написать .
Идея в том, чтобы делать связи в файле по индексам или по ключам.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
05.06.2016, 19:01  [ТС]     Подобие графа #3
UPD2:
То что уже имеется:
-все возможные объекты room вводятся из файлов
Из идей было такое:
-названия этих файлов (с набором данных для room, описано выше) будут расположены иерархически в файле - карте и в зависимости от степени вложенности - присваивать каждому названию индекс.
-В соответствии индексу и протягивать связи между объектами, создавая тем самым граф.

Но с реализацией в тупике.
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
05.06.2016, 19:08     Подобие графа #4
Зачем объектам комнат иерархичность?
Можно, к примеру, иметь четыре записи/файла:
0: Первая комната, связи: 1, 2
1: Вторая комната, связи: 0, 3
2: Третья комната, связи: 0, 3
3: Четвёртая комната, связи: 1, 2
Затем по этим данным при загрузке восстанавливать массив указателей.

Добавлено через 1 минуту
Или вопрос в том, как по таким данным восстановить объекты?
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
05.06.2016, 19:14  [ТС]     Подобие графа #5
Vort_, о таком варианте структуры файла - карты и не подумал, хотел как-то сделать что-бы и наглядно было ясно что-куда и что-бы это потом можно было индексировать от степени вложенности. Но теперь от этой идеи откажусь.

Но это даже наверное не главная проблема, не хватает информации и знаний о том, как потом имея индексы воссоздать граф такого типа, не много информации по этому поводу нашёл. Если вас не затруднит, я бы был рад если вы покажите как.
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
05.06.2016, 19:31     Подобие графа #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот пример:
Файл:
Код
4
First room
First room description
2 1 2
Second room
Second room description
2 0 3
Third room
Third room description
2 0 3
Fourth room
Fourth room description
2 1 2
Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
 
using namespace std;
 
class Room {
private:
    string name;
    string story;
    vector<Room*> rooms;
public:
    Room() {}
    Room(string name, string story) {
        this->name = name;
        this->story = story;
    }
public:
    string getName() const { return name; }
    string getStory() const { return story; }
    void addLink(Room* link) { rooms.push_back(link); }
};
 
void main()
{
    ifstream file;
    file.open("rooms.txt");
 
    int roomCount;
    file >> roomCount;
    file.ignore();
 
    vector<Room> rooms(roomCount);
    for (int i = 0; i < roomCount; i++)
    {
        string name;
        string story;
        getline(file, name);
        getline(file, story);
        rooms[i] = Room(name, story);
 
        int linkCount;
        file >> linkCount;
 
        for (int j = 0; j < linkCount; j++)
        {
            int linkedIndex;
            file >> linkedIndex;
            rooms[i].addLink(&rooms[linkedIndex]);
        }
        file.ignore();
    }
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
06.06.2016, 13:12     Подобие графа #7
Цитата Сообщение от vadim_bz Посмотреть сообщение
Нужно создать некое подобие графа, элементом которого был бы класс расположенный выше.
Ну, комнаты у вас и так связаны и образуют граф через указатели. А вы в каком виде граф хотите получить?
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
06.06.2016, 13:19  [ТС]     Подобие графа #8
Mr.X, именно так и хотел, не был уверен в номенклатуре, так как при поисках находил нечто иное, отличное от желаемого.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 18:19  [ТС]     Подобие графа #9
Уж коль далеко не ходить, как устроить для него очищение выделенной памяти?) Думаю обращаться в деструкторе к тому же файлу - карте не совсем правильно, может сделать так что бы при вызове деструктора любой комнаты очищался бы весь граф сразу, или тоже вариант не очень?
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 18:22     Подобие графа #10
Если использовать мой вариант - vector<Room>, то он сам очистится как выйдет из области видимости.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 19:08  [ТС]     Подобие графа #11
Vort_, ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 19:13     Подобие графа #12
За один элемент всё держится что ли?
Если так, то можно создать временный массив, закинуть в него указатели на все элементы.
Затем пройтись по массиву и очистить у каждого объекта ссылки на соседние комнаты (не удаляя объекты).
После чего в цикле удалить все объекты в массиве.

Но точно сказать, не понимая структуры решения, я не могу.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
07.06.2016, 19:34     Подобие графа #13
Используйте shared_ptr.
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 19:35     Подобие графа #14
Цитата Сообщение от Toshkarik Посмотреть сообщение
Используйте shared_ptr.
Только поможет ли это, если комнаты связаны в кольцо?
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
07.06.2016, 19:38     Подобие графа #15
Да, упустил из вида. Тогда weak_ptr.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:29  [ТС]     Подобие графа #16
Vort_ , у меня так и выходит, что каждые соседние комнаты имеют указатели на друг друга. Я думал сделать так, что бы при вызове деструктора для произвольной комнаты начинался поиск крайней комнаты графа (которая имеет только одну ссылку на соседнюю), очистить её, вернуться обратно и снова начать поиск крайней, пока комнат не останется.
Но это и правда ломается если комнат всего 1 или где то не протянута обратная связь.
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:34  [ТС]     Подобие графа #17
Кликните здесь для просмотра всего текста
Подобие графа
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
07.06.2016, 21:52     Подобие графа #18
Цитата Сообщение от vadim_bz Посмотреть сообщение
ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
Умные указатели используйте.
Vort_
 Аватар для Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
08.06.2016, 06:30     Подобие графа #19
мне кажется, что как загрузкой, так и удалением графа должна заниматься внешняя, по отношению к элементу, сущность
задача же деструктора элемента - уничтожить именно элемент
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2016, 17:55     Подобие графа
Еще ссылки по теме:

C++ Робот (подобие игры Sokoban)
Подобие math.h для геометрии C++
Подобие чата с ботом C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
08.06.2016, 17:55  [ТС]     Подобие графа #20
Не правильно?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Room {
    private:
        string name;
        string story;
        vector <weak_ptr <Room>> *rooms;
    public:
        Room () {}
        Room (string name, string story) {
            this->name = name;
            this->story = story;
            rooms = new vector <weak_ptr <Room>>;
            }
        void addRoom (Room *room) { 
            shared_ptr <Room> ptr;
            ptr = make_shared <Room> (*room);
            rooms->push_back(ptr);
            delete room;
            }
    public:
        string getName () const { return name; }
        string getStory () const { return story; }
        //vector <Room*> *get_ptrRooms () const { return rooms; }
    };
Yandex
Объявления
08.06.2016, 17:55     Подобие графа
Ответ Создать тему
Опции темы

Текущее время: 08:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru