URL: https://github.com/freeipa/freeipa/pull/917 Author: tomaskrizek Title: #917: ipapython/graph.py complexity optimization. Action: opened
PR body: """ This PR is a re-open, because I pushed the original into a mirror repo. Original PR: https://github.com/freeipa/freeipa/pull/905 """ To pull the PR as Git branch: git remote add ghfreeipa https://github.com/freeipa/freeipa git fetch ghfreeipa pull/917/head:pr917 git checkout pr917
From 0ee6522143b9d178c683cc16a16ca5a246563d53 Mon Sep 17 00:00:00 2001 From: Aleksei Slaikovskii <aslai...@redhat.com> Date: Fri, 7 Jul 2017 15:50:06 +0200 Subject: [PATCH 1/3] 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. https://pagure.io/freeipa/issue/7051 --- ipapython/graph.py | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/ipapython/graph.py b/ipapython/graph.py index 6b31c915c0..ed0b359f75 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): @@ -69,11 +70,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) From 3e30a661a0667c8b18f4b8bf7bcad8073be03bd0 Mon Sep 17 00:00:00 2001 From: Aleksei Slaikovskii <aslai...@redhat.com> Date: Fri, 7 Jul 2017 15:50:37 +0200 Subject: [PATCH 2/3] ipapython/graph.py String formatting Changed string formatting for Value Errors raise. --- ipapython/graph.py | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/ipapython/graph.py b/ipapython/graph.py index ed0b359f75..c94eb2c886 100644 --- a/ipapython/graph.py +++ b/ipapython/graph.py @@ -24,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) @@ -34,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] From bf422cec00901b5e69e1fd77b7f0ebd6cacabfa3 Mon Sep 17 00:00:00 2001 From: Aleksei Slaikovskii <aslai...@redhat.com> Date: Fri, 7 Jul 2017 15:51:01 +0200 Subject: [PATCH 3/3] ipapython/graph.py redundant variable fix Changed deletion of edges in remove_vertex method because there's no need to store redundant variable in memory. --- ipapython/graph.py | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/ipapython/graph.py b/ipapython/graph.py index c94eb2c886..347c29905e 100644 --- a/ipapython/graph.py +++ b/ipapython/graph.py @@ -54,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): """
_______________________________________________ FreeIPA-devel mailing list -- freeipa-devel@lists.fedorahosted.org To unsubscribe send an email to freeipa-devel-le...@lists.fedorahosted.org
