oop — Реализация объектно-ориентированных графов в Stack Overflow

Question

oop — Реализация объектно-ориентированных графов в Stack Overflow

Я должен реализовать симуляцию WWW на c ++ с использованием графиков, где узлы — это веб-страницы, а направленные ребра — это URL-адреса.

В школе, на нашем уровне, мы все еще начинаем в объектно-ориентированном программировании, поэтому они предложили реализовать с использованием списков смежности и матриц смежности, но они мне не нравятся, потому что они монстры памяти и очень ограничены.

Вопрос:
Можете ли вы предложить другую структуру данных (предпочтительно объектно-ориентированный материал), которая использует указатели (как ребра) на другие узлы, и где я могу динамически генерировать столько ребер, сколько мне нравится ???

Я прочитал это, но я не нашел ничего полезного:
Объектно-ориентированная реализация структур данных графа

-1

c++directed-acyclic-graphs graph object oop

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Честно говоря, попытка представить это только в одной структуре данных окажется довольно неэффективной. В действительности у вас есть меньший список регистраторов доменов, которые обеспечивают поиск. Что-то более точное, чем один тупой график, будет:

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

class Webpage;
class Registrar : public std::enable_shared_from_this<Registrar> {
public:
std::shared_ptr<Webpage> resolve(const std::string &url);
private:
std::map<std::string, std::shared_ptr<Webpage>> pages;
};

class Webpage {
public:
Webpage(std::shared_ptr<Registrar> registrar, const std::string &url) :
registrar(registrar),
url(url){
}

std::shared_ptr<Webpage> addLink(const std::string &url){
links.push_back(url);
return registrar->resolve(url);
}

std::vector<std::shared_ptr<Webpage>> resolvePageLinks(){
std::vector<std::shared_ptr<Webpage>> pages;
for (auto &linkUrl : links){
pages.push_back(registrar->resolve(linkUrl));
}
return pages;
}

std::string getUrl() const{
return url;
}
private:
std::string url;
std::shared_ptr<Registrar> registrar;
std::vector<std::string> links;
};

std::shared_ptr<Webpage> Registrar::resolve(const std::string &url){
auto found = pages.find(url);
if (found != pages.end()){
return found->second;
}
else{
auto webpage = std::make_shared<Webpage>(shared_from_this(), url);
pages.insert({url, webpage});
return webpage;
}
}

void printPageHierarchy(std::shared_ptr<Webpage> current, int depth, std::set<std::shared_ptr<Webpage>> &visited){
std::cout << std::string(3*depth, ' ');
std::cout << current->getUrl() << std::endl;
if (visited.find(current) == visited.end()){
visited.insert(current);
++depth;
for (auto page : current->resolvePageLinks()){
printPageHierarchy(page, depth, visited);
}
}else{
std::cout << std::string(3*depth, ' ');
std::cout << "..." << std::endl;
}
}

void printPageHierarchy(std::shared_ptr<Webpage> current){
std::set<std::shared_ptr<Webpage>> visited;
printPageHierarchy(current, 0, visited);
}

int main(){
auto registrar = std::make_shared<Registrar>();
auto site1 = registrar->resolve("site1.com");
site1->addLink("site2.com");
site1->addLink("site3.com")->addLink("site4.com")->addLink("site1.com");
std::cout << "From site1.com:" << std::endl;
printPageHierarchy(site1);

std::cout << "_____________\nFrom site3.com:" << std::endl;
printPageHierarchy(registrar->resolve("site3.com"));
}

Это довольно упрощенно и, очевидно, минимально. Ваш вопрос делает немного неясным, что именно ваши требования на самом деле.

2