그래프를 작성하기에 충분한 정보를 저장하는 중

Question

#ifndef ACTOR_H 
#define ACTOR_H 

#include<vector> 
#include<iostream> 
#include<queue> 
#include<string> 

struct Link; 
/* (Vertex) Object Class to represent actors */ 
class ActorNode { 
    private: 
     /*Member Variables*/ 
     std::string name; 
     std::vector<Link*> links; 

    public: 
     /*Constructor*/ 
     ActorNode() : name("") {} 

     /*Getters and Setters*/ 
     std::string getName(); 
     void setName(std::string actor); 

     std::vector<Link*> getLinks(); 

     /*Member Functions*/ 
     //void addLink(); 
}; 
struct Link { 

    /*Member Variables*/ 
    ActorNode* cs1; 
    ActorNode* cs2; 
    std::string movieTitle; 
    int year; 
    int weight; 

    /*Constructor*/ 
    Link() : cs1(0), cs2(0), movieTitle(""), year(1), weight(1) {} 

}; 
#endif 

저녁 모두. 그래서 저는 두 배우가 함께 행동 한 영화의 연결된 액터의 그래프에서 두 배우 (가중치와 비가 중도) 사이의 최단 경로를 풀기위한 그래프 구현 작업을하고 있습니다. 최단 경로 문제를 풀기위한 것입니다. Dijkstra의 알고리즘을 사용합니다.

내 구현은 액터의 이름 인 문자열과 두 액터를 연결하는 "링크/무비"의 벡터가 들어있는 벡터를 포함하는 ActorNode 클래스를 갖기를 원합니다. My Link 클래스에는 두 개의 별을 연결하는 두 개의 ActorNode 포인터가 있습니다. 그리고 영화의 이름, 만든 해 그리고 나중에 나오는 것입니다 (나중에 재생 될 것입니다)

여기 내 문제는 다음과 같습니다. 내가 actorName에서 moviename movieYear 그냥 ... 모든 라인이있는 큰 텍스트 파일의 해제 그래프를 구축하고

내가 효율적으로 찾을 수와 배우 사이에 내 링크를 생성하기에 충분한 정보를 저장하고 생각하지 않는다. 나는이 문제를 구체적으로 해결할 방법을 찾고 있었다. 키가 무비 이름이되고 값이 해당 무비의 캐스트로 구성된 ActorNode 포인터 벡터 인 hashmap을 만들려고합니다. 그와 같은 무언가가 내가 믿는 바로 그 배우들 사이의 연결 고리를 만들 수있게 해줄 것입니다. ' 나는이 데이터 구조를 저장할 위치에 대해 다소 혼란 스럽다. 나는 확실히 모든 ActorNode에 대한 그래프에서 모든 영화의 모든 캐스트에 대한 해시 맵을 원하지 않습니다.

전역 변수와 같은 것을 작성하는 것이 좋지 않습니까?

Answer 1

두 개의지도 (해시 또는 다른 다양성), 어떤 종류의 액터 이름을 Actor 데이터 구조에 매핑하고, 다른 하나는 Movie 데이터 구조의 일종으로 매핑하는 것이 좋습니다. Actor 및 Move은지도의 존재를 알 필요가 없습니다.

지도를 계산하고 반환하는 함수에서지도 로컬 변수를 모두 만들 수 있습니다. 함수가 반환되면지도가 자동으로 소멸됩니다. 그러나 그래프의 모든 노드에 대한 포인터를 보유 할 수있는 데이터 구조가 필요합니다. 이를위한 별도의 포인터 벡터를 작성할 수 있습니다. 그러나지도 자체는 완벽하게 유용하며 그래프가 준비되면 배우와 영화를 찾는 추가 목적을 수행합니다. 여기

이 (이 토론에 필수적인 검증되지 않은 의사 만 부분)처럼 보일 수있는 방법은 다음과 같습니다 원칙적으로

class Movie; 

class Actor { 
    std::string name; 
    std::vector<Movie*> career; 
}; 

class Movie { 
    std::string title; 
    std::vector<Actor*> cast; 
}; 

class Graph { 
    std::unordered_map<std::string, std::unique_ptr<Actor>> actors; 
    std::unordered_map<std::string, std::unique_ptr<Movie>> movies; 
}; 

이이 그래프를 나타냅니다. 두 종류의 노드는 영화와 배우의 두 부분으로 된 그래프라는 사실을 암시합니다. 원래 영화를 가장자리로 원했던 그래프는 아니지만 거의 수정하지 않고 Dijkstra 또는 다른 그래프 알고리즘을 적용 할 수 있습니다.

원하는 경우이 이진 그래프에서 의도 한 그래프의 실제 표현을 만들 수 있습니다. 각 영화에 액터의 각 쌍에 대한 링크를 추가하기 만하면됩니다. 그러나 링크를 열거하기를 원할 때마다 Movie 노드를 직접 사용할 수 있기 때문에 중복 될 수 있습니다.