URL: https://github.com/freeipa/freeipa/pull/905 Author: slaykovsky Title: #905: ipapython/graph.py complexity optimization. Action: opened

## Advertising

PR body: """ Hi! I've just read the code and I saw that graph bfs uses not optimal for Python solution. So I've edited it with more optimal one. Also I've changed string formatting for Value Errors raise and deletion of edges in remove_vertex method because there's no need to store redundant variable in memory. Could you please take a look and leave some comments and maybe merge it. Thanks! """ To pull the PR as Git branch: git remote add ghfreeipa https://github.com/freeipa/freeipa git fetch ghfreeipa pull/905/head:pr905 git checkout pr905

From 92d1a64597fa3b682199652ba1d57484a43de5c5 Mon Sep 17 00:00:00 2001 From: Aleksei Slaikovskii <aslai...@redhat.com> Date: Fri, 7 Jul 2017 14:54:30 +0200 Subject: [PATCH] ipapython/graph.py complexity optimization. Hi! I've just read the code and I saw that graph bfs uses not optimal for Python solution. So I've edited it with more optimal one. Also I've changed string formatting for Value Errors raise and deletion of edges in remove_vertex method because there's no need to store redundant variable in memory. Could you please take a look and leave some comments and maybe merge it. Thanks! --- ipapython/graph.py | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-) diff --git a/ipapython/graph.py b/ipapython/graph.py index 6b31c915c0..347c29905e 100644 --- a/ipapython/graph.py +++ b/ipapython/graph.py @@ -1,6 +1,7 @@ # -# Copyright (C) 2015 FreeIPA Contributors see COPYING for license +# Copyright (C) 2015-2017 FreeIPA Contributors see COPYING for license # +from collections import deque class Graph(object): @@ -23,8 +24,10 @@ def add_vertex(self, vertex): def add_edge(self, tail, head): if tail not in self.vertices: raise ValueError("tail is not a vertex") + if head not in self.vertices: raise ValueError("head is not a vertex") + self.edges.append((tail, head)) self._adj[tail].append(head) @@ -33,14 +36,17 @@ def remove_edge(self, tail, head): self.edges.remove((tail, head)) except KeyError: raise ValueError( - "graph does not contain edge: (%s, %s)" % (tail, head)) + "graph does not contain edge: ({0}, {1})".format(tail, head) + ) self._adj[tail].remove(head) def remove_vertex(self, vertex): try: self.vertices.remove(vertex) except KeyError: - raise ValueError("graph does not contain vertex: %s" % vertex) + raise ValueError( + "graph does not contain vertex: {0}".format(vertex) + ) # delete _adjacencies del self._adj[vertex] @@ -48,8 +54,9 @@ def remove_vertex(self, vertex): adj[:] = [v for v in adj if v != vertex] # delete edges - edges = [e for e in self.edges if e[0] != vertex and e[1] != vertex] - self.edges[:] = edges + self.edges = [ + e for e in self.edges if e[0] != vertex and e[1] != vertex + ] def get_tails(self, head): """ @@ -69,11 +76,12 @@ def bfs(self, start=None): Return a set of all visited vertices """ if not start: - start = list(self.vertices)[0] + start = next(iter(self.vertices)) visited = set() - queue = [start] + queue = deque([start]) + while queue: - vertex = queue.pop(0) + vertex = queue.popleft() if vertex not in visited: visited.add(vertex) queue.extend(set(self._adj.get(vertex, [])) - visited)

_______________________________________________ FreeIPA-devel mailing list -- freeipa-devel@lists.fedorahosted.org To unsubscribe send an email to freeipa-devel-le...@lists.fedorahosted.org