Speichern genug Informationen zum Erstellen von Grafik

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 

Abend alle. Also arbeite ich an einer Graphenimplementierung, die den kürzesten Weg zwischen zwei (gewichteten und ungewichteten) Akteuren in einem Graphen von Schauspielern lösen soll, die durch Filme verbunden sind, in denen diese beiden Akteure zusammen agieren. Ich soll die Probleme des kürzesten Weges lösen Verwenden des Dijkstra-Algorithmus.

Meine Implementierung ist Ich möchte eine ActorNode-Klasse haben, die eine Zeichenfolge enthält, die den Namen des Schauspielers und einen Vektor, der einen Vektor von "Links/Filme" enthält, die zwei Akteure verbindet. Meine Link-Klasse hat nur zwei ActorNode-Zeiger, um die beiden Co-Stars zu verbinden und dann den Namen des Films, das Jahr, in dem er gemacht wurde, und das Gewicht (das später ins Spiel kommt)

ich baue das Diagramm aus einer großen Textdatei, die diese nur in jeder Zeile hat ... actorname moviename movieYear

glaube ich nicht, dass ich genug Informationen speichere effizient zu finden und meine Verbindungen zwischen den Akteuren zu schaffen. Ich suchte nach einer Methode, um dieses Problem spezifisch zu lösen. Ich dachte an eine hashmap, wo der Schlüssel wäre ein Film Name und der Wert wäre ein Vektor von ActorNode Zeigern, die aus der Besetzung des Films besteht. So etwas würde mir erlauben, meine Verbindungen zwischen Schauspielern ziemlich schnell aufzubauen, glaube ich. Ich bin ein wenig verwirrt darüber, wo ich diese Datenstruktur speichern könnte. Ich würde sicherlich keine hashmap für alle Casts aller Filme in meinem Graphen für jeden einzelnen ActorNode wollen.

Wäre es eine schlechte Programmierung, etwas wie eine globale Variable zu machen?

Answer 1

Sie möchten wahrscheinlich zwei Karten (Hash oder eine andere Sorte), eine Zuordnung Actor-Namen zu einer Art von Actor Datenstruktur, und eine andere Zuordnung von Filmtiteln zu einer Art von Movie Datenstruktur. Actor und müssen nicht die Existenz der Karten bewusst sein.

Sie können beide Zuordnungen zu lokalen Variablen in einer Funktion machen, die Ihr Diagramm berechnet und zurückgibt. Sobald die Funktion zurückkehrt, werden die Karten automatisch zerstört. Sie benötigen jedoch eine Datenstruktur, um Zeiger auf alle Knoten Ihres Graphen zu halten. Sie können einen separaten Vektor von Zeigern dafür erstellen. Allerdings sind die Karten selbst dafür perfekt geeignet und dienen zusätzlich dazu, Ihre Schauspieler und Filme nachzusehen, sobald die Grafik fertig ist.

Hier ist, wie dies aussehen könnte (ungetestet Pseudo-Code, nur Teile wesentlich für diese Diskussion):

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; 
}; 

Grundsätzlich dies Ihr Diagramm darstellt. Zwei Arten von Knoten weisen auf die Tatsache hin, dass es sich um ein zweiteiliges Diagramm von Filmen und Schauspielern handelt, nicht genau das Diagramm, das Sie ursprünglich mit Filmen als Kanten wollten, aber Sie können Dijkstra oder einen anderen Grafikalgorithmus mit wenig oder keiner Modifikation anwenden.

Wenn Sie möchten, können Sie aus diesem zweiteiligen Diagramm eine physische Darstellung Ihres beabsichtigten Graphen erstellen. Fügen Sie einfach für jedes Paar von Akteuren in jedem Film einen Link hinzu. Dies ist jedoch wahrscheinlich überflüssig, denn wann immer Sie Links aufzählen möchten, können Sie einfach den Movie-Knoten direkt verwenden.