0
\$\begingroup\$

I am working on implementing a graph to solve shortest path between two vertices using Dijkstra's algorithm. Trying to keep it at least somewhat efficient because I know there are some time constraints on how long I have to find shortest path for 100 pairs of actors/actresses.

I am limited to just using the data structures from the STL. I spent some time in the lab today with my TA designing everything on paper and thought about having both a vertex and edge class. I also thought of making an actual graph class that could speed up searching by using unordered_maps.

What I am a little unsure about is the efficiency of this design. I know unordered_maps are really fast so I was hoping to take advantage of the \$O(1)\$ find time. It's not really \$O(1)\$ I think because, even though the unordered_map will give me a the movie vector or actor vector in \$O(1)\$ time, I potentially have to search that entire vector for the actor or movie I am searching for. (Though those vectors aren't going to be incredibly long. They just contain the cast of a single movie or a single actor's list of movies they have been in.)

I know I want to use the speed of an unordered_map, but the way I am currently designing this feels like I am actually not taking advantage of the unordered_map really. Why? Because I feel like I could do everything I just described without the Graph class by just using ActorNodes along with their vectors of Movie pointers and Movie objects along with their vectors of ActorNode pointers. I could do exactly what I want to do with the unordered_maps already and it sounds like it would be just as efficient as the way I am thinking of with unordered_maps. That makes me feel like I am missing something and am designing this incorrectly.

The problem I am solving is I have 1 minute to find the shortest path between 100 pairs of actors in a pretty large graph (where the edges of my graph represent a movie those two actors were in together) using Dijkstra's algorithm. The graph can be either weighted or unweighted. Weight is determined by: 1+(2015-(the year the movie was made)).

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

 /*             OBJECT ORIENTED DESIGN
  *
  *        (Graph)1 <----------> n(Actor object)
  *             1                        n
  *              \                       /\
  *                 \                    |
  *                    \                 | 
  *                       \              |
  *                          \           \/
  *                             \        n
  *                              n(Movie object)
  */

 /* THE IDEA:
  * Represent a graph with two unordered maps. One to hold all the 
  * actorNodes of a graph and a vector of pointers to movies that particular actor is in
  * as well as an unordered_map of movies with a vector of pointers to actors that are in
  * that particular movie. I believe doing this will accurately represent a graph.
  */

 class Movie;       // forward declaration to shut compiler up.
 class ActorNode;   // forward declaration to shut compiler up.

 /* Graph object that holds all ActorNodes and Movies */
 class Graph {

     private:
         /*Member Variables*/
         std::unordered_map<std::string,std::vector<Movie*>> vertices;
         std::unordered_map<std::string,std::vector<ActorNode*>> edges;

     public:
         /*Constructor*/
         Graph() {}

         /*Destructor*/
         ~Graph();

         /*Member Functions*/
    }
 };

 /* (Vertex) Object Class to represent actors */
class ActorNode {

     //can be converted to struct instead of class??

     private:
         /*Member Variables*/
         std::string name;
         std::vector<Movie*> movies;

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

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

         std::vector<Movie*> getMovies();

         /*Member Functions*/

 };

 /* Object class to hold movies. Edges? */

class Movie {

     //can be converted to struct instead of class?

     private:
         std::string movie;
         int year;
         int weight;
         std::vector<ActorNode*> cast;

     public:
         /*Constructor*/
         Movie() : movie(""), year(1), weight(1) {}

         /*Getters and Setters*/
         std::string getMovie();
         void setMovie(std::string movie);

         int getYear();
   I     void setYear(int yr);

         int getWeight();
         void setWeight(int wt);

         std::vector<ActorNode*> getCast();

         /*Member Functions*/

 };
\$\endgroup\$
  • \$\begingroup\$ It depends. What are the questions you are trying to answer with the graph. If you are just doing actor to actor searches then it is overkill. \$\endgroup\$ – Martin York May 20 '17 at 17:43
  • \$\begingroup\$ I have 1 minute to find the shortest path between 100 pairs of actors in a pretty large graph using djikstra's algorithm. What do you mean it is overkill if you don't mind explaining please. \$\endgroup\$ – Koala May 20 '17 at 18:43
  • 1
    \$\begingroup\$ Then your graph is overkill. Simply have one set (of actors) std::unordered_set<Actor>. Each Actor contains a vector of Actor* (links). Each link represents a film the actors have in common. The use of unordered_set rather than set is good when building the graph (traversal will finding should be trivial). \$\endgroup\$ – Martin York May 20 '17 at 19:34
0
\$\begingroup\$

I think the solution here is quite close to what Loki said. Every actor is a node and the films they share build and equivalence class, which comes down to an edge in the graph.

Now the trick is to avoid loops in the graph. Here you should google Johnson's algorithm for finding simple cycles. The idea rather simple, whenever you visit a node (actor) you mark it/him and do not traverse further when you find him again. It guarantees that the longest path might only be N-1 steps.

Together with building equivalence classes of the movies you end up with a rather small graph, which should be easy to traverse.

So you end up with a simpl construct:

struct actor {
    actor(const std::string& Name)
        : name(Name);

    void AddPartner(actor* partner) {
        partners.push_back(partner);
    }

    const std::string   name;
    std::vector<actor*> partners;
}

class graph {
    AddActor(const std::string& name) {
        actors.emplace_back(std::make_unique<actor>(name));
    }
    void AddPartners(const std::string& name1, const std::string& name2) {
        actor* actor1 = nullptr;
        actor* actor2 = nullptr;
        for (auto&& act : actors) {
            if (act->name == name1) {
                actor1 = act.get();
                if(actor2)
                    break;
            } 
            if (act->name == name2) {
                actor2 = act.get();
                if(actor1)
                    break;
            }
        }
        actor1->AddPartner(actor2);
        actor2->AddPartner(actor1);
    }
private:
    std::vector<std::unique_ptr<actor>> actors;
}

Then what you need is a simple breadth first search to find the shortest path:

void findShortestLink(const std::string& name1, const std::string& name2) {
    actor* firstActor = (*std::find(actors.begin(), actors.get(), [&name1](auto&& act) { return act.get()->name == name1;}).get(); 
    std::queue<actor*> queue;
    queue.push(firstActor);
    std::unordered_set<actor*> visited;
    visited.insert(firstActor);
    while(!queue.empty()) {
        actor* current = queue.front();
        queue.pop();
        for (auto&& partner : partners) {
            if (visited.count(partner) == 0) {
                if (partner->name == name2) {
                    std::queue<actor*> emptyQueue;
                    std::swap(queue, emptyQueue);
                    break;
                } 
                visited.insert(partner);
                queue.push(partner);
            }
        }
    }
}

But how can you know how many movies you walked? Here you can add a member to the actors, that remembers the movie they come from.

 struct actor {
    actor(const std::string& Name)
        : name(Name);

    void AddPartner(actor* partner) {
        partners.push_back(partner);
    }

    const std::string   name;
    std::vector<actor*> partners;
    actor* predecessor;
}

Now you can set them and walk them back if you found the right one

size_t findShortestLink(const std::string& name1, const std::string& name2) {
    actor* firstActor = (*std::find(actors.begin(), actors.get(), [&name1](auto&& act) { return act.get()->name == name1;}).get(); 
    std::queue<actor*> queue;
    queue.push(firstActor);
    std::unordered_set<actor*> visited;
    visited.insert(firstActor);
    while(!queue.empty()) {
        actor* current = queue.front();
        queue.pop();
        for (auto&& partner : partners) {
            if (visited.count(partner) == 0) {
                partner->predecessor = current;
                if (partner->name == name2) {
                    std::queue<actor*> emptyQueue;
                    std::swap(queue, emptyQueue);
                    size_t result = 0;
                    while (partner->predecessor != firstActor) {
                        result++;
                        partner = partner->predecessor;
                    }
                    return result;
                } 
                visited.insert(partner);
                queue.push(partner);
            }
        }
    }
    return 0;
}

Now how can we add the weights? This depends on personal preference. You can either make partners a std::vector<std::pair<actor*, size_t>> and add first and second appropriately or add a std::unordered_map<actor*, size_t> to the actor.

Any way you obviously just need to increment/multiply (depending on how your weight affects the score) result with the weight.

EDIT:

If you really need the movie info you should go with a multimap and create a simple struct that stores the movie data. Then the while clause would obviously be:

std::vector<std::vector<movieInfo>>;                   
while (partner->predecessor != firstActor) {
    result.emplace_back(partner->GetMovieInfo(partner->predecessor);
    partner = partner->predecessor;
}

Edit2: What to do about movies?

So you want to keep track of the movies. That should happen when you create a link between the two actors. The easiest way would be with an array of structures that hod the movie information.

We can easily adopt our actor class for that purpose

struct movieInfo {
    // Whatever you need here
}

struct actor {
    actor(const std::string& Name)
        : name(Name);

    void AddPartner(actor* partner, movieInfo&& info) {
        partners.push_back(partner);
        if (movies.count(partner) == 0) {
            movies.insert(std::make_pair<actor*, std::vector<movieInfo>(partner, std::vector<movieInfo>(1, std::move(info))));
        } else {
            movies.at(partner).emplace_back(std::move(info));
        }
    }

    const std::string   name;
    std::vector<actor*> partners;
    std::unordered_map<actor*, std::vector<movieInfo>> movies;
}

Now you can use the above alternation of the result and return a vector of the vector of movies

std::vector<std::vector<movieInfo>>;                   
while (partner->predecessor != firstActor) {
    result.emplace_back(partner->GetMovieInfo(partner->predecessor);
    partner = partner->predecessor;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.