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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
vadim_bz
1 / 1 / 1
Регистрация: 11.04.2015
Сообщений: 35
#1

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

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

Имеется примерно такой вот класс:
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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 18:53     Подобие графа
Посмотрите здесь:

Подобие игры - C++
Ребята. Начал писать, но тут проблема. Программа не работает. Он запускает лишь ранее скомпилированный код (который &quot;загружает&quot; игру), а...

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

Подобие базы данных - C++
А если быть точнее, то цель стоит- вывести перед пользователем список, из которого он нажатием клавиши 1 2 или 3 4 5выберет интересующий...

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

Робот (подобие игры Sokoban) - C++
Написать программу, на подобие игры Sokoban 1) создаёте матрицу нужного размера 2) из входного файла считываете заполнение поля 3)...

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

Подобие MessageBox выводящего INT и LPCSTR . Не тупо ли ? - C++
Привыкшему к удобствам PHP с++ нубу захотелось сделать такое вот извращение.. Функция выводит текст как INT типа так и строкового типа......

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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_
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_
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
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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_
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_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 19:13     Подобие графа #12
За один элемент всё держится что ли?
Если так, то можно создать временный массив, закинуть в него указатели на все элементы.
Затем пройтись по массиву и очистить у каждого объекта ссылки на соседние комнаты (не удаляя объекты).
После чего в цикле удалить все объекты в массиве.

Но точно сказать, не понимая структуры решения, я не могу.
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
07.06.2016, 19:34     Подобие графа #13
Используйте shared_ptr.
Vort_
186 / 186 / 52
Регистрация: 10.07.2012
Сообщений: 400
07.06.2016, 19:35     Подобие графа #14
Цитата Сообщение от Toshkarik Посмотреть сообщение
Используйте shared_ptr.
Только поможет ли это, если комнаты связаны в кольцо?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2016, 19:38     Подобие графа
Еще ссылки по теме:

Обращение к методам базового класса (есть ли подобие base/super?) - C++
Понятное дело, что можно обращаться к методам базового класса так: BaseClass::hisMethod(); Однако это зависимость от названия класса. Не...

Обход графа в ширину - C++
Подскажите, как во время обхода графа в ширину помечать вершины как четные и не четные?

Варианты обхода графа - C++
подскажите пожалуйста сколько путей существует для такого графа, чтобы проходить через каждую Добавлено через 44 секунды или...

Обход в ширину графа - C++
Здравствуйте, помогите пожалуйста разобраться что не так в алгоритме работы обхода в ширину графа( Заданию матрицу Число вершин ...

Хроматическое число графа - C++
Здравствуйте =) Не можете подсказать какой-либо алгоритм нахождения хроматического числа графа


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

Или воспользуйтесь поиском по форуму:
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
07.06.2016, 19:38     Подобие графа #15
Да, упустил из вида. Тогда weak_ptr.
Yandex
Объявления
07.06.2016, 19:38     Подобие графа
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru