-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathActorGraph.hpp
145 lines (120 loc) · 3.78 KB
/
ActorGraph.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*
* ActorGraph.hpp
* Author: Adrian Guthals
* Date: 2/24/2015
*
* This file is meant to exist as a container for starter code that you
* can use to read the input file format defined in movie_casts.tsv. Feel
* free to modify any/all aspects as you wish.
*/
/**
* Name: Rui Deng
* Dadong Jing
* Data: Mar 10, 2016
* Overview: this file contains all the methods to build actor graph
* Assignment number: PA4
*/
#ifndef ACTORGRAPH_HPP
#define ACTORGRAPH_HPP
#include <iostream>
#include "ActorNode.hpp"
#include "ActorEdge.hpp"
#include "Movie.hpp"
#include <unordered_map>
#include <climits>
#include <queue>
#include "UnionFind.hpp"
// Maybe include some data structures here
using namespace std;
class ActorGraph {
protected:
//variable for ActorGraph
unordered_map<string,ActorNode*> *actorMap;
unordered_map<string,Movie*> *MovieMap;
public:
/**
* ActorGraph constructor
*/
ActorGraph(void)
{
actorMap = new unordered_map<string,ActorNode*>();
MovieMap = new unordered_map<string,Movie*>();
//moviePQ = new priority_queue<Movie*,vector<Movie*>,movieCmp>();
}
/**
* destructor
*/
~ActorGraph()
{
deleteAll();
delete actorMap;
delete MovieMap;
}
/* delete all method for destructor */
void deleteAll();
/*add the edge connection for two actoNode and a movie
* Param: the actorA and actorB and their connection movie
* Return: void
*/
void connectGraph(ActorNode* start, ActorNode* end, Movie* movie);
/**
* BFS find method for finding the shortest connection in unweighted
* graph
* Param: the starting actor name and ending actor name
* Return: void
*/
void BFSFind(string actorF, string actorTo);
/**
* Dijkstra find method for finding the shortest path in weighted graph
* Param: the starting actor name and ending actor name
* Return: void
*/
void DijkstraFind(string actorF, string actorTo);
/* a helper method to write path to a output file
* Param: starting actor name, ending actor name, and the output file
* Return: void
*/
void writePathHelper(string actorF, string actorTo,ofstream& output);
/**
* a helper method to load just actors and movies without connecting
* the edges when doing actor connection
* Param: input file that we need to read
* Return: bool, true for successfully read and false for unsuccessfully read
*/
bool load(const char* in_filename);
/**
* a helper method to BFS the graph when doing action connection
* Param: starting actor name, ending actor name
* Return: int year which two actors starting become connected
*/
int BFSActorConnect(string actorF, string actorTo);
/**
* a helper method to using disjoint set to union nodes and then
* find the path between actors
* Param: starting actor name, ending actor name
* Return: int year which two actors starting become connected
*/
int UnionActorConnect(string actorF, string actorTo);
/* reverse vector helper method to get the correct path
* Parm: vector
* Return: vector in the reverse order
*/
vector<ActorNode*> reverse(vector<ActorNode*> in);
/** You can modify this method definition as you wish
*
* Load the graph from a tab-delimited file of actor->movie relationships.
*
* in_filename - input filename
* use_weighted_edges - if true, compute edge weights as
* 1 + (2015 - movie_year), otherwise all edge weights will be 1
*
* return true if file was loaded sucessfully, false otherwise
*/
bool loadFromFile(const char* in_filename, bool use_weighted_edges);
/* extension method to find the average dist to Kevin Bacon
* Param: actorStart name(which is Kevin Bacon)
* Return: double, average dist to Kevin Bacon
*/
double extension(string actorStart);
};
#endif //ACTORGRAPH_HPP