Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
1

Подобие графа

05.06.2016, 18:53. Показов 1191. Ответов 29
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Имеется примерно такой вот класс:
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:
Необязательно себя утруждать и писать код, приму любую помощь. Достаточно просто объяснить, как это возможно реализовать, либо не возможно и свой вариант решения задачи.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.06.2016, 18:53
Ответы с готовыми решениями:

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием...

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

Подобие игры
Ребята. Начал писать, но тут проблема. Программа не работает. Он запускает лишь ранее...

Подобие треугольников
На проверочном сайте проходит 80%, где ошибка? Заданы два треугольника: ABC и DEF. Необходимо...

29
199 / 199 / 78
Регистрация: 10.07.2012
Сообщений: 409
05.06.2016, 19:00 2
Я думал как раз код написать .
Идея в том, чтобы делать связи в файле по индексам или по ключам.
0
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
05.06.2016, 19:01  [ТС] 3
UPD2:
То что уже имеется:
-все возможные объекты room вводятся из файлов
Из идей было такое:
-названия этих файлов (с набором данных для room, описано выше) будут расположены иерархически в файле - карте и в зависимости от степени вложенности - присваивать каждому названию индекс.
-В соответствии индексу и протягивать связи между объектами, создавая тем самым граф.

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

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

Но это даже наверное не главная проблема, не хватает информации и знаний о том, как потом имея индексы воссоздать граф такого типа, не много информации по этому поводу нашёл. Если вас не затруднит, я бы был рад если вы покажите как.
0
199 / 199 / 78
Регистрация: 10.07.2012
Сообщений: 409
05.06.2016, 19:31 6
Лучший ответ Сообщение было отмечено vadim_bz как решение

Решение

Вот пример:
Файл:
Код
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();
    }
}
1
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
06.06.2016, 13:12 7
Цитата Сообщение от vadim_bz Посмотреть сообщение
Нужно создать некое подобие графа, элементом которого был бы класс расположенный выше.
Ну, комнаты у вас и так связаны и образуют граф через указатели. А вы в каком виде граф хотите получить?
0
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
06.06.2016, 13:19  [ТС] 8
Mr.X, именно так и хотел, не был уверен в номенклатуре, так как при поисках находил нечто иное, отличное от желаемого.
0
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 18:19  [ТС] 9
Уж коль далеко не ходить, как устроить для него очищение выделенной памяти?) Думаю обращаться в деструкторе к тому же файлу - карте не совсем правильно, может сделать так что бы при вызове деструктора любой комнаты очищался бы весь граф сразу, или тоже вариант не очень?
0
199 / 199 / 78
Регистрация: 10.07.2012
Сообщений: 409
07.06.2016, 18:22 10
Если использовать мой вариант - vector<Room>, то он сам очистится как выйдет из области видимости.
0
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 19:08  [ТС] 11
Vort_, ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
0
199 / 199 / 78
Регистрация: 10.07.2012
Сообщений: 409
07.06.2016, 19:13 12
За один элемент всё держится что ли?
Если так, то можно создать временный массив, закинуть в него указатели на все элементы.
Затем пройтись по массиву и очистить у каждого объекта ссылки на соседние комнаты (не удаляя объекты).
После чего в цикле удалить все объекты в массиве.

Но точно сказать, не понимая структуры решения, я не могу.
1
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
07.06.2016, 19:34 13
Используйте shared_ptr.
0
199 / 199 / 78
Регистрация: 10.07.2012
Сообщений: 409
07.06.2016, 19:35 14
Цитата Сообщение от Toshkarik Посмотреть сообщение
Используйте shared_ptr.
Только поможет ли это, если комнаты связаны в кольцо?
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
07.06.2016, 19:38 15
Да, упустил из вида. Тогда weak_ptr.
1
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:29  [ТС] 16
Vort_ , у меня так и выходит, что каждые соседние комнаты имеют указатели на друг друга. Я думал сделать так, что бы при вызове деструктора для произвольной комнаты начинался поиск крайней комнаты графа (которая имеет только одну ссылку на соседнюю), очистить её, вернуться обратно и снова начать поиск крайней, пока комнат не останется.
Но это и правда ломается если комнат всего 1 или где то не протянута обратная связь.
0
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
07.06.2016, 20:34  [ТС] 17
Кликните здесь для просмотра всего текста
Подобие графа
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
07.06.2016, 21:52 18
Цитата Сообщение от vadim_bz Посмотреть сообщение
ах да, забыл сказать, сделал всё с выделением памяти и после создания всё это живёт не умирая. Вот и подумываю, как лучше организовать очищение (деструктор).
Умные указатели используйте.
0
199 / 199 / 78
Регистрация: 10.07.2012
Сообщений: 409
08.06.2016, 06:30 19
мне кажется, что как загрузкой, так и удалением графа должна заниматься внешняя, по отношению к элементу, сущность
задача же деструктора элемента - уничтожить именно элемент
0
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; }
    };
0
08.06.2016, 17:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.06.2016, 17:55
Помогаю со студенческими работами здесь

Подобие чата с ботом
А как сделать что то на подобе чата с ботом Тоесть что-бы если я написал в консоль слово которое я...

Подобие базы данных
А если быть точнее, то цель стоит- вывести перед пользователем список, из которого он нажатием...

Подобие math.h для геометрии
Существуют ли такие библиотеки? И где их взять.. Например, нужно найти расстояние от точки до...

Робот (подобие игры Sokoban)
Написать программу, на подобие игры Sokoban 1) создаёте матрицу нужного размера 2) из входного...

Как сделать подобие case из Pascal в C++
Есть программа, в ней 3 задачи, как сделать как в паскале что бы при открытии программы выводилось...

Выравнивание данных в структуре. Подобие alignas()
Здравствуйте , есть у меня одна проблема , связанная с необходимостью выровнять объекты в...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru