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

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

Reply via email to