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

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

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

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

05.06.2016, 18:53. Просмотров 554. Ответов 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:
Необязательно себя утруждать и писать код, приму любую помощь. Достаточно просто объяснить, как это возможно реализовать, либо не возможно и свой вариант решения задачи.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 18:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подобие графа (C++):

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

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

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

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

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

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

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

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

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

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

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

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

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

Конденсация графа - C++
Найти число компонент сильной связности, вот может быть кто-нибудь реализовывал нечто подобное?


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.06.2016, 19:38
Ответ Создать тему
Опции темы

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