timeit

Програмиране с Python

Курс във Факултета по Математика и Информатика към СУ

Решение на Социална мрежа от Деница Петрова

Обратно към всички решения

Към профила на Деница Петрова

Резултати

  • 10 точки от тестове
  • 0 бонус точки
  • 10 точки общо
  • 8 успешни тест(а)
  • 0 неуспешни тест(а)

Код

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import datetime
from uuid import uuid4


class Post:
    def __init__(self, uuid, content):
        self.author = uuid
        self.published_at = datetime.datetime.now()
        self.content = content


class Queue:
    def __init__(self, limit):
        self.limit = limit
        self.queue = []

    def push(self, element):
        self.queue.append(element)
        if len(self.queue) > self.limit:
            self.queue.pop(0)

    def pop(self):
        if len(self.queue) > 0:
            self.queue.pop(0)


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = Queue(50)

    def __repr__(self):
        return str(self.uuid)

    def add_post(self, post_content):
        self.posts.push(Post(self.uuid, post_content))

    def get_post(self):
        return iter(self.posts.queue)


class Graph:
    def __init__(self):
        self.__network = {}

    def __iter__(self):
        return iter(self.network.values())

    def vertices(self):
        return self.__network.keys()

    def add_vertex(self, vertex):
        if vertex not in self.__network:
            self.__network[vertex] = []

    def delete_vertex(self, vertex):
        if vertex in self.__network:
            del self.__network[vertex]
        for k, v in self.__network.items():
            if vertex in v:
                v.pop(v.idex(vertex))

    def add_edge(self, frm, to):
        if frm in self.__network:
            if to not in self.__network[frm]:
                self.__network[frm].append(to)
        else:
            self.__network[frm] = [to]

    def delete_edge(self, frm, to):
        if to not in self.__network[frm]:
            return
        self.__network[frm].pop(self.__network[frm].index(to))

    def has_edge(self, frm, to):
        return to in self.__network[frm]

    def get_symmetric(self, vertex):
        result = []
        for x in self.__network[vertex]:
            if vertex in self.__network[x]:
                result.append(x)
        return result

    def get_vertices_to(self, frm):
        return self.__network[frm]

    def get_vertices_from(self, vertex):
        result = []
        for key, value in self.__network.items():
            if vertex in value:
                result.append(key)
        return result

    def find_shortest_path(self, frm, to, path=[]):
        path = path + [frm]
        if frm == to:
            return path
        if frm not in self.__network:
            return None
        shortest = None
        for vertex in self.__network[frm]:
            if vertex not in path:
                new_path = self.find_shortest_path(vertex, to, path)
                if new_path:
                    if not shortest or len(new_path) < len(shortest):
                        shortest = new_path
        return shortest


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class SocialGraph():
    def __init__(self):
        self.graph = Graph()
        self.users = {}

    def add_user(self, user):
        if user.uuid not in self.users:
            self.users[user.uuid] = user
            self.graph.add_vertex(user.uuid)
        else:
            raise UserAlreadyExistsError()

    def get_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        del self.users[user_uuid]
        self.graph.delete_vertex(user_uuid)

    def follow(self, follower_uuid, followee_uuid):
        self.graph.add_edge(follower_uuid, followee_uuid)

    def unfollow(self, follower, followee):
        self.graph.delete_edge(follower.uuid, followee.uuid)

    def is_following(self, follower_uuid, followee_uuid):
        return self.graph.has_edge(follower_uuid, followee_uuid)

    def followers(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return set(self.graph.get_vertices_from(user_uuid))

    def following(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return set(self.graph.get_vertices_to(user_uuid))

    def friends(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return self.graph.get_symmetric(user_uuid)

    def max_distance(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        max_dist = 0
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None:
                max_dist = max([max_dist, len(path)])
        return max_dist - 1

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid and to_user_uuid not in self.users:
            raise UserDoesNotExistError()
        path = self.graph.find_shortest_path(from_user_uuid, to_user_uuid)
        if path is None:
            raise UsersNotConnectedError
        return len(path) - 1

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        uuids = []
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None and len(path) == n + 1:
                uuids.append(path[-1])
        return uuids

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        followees = self.graph.get_vertices_to(user_uuid)
        posts = []
        for followee in followees:
            posts = posts + list(self.users[followee].get_post())
        posts.sort(key=lambda post: post.published_at, reverse=True)
        return iter(posts[offset:][:limit])

Лог от изпълнението

........
----------------------------------------------------------------------
Ran 8 tests in 0.063s

OK

История (3 версии и 3 коментара)

Деница обнови решението на 17.04.2016 10:03 (преди над 1 година)

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
import datetime
from uuid import uuid4


class Post:
    def __init__(self, uuid, content):
        self.author = uuid
        self.published_at = datetime.datetime.now()
        self.content = content


class Queue:
    def __init__(self, limit):
        self.limit = limit
        self.queue = []

    def size(self):
        return len(self.queue)

    def push(self, element):
        self.queue.append(element)
        if len(self.queue) > self.limit:
            self.queue.pop(0)

    def pop(self):
        if self.size == 0:
            return
        return self.queue.pop(0)

    def __str__(self):
        return str(self.queue)


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = Queue(50)

    def __repr__(self):
        return str(self.uuid)

    def add_post(self, post_content):
        self.posts.push(Post(self.uuid, post_content))

    def get_post(self):
        return iter(self.posts.queue)


class Graph:
    def __init__(self):
        self.__network = {}

    def __iter__(self):
        return iter(self.network.values())

    def vertices(self):
        return self.__network.keys()

    def add_vertex(self, vertex):
        if vertex not in self.__network:
            self.__network[vertex] = []

    def delete_vertex(self, vertex):
        if vertex in self.__network:
            del self.__network[vertex]
        for k, v in self.__network.items():
            if vertex in v:
                v.pop(v.idex(vertex))

    def add_edge(self, frm, to):
        if frm in self.__network:
            if to not in self.__network[frm]:
                self.__network[frm].append(to)
        else:
            self.__network[frm] = [to]

    def delete_edge(self, frm, to):
        if to not in self.__network[frm]:
            return
        self.__network[frm].pop(self.__network[frm].index(to))

    def has_edge(self, frm, to):
        return to in self.__network[frm]

    def get_symmetric(self, vertex):
        result = []
        for x in self.__network[vertex]:
            if vertex in self.__network[x]:
                result.append(x)
        return result

    def get_vertices_to(self, frm):
        return self.__network[frm]

    def get_vertices_from(self, vertex):
        result = []
        for key, value in self.__network.items():
            if vertex in value:
                result.append(key)
        return result

    def find_shortest_path(self, frm, to, path=[]):
        path = path + [frm]
        if frm == to:
            return path
        if frm not in self.__network:
            return None
        shortest = None
        for vertex in self.__network[frm]:
            if vertex not in path:
                new_path = self.find_shortest_path(vertex, to, path)
                if new_path:
                    if not shortest or len(new_path) < len(shortest):
                        shortest = new_path
        return shortest


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class SocialGraph():
    def __init__(self):
        self.graph = Graph()
        self.users = {}

    def add_user(self, user):
        if user.uuid not in self.users:
            self.users[user.uuid] = user
            self.graph.add_vertex(user.uuid)
        else:
            raise UserAlreadyExistsError()

    def get_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        del self.users[user_uuid]
        self.graph.delete_vertex(user_uuid)

    def follow(self, follower_uuid, followee_uuid):
        self.graph.add_edge(follower_uuid, followee_uuid)

    def unfollow(self, follower, followee):
        self.graph.delete_edge(follower.uuid, followee.uuid)

    def is_following(self, follower_uuid, followee_uuid):
        return self.graph.has_edge(follower_uuid, followee_uuid)

    def followers(self, user_uuid):
        return set(self.graph.get_vertices_from(user_uuid))

    def following(self, user_uuid):
        return set(self.graph.get_vertices_to(user_uuid))

    def friends(self, user_uuid):
        return self.graph.get_symmetric(user_uuid)

    def max_distance(self, user_uuid):
        max_dist = 0
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None:
                max_dist = max([max_dist, len(path)])
        return max_dist - 1

    def min_distance(self, from_user_uuid, to_user_uuid):
        path = self.graph.find_shortest_path(from_user_uuid, to_user_uuid)
        if path is None:
            raise UsersNotConnectedError
        return len(path) - 1

    def nth_layer_followings(self, user_uuid, n):
        uuids = []
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None and len(path) == n + 1:
                uuids.append(path[-1])
        return uuids

    def generate_feed(self, user_uuid, offset=0, limit=10):
        followees = self.graph.get_vertices_to(user_uuid)
        posts = []
        for followee in followees:
            posts = posts + list(self.users[followee].get_post())
        posts.sort(key=lambda post: post.published_at, reverse=True)
        return iter(posts[offset:][:limit])

Деница обнови решението на 17.04.2016 10:07 (преди над 1 година)

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
import datetime
from uuid import uuid4


class Post:
    def __init__(self, uuid, content):
        self.author = uuid
        self.published_at = datetime.datetime.now()
        self.content = content


class Queue:
    def __init__(self, limit):
        self.limit = limit
        self.queue = []

    def push(self, element):
        self.queue.append(element)
        if len(self.queue) > self.limit:
            self.queue.pop(0)

    def pop(self):
        if len(self.queue) > 0:
            self.queue.pop(0)


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = Queue(50)

    def __repr__(self):
        return str(self.uuid)

    def add_post(self, post_content):
        self.posts.push(Post(self.uuid, post_content))

    def get_post(self):
        return iter(self.posts.queue)


class Graph:
    def __init__(self):
        self.__network = {}

    def __iter__(self):
        return iter(self.network.values())

    def vertices(self):
        return self.__network.keys()

    def add_vertex(self, vertex):
        if vertex not in self.__network:
            self.__network[vertex] = []

    def delete_vertex(self, vertex):
        if vertex in self.__network:
            del self.__network[vertex]
        for k, v in self.__network.items():
            if vertex in v:
                v.pop(v.idex(vertex))

    def add_edge(self, frm, to):
        if frm in self.__network:
            if to not in self.__network[frm]:
                self.__network[frm].append(to)
        else:
            self.__network[frm] = [to]

    def delete_edge(self, frm, to):
        if to not in self.__network[frm]:
            return
        self.__network[frm].pop(self.__network[frm].index(to))

    def has_edge(self, frm, to):
        return to in self.__network[frm]

    def get_symmetric(self, vertex):
        result = []
        for x in self.__network[vertex]:
            if vertex in self.__network[x]:
                result.append(x)
        return result

    def get_vertices_to(self, frm):
        return self.__network[frm]

    def get_vertices_from(self, vertex):
        result = []
        for key, value in self.__network.items():
            if vertex in value:
                result.append(key)
        return result

    def find_shortest_path(self, frm, to, path=[]):
        path = path + [frm]
        if frm == to:
            return path
        if frm not in self.__network:
            return None
        shortest = None
        for vertex in self.__network[frm]:
            if vertex not in path:
                new_path = self.find_shortest_path(vertex, to, path)
                if new_path:
                    if not shortest or len(new_path) < len(shortest):
                        shortest = new_path
        return shortest


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class SocialGraph():
    def __init__(self):
        self.graph = Graph()
        self.users = {}

    def add_user(self, user):
        if user.uuid not in self.users:
            self.users[user.uuid] = user
            self.graph.add_vertex(user.uuid)
        else:
            raise UserAlreadyExistsError()

    def get_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        del self.users[user_uuid]
        self.graph.delete_vertex(user_uuid)

    def follow(self, follower_uuid, followee_uuid):
        self.graph.add_edge(follower_uuid, followee_uuid)

    def unfollow(self, follower, followee):
        self.graph.delete_edge(follower.uuid, followee.uuid)

    def is_following(self, follower_uuid, followee_uuid):
        return self.graph.has_edge(follower_uuid, followee_uuid)

    def followers(self, user_uuid):
        return set(self.graph.get_vertices_from(user_uuid))

    def following(self, user_uuid):
        return set(self.graph.get_vertices_to(user_uuid))

    def friends(self, user_uuid):
        return self.graph.get_symmetric(user_uuid)

    def max_distance(self, user_uuid):
        max_dist = 0
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None:
                max_dist = max([max_dist, len(path)])
        return max_dist - 1

    def min_distance(self, from_user_uuid, to_user_uuid):
        path = self.graph.find_shortest_path(from_user_uuid, to_user_uuid)
        if path is None:
            raise UsersNotConnectedError
        return len(path) - 1

    def nth_layer_followings(self, user_uuid, n):
        uuids = []
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None and len(path) == n + 1:
                uuids.append(path[-1])
        return uuids

    def generate_feed(self, user_uuid, offset=0, limit=10):
        followees = self.graph.get_vertices_to(user_uuid)
        posts = []
        for followee in followees:
            posts = posts + list(self.users[followee].get_post())
        posts.sort(key=lambda post: post.published_at, reverse=True)
        return iter(posts[offset:][:limit])

Имаш чупещи се примерни тестове, което е проблем.

Иначе:

  • from queue import Queue :)
  • Харесва ми отделния Graph клас, така че SocialGraph да не се занимава с алгоритми за обхождания и търсене.
  • Ребрата в графа ти няма нужда да са подредени. Ако ползваш set, вместо list много неща ще станат по-лесно.

Не са част от примерните тестове, но погледни условието и помисли дали връщаш грешки на всички места, на които се очаква. Мини още веднъж през условието и се увери, че навсякъде приемаш и връщаш каквото се очаква :)

Деница обнови решението на 18.04.2016 13:26 (преди над 1 година)

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import datetime
from uuid import uuid4


class Post:
    def __init__(self, uuid, content):
        self.author = uuid
        self.published_at = datetime.datetime.now()
        self.content = content


class Queue:
    def __init__(self, limit):
        self.limit = limit
        self.queue = []

    def push(self, element):
        self.queue.append(element)
        if len(self.queue) > self.limit:
            self.queue.pop(0)

    def pop(self):
        if len(self.queue) > 0:
            self.queue.pop(0)


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = Queue(50)

    def __repr__(self):
        return str(self.uuid)

    def add_post(self, post_content):
        self.posts.push(Post(self.uuid, post_content))

    def get_post(self):
        return iter(self.posts.queue)


class Graph:
    def __init__(self):
        self.__network = {}

    def __iter__(self):
        return iter(self.network.values())

    def vertices(self):
        return self.__network.keys()

    def add_vertex(self, vertex):
        if vertex not in self.__network:
            self.__network[vertex] = []

    def delete_vertex(self, vertex):
        if vertex in self.__network:
            del self.__network[vertex]
        for k, v in self.__network.items():
            if vertex in v:
                v.pop(v.idex(vertex))

    def add_edge(self, frm, to):
        if frm in self.__network:
            if to not in self.__network[frm]:
                self.__network[frm].append(to)
        else:
            self.__network[frm] = [to]

    def delete_edge(self, frm, to):
        if to not in self.__network[frm]:
            return
        self.__network[frm].pop(self.__network[frm].index(to))

    def has_edge(self, frm, to):
        return to in self.__network[frm]

    def get_symmetric(self, vertex):
        result = []
        for x in self.__network[vertex]:
            if vertex in self.__network[x]:
                result.append(x)
        return result

    def get_vertices_to(self, frm):
        return self.__network[frm]

    def get_vertices_from(self, vertex):
        result = []
        for key, value in self.__network.items():
            if vertex in value:
                result.append(key)
        return result

    def find_shortest_path(self, frm, to, path=[]):
        path = path + [frm]
        if frm == to:
            return path
        if frm not in self.__network:
            return None
        shortest = None
        for vertex in self.__network[frm]:
            if vertex not in path:
                new_path = self.find_shortest_path(vertex, to, path)
                if new_path:
                    if not shortest or len(new_path) < len(shortest):
                        shortest = new_path
        return shortest


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class SocialGraph():
    def __init__(self):
        self.graph = Graph()
        self.users = {}

    def add_user(self, user):
        if user.uuid not in self.users:
            self.users[user.uuid] = user
            self.graph.add_vertex(user.uuid)
        else:
            raise UserAlreadyExistsError()

    def get_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        del self.users[user_uuid]
        self.graph.delete_vertex(user_uuid)

    def follow(self, follower_uuid, followee_uuid):
        self.graph.add_edge(follower_uuid, followee_uuid)

    def unfollow(self, follower, followee):
        self.graph.delete_edge(follower.uuid, followee.uuid)

    def is_following(self, follower_uuid, followee_uuid):
        return self.graph.has_edge(follower_uuid, followee_uuid)

    def followers(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return set(self.graph.get_vertices_from(user_uuid))

    def following(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return set(self.graph.get_vertices_to(user_uuid))

    def friends(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        return self.graph.get_symmetric(user_uuid)

    def max_distance(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        max_dist = 0
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None:
                max_dist = max([max_dist, len(path)])
        return max_dist - 1

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid and to_user_uuid not in self.users:
            raise UserDoesNotExistError()
        path = self.graph.find_shortest_path(from_user_uuid, to_user_uuid)
        if path is None:
            raise UsersNotConnectedError
        return len(path) - 1

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        uuids = []
        for uuid in self.graph.vertices():
            path = self.graph.find_shortest_path(user_uuid, uuid)
            if path is not None and len(path) == n + 1:
                uuids.append(path[-1])
        return uuids

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.users:
            raise UserDoesNotExistError()
        followees = self.graph.get_vertices_to(user_uuid)
        posts = []
        for followee in followees:
            posts = posts + list(self.users[followee].get_post())
        posts.sort(key=lambda post: post.published_at, reverse=True)
        return iter(posts[offset:][:limit])