Author: astaric
Date: Tue May 7 09:33:21 2013
New Revision: 1479827
URL: http://svn.apache.org/r1479827
Log:
Use BFS instead of DFS for cycle detections, as it needs less queries. --
towards BEP-0006
Modified:
bloodhound/trunk/bloodhound_dashboard/bhdashboard/model.py
bloodhound/trunk/bloodhound_relations/bhrelations/api.py
bloodhound/trunk/bloodhound_relations/bhrelations/tests/api.py
Modified: bloodhound/trunk/bloodhound_dashboard/bhdashboard/model.py
URL:
http://svn.apache.org/viewvc/bloodhound/trunk/bloodhound_dashboard/bhdashboard/model.py?rev=1479827&r1=1479826&r2=1479827&view=diff
==============================================================================
--- bloodhound/trunk/bloodhound_dashboard/bhdashboard/model.py (original)
+++ bloodhound/trunk/bloodhound_dashboard/bhdashboard/model.py Tue May 7
09:33:21 2013
@@ -265,7 +265,6 @@ class ModelBase(object):
final_sql = sql + wherestr
if limit is not None:
final_sql += ' LIMIT ' + str(int(limit))
- final_sql
if order_by:
final_sql += "\nORDER BY " + ', '.join(order_by)
for row in env.db_query(final_sql, values):
Modified: bloodhound/trunk/bloodhound_relations/bhrelations/api.py
URL:
http://svn.apache.org/viewvc/bloodhound/trunk/bloodhound_relations/bhrelations/api.py?rev=1479827&r1=1479826&r2=1479827&view=diff
==============================================================================
--- bloodhound/trunk/bloodhound_relations/bhrelations/api.py (original)
+++ bloodhound/trunk/bloodhound_relations/bhrelations/api.py Tue May 7
09:33:21 2013
@@ -288,15 +288,20 @@ class RelationsSystem(Component):
return validator
def _validate_no_cycle(self, relation):
- cycle = self._find_cycle(relation.source, relation, [])
- if cycle != None:
+ """If a path exists from relation's destination to its source,
+ adding the relation will create a cycle.
+ """
+ path = self._find_path(relation.destination,
+ relation.source,
+ relation.type)
+ if path:
cycle_str = [self._get_resource_name_from_id(resource_id)
- for resource_id in cycle]
- error = 'Cycle in ''%s'': %s' % (
+ for resource_id in path]
+ error = 'Cycle in ''%s'': %s' % (
self.render_relation_type(relation.type),
' -> '.join(cycle_str))
- error = CycleValidationError(error)
- error.failed_ids = cycle
+ error = CycleValidationError(error)
+ error.failed_ids = path
raise error
def _validate_parent(self, relation):
@@ -311,7 +316,7 @@ class RelationsSystem(Component):
parent_relations = self._select_relations(
source, self.PARENT_RELATION_TYPE)
- if len(parent_relations):
+ if len(parent_relations) > 0:
source_resource_name = self._get_resource_name_from_id(
relation.source)
parent_ids_ins_string = ", ".join(
@@ -327,24 +332,28 @@ class RelationsSystem(Component):
for relation in parent_relations]
raise ex
- def _find_cycle(self, source_to_check, relation, path):
- #todo: optimize this
- destination = relation.destination
- if source_to_check == destination:
- path.append(destination)
- return path
- path.append(destination)
- relations = Relation.select(
- self.env,
- where=dict(source=destination, type=relation.type),
- order_by=["destination"]
- )
- for linked_relation in relations:
- cycle = self._find_cycle(
- source_to_check, linked_relation, copy(path))
- if cycle is not None:
- return cycle
- return None
+ def _find_path(self, source, destination, relation_type):
+ known_nodes = set()
+ new_nodes = set([source])
+ paths = {(source, source): [source]}
+
+ while new_nodes:
+ known_nodes = set.union(known_nodes, new_nodes)
+ with self.env.db_query as db:
+ relations = dict(db("""
+ SELECT source, destination
+ FROM bloodhound_relations
+ WHERE type = '%(relation_type)s'
+ AND source IN (%(new_nodes)s)
+ """ % dict(
+ relation_type=relation_type,
+ new_nodes=', '.join("'%s'" % n for n in new_nodes))
+ ))
+ new_nodes = set(relations.values()) - known_nodes
+ for s, d in relations.items():
+ paths[(source, d)] = paths[(source, s)] + [d]
+ if destination in new_nodes:
+ return paths[(source, destination)]
def render_relation_type(self, end):
return self._labels[end]
Modified: bloodhound/trunk/bloodhound_relations/bhrelations/tests/api.py
URL:
http://svn.apache.org/viewvc/bloodhound/trunk/bloodhound_relations/bhrelations/tests/api.py?rev=1479827&r1=1479826&r2=1479827&view=diff
==============================================================================
--- bloodhound/trunk/bloodhound_relations/bhrelations/tests/api.py (original)
+++ bloodhound/trunk/bloodhound_relations/bhrelations/tests/api.py Tue May 7
09:33:21 2013
@@ -233,10 +233,10 @@ class ApiTestCase(MultiproductTestCase):
try:
relations_system.add(ticket2, ticket1, "dependson")
- self.assertFalse(True, "Should throw an exception")
+ self.fail("Should throw an exception")
except CycleValidationError, ex:
- self.assertEqual("tp1:ticket:1", ex.failed_ids[0])
-
+ self.assertSequenceEqual(
+ ["tp1:ticket:1", "tp1:ticket:2"], ex.failed_ids)
def test_can_add_more_dependsons(self):
#arrange
