Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Graph

Автор: sol78 24.7.2008, 13:50

Нужно спроектировать Граф.
Который состоит из Element, Link, Weight.
Подскажите плз, хороший алгоритм, удобный в реализации(желательно без матрицы).
И как его (алгоритм) лучше реализовать, с точки зрения дизайна?

Автор: jonie 24.7.2008, 20:19

тут обсуждаются проблемы с языком С++. проектирование в другом разделе.
возьмите исходники нейросетевых библиотек, там все это уже реализовано.... да и чистые графовые либы тоже имеются...

и чем плоха матрица (например смежности)? матрица легко опишет все связи, и займет минимум места. ну а веса связей можно хранить в ней же.

Автор: anatox91 24.7.2008, 20:33

http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/table_of_contents.html

Автор: Ulysses4j 24.7.2008, 20:44

Цитата(anatox91 @ 24.7.2008, 21:33

)

Boost Graph Library

А еще лучше, наверное, посмотреть книжку по этой библиотеке на русском языке (она вроде бы вполне гуглабельна). Вообще, реализация графов это задача, которая имеет один из самых высоких коэффициентов по соотношению реальная сложность/кажущаяся простота. Так что будьте осторожны smile

Автор: sol78 28.7.2008, 10:49

Код


#ifndef _GRAPHO_
#define _GRAPHO_

#include <iostream>
#include <vector>
#include <set>
#include <string>

using namespace std;

template <class T, class W > class grapho
{
private:

    template < class T, class W > class element;

    template < class T, class W > struct link
    {
        element< T, W > *    m_source;
        element< T, W > *    m_destination;
        W                    m_weight;
    };

    template < class T, class W > struct element
    {
        vector< link< T, W > >*    m_destinations;
        T node;
    };

    string m_name;

    set< element < W, T > >    m_elements;
    set< link < W, T > >    m_links;

public:
    grapho(char* name):m_name(name)
    {}

};

#endif

Вот наметки графа, я пошла по пути навороченного Линкед Листа.
Может будут какието соображениыа по этому поводу?

Автор: Alek86 28.7.2008, 16:47

sol78, ты читаешь, что другие иногда в твоей теме пишут? smile

если тебе нужно самой спроектировать граф, то лучше задавать вопросы в соотв. разделе (и не типа "спроектируйте-ка мне такую штуку")
если же просто нужен граф, то тебе ужен посоветовали обратить внимание на Boost Graph Library

Автор: Ulysses4j 28.7.2008, 17:01

sol78, вы бы попытались на человеческом языке разъяснить основные архитектурные решения в вашей реализации. Комментарии хотя бы в коде сделали...