Commits

Chris Mutel committed c5d0515

0.3 release - complete reorganization so that it installs correctly

  • Participants
  • Parent commits fdd404b

Comments (0)

Files changed (15)

+syntax:glob
+*.pyc
+.DS_Store
+*.tmproj
+dist
+MANIFEST
+include *.txt
+recursive-include django_dag/*.py
+include django_dag/sql/*.sql
+To test: ./manage.py test --settings=dag.tests.settings
 template tags and filters
-pygraph
-pyrecursion
+pygraph

django_dag/sql.py

+import os
+from django.db import connections, transaction
+
+def sql(obj, params=(), using="default", as_dict=False):
+    """
+Execute arbitrary SQL, passed either as a filepath or a string.
+
+Filenames should be relative to BRIGHTWAY_ROOT_PATH.
+
+Outputs a cursor object. It is up to the consumer to fetchone(), fetchall(), etc.
+
+.. rubric:: Inputs
+
+* obj: String. Either a filepath or a string for the SQL to execute.
+* params: Tuple. Parameters for SQL query
+* using: String. Database to use (useful only with multiple databases)
+
+.. rubruc:: Outputs
+
+A python DBABI cursor object.
+    """
+    # TODO: Pass stringIO object as well?
+    try:
+        filepath = os.path.join(os.path.dirname(__file__), obj)
+        query = open(filepath, "r").read()
+    except IOError:
+        # Assume query is a string
+        query = obj
+    cursor = connections[using].cursor()
+    cursor.execute(query, params)
+    if as_dict:
+        return dict_cursor(cursor)
+    else:
+        return cursor
+
+def dict_cursor(cursor):
+    """Turn SQL tuples into dictionaries. Returns generator."""
+    description = [x[0] for x in cursor.description]
+    for row in cursor:
+        yield dict(zip(description, row))
+

django_dag/sql/__init__.py

-import os
-from django.db import connections, transaction
-
-def sql(obj, params=(), using="default", as_dict=False):
-    """
-Execute arbitrary SQL, passed either as a filepath or a string.
-
-Filenames should be relative to BRIGHTWAY_ROOT_PATH.
-
-Outputs a cursor object. It is up to the consumer to fetchone(), fetchall(), etc.
-
-.. rubric:: Inputs
-
-* obj: String. Either a filepath or a string for the SQL to execute.
-* params: Tuple. Parameters for SQL query
-* using: String. Database to use (useful only with multiple databases)
-
-.. rubruc:: Outputs
-
-A python DBABI cursor object.
-    """
-    # TODO: Pass stringIO object as well?
-    try:
-        filepath = os.path.join(os.path.dirname(__file__), obj)
-        query = open(filepath, "r").read()
-    except IOError:
-        # Assume query is a string
-        query = obj
-    cursor = connections[using].cursor()
-    cursor.execute(query, params)
-    if as_dict:
-        return dict_cursor(cursor)
-    else:
-        return cursor
-
-def dict_cursor(cursor):
-    """Turn SQL tuples into dictionaries. Returns generator."""
-    description = [x[0] for x in cursor.description]
-    for row in cursor:
-        yield dict(zip(description, row))
-

django_dag/sql/objects_downwards.sql

-select min(tc.depth) as depth, n.id as node_id, n.content_type_id, n.object_id 
-    from dag_node as n
-    inner join dag_transitive_closure as tc
-    on n.id = tc.node_from_id 
-    where tc.node_to_id = %s
-        and tc.depth <= %s 
-    group by n.id, n.content_type_id, n.object_id, tc.depth
-    order by tc.depth

django_dag/sql/objects_upwards.sql

-select min(tc.depth) as depth, n.id as node_id, n.content_type_id, n.object_id 
-    from dag_node as n
-    inner join dag_transitive_closure as tc
-    on n.id = tc.node_to_id 
-    where tc.node_from_id = %s
-        and tc.depth <= %s 
-    group by n.id, n.content_type_id, n.object_id, tc.depth
-    order by tc.depth

django_dag/sql/transitive_closure.sql

-/*
-
-Schema and triggers for maintaining the transitive closure and acyclicity of
-an incrementally created DAG.
-
-Adapted from http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx
-which references
-
-    Guozhu Dong et al., "Maintaining Transitive Closure of Graphs in SQL"
-    http://www.comp.nus.edu.sg/~wongls/psZ/dlsw-ijit97-16.ps
-
-which in turn references other articles by the same author with proof of
-correctness.
-
-*/
-begin;
-
-create table node (
-    node_id     int,
-    primary key (node_id)
-);
-
-create table edge (
-    node_from   int         references node(node_id)
-                            on update cascade on delete cascade,
-    node_to     int         references node(node_id)
-                            on update cascade on delete cascade,
-    graph_id        int default 42,
-    primary key (node_to, node_from, graph_id),
-    check (node_to != node_from)
-);
-
-create function no_edge_updates() returns trigger as $$
-begin raise exception 'Cannot update edge-table. Delete and insert instead.'; end;
-$$ language plpgsql;
-
-create trigger trig_no_edge_updates before update on edge
-    for each row execute procedure no_edge_updates();
-
-create sequence t_edge_id;
-create table transitive_closure (
-    t_edge_id       int         default nextval('t_edge_id'),
-    graph_id            int ,
-    node_from       int         not null references node(node_id)
-                                         on delete cascade on update cascade,
-    node_to         int         not null references node(node_id)
-                                         on delete cascade on update cascade,
-    -- Auxiliary columns needed to maintain deletions:
-    -- These references justify the surrogate key t_edge_id.
-    -- The lack of foreign keys on them is due to horrible delete-performance.
-    -- It should only be the triggers modifying this table anyway.
-    entry_id        int         not null,
-    direct_id       int         not null,
-    exit_id         int         not null,
-    depth           int         not null default 0,
-    primary key (t_edge_id)
-);
-
-create index idx_trans_from_graph_to on transitive_closure(node_from, graph_id, node_to);
-create index idx_trans_to_graph      on transitive_closure(node_to, graph_id);
-
-create function enforce_acyclicity() returns trigger as
-$$
-begin
-
-if exists(select 1 from transitive_closure where node_to=NEW.node_from and node_from=NEW.node_to and graph_id=NEW.graph_id) then
-    raise exception 'Inserting (%,%) will create a loop.', NEW.node_from, NEW.node_to;
-end if;
-
-return NEW;
-
-end;
-$$ language plpgsql;
-
-create trigger trig_enforce_acyclicity before insert on edge
-    for each row execute procedure enforce_acyclicity();
-
-create function add_implied_edges() returns trigger
-as $$
-declare
-    id int;
-begin
-    id := nextval('t_edge_id');
-    insert into transitive_closure (node_from, node_to, graph_id, entry_id, direct_id, exit_id, t_edge_id) values (new.node_from, new.node_to, new.graph_id, id, id, id, id);
-
-    insert into transitive_closure (direct_id, exit_id, entry_id, node_from, node_to, graph_id, depth)
-
-        -- Incoming edges.
-        select id, id, t_edge_id, node_from, new.node_to, new.graph_id, depth + 1
-            from transitive_closure
-            where node_to = new.node_from
-                  and graph_id=new.graph_id
-
-        union
-
-        -- Outgoing edges.
-        select id, t_edge_id, id, new.node_from, node_to, new.graph_id, depth + 1
-            from transitive_closure
-            where node_from = new.node_to
-                  and graph_id=new.graph_id
-
-        union
-
-        -- Incoming to outgoing.
-        select a.t_edge_id, id, b.t_edge_id, a.node_from, b.node_to, new.graph_id, a.depth + b.depth + 1
-            from transitive_closure a
-                 cross join transitive_closure b
-            where a.node_to = new.node_from and b.node_from = new.node_to
-                  and a.graph_id=new.graph_id and b.graph_id=new.graph_id;
-
-    return null;
-end;
-$$ language plpgsql;
-
-create trigger trig_add_implied_edges after insert on edge
-    for each row execute procedure add_implied_edges();
-
-create function remove_implied_edges() returns trigger
-as $$
-begin
-
-    create temporary table purge_list as
-        -- The direct edge.
-        select direct_id as t_edge_id
-        from transitive_closure
-        where node_from = old.node_from
-              and node_to = old.node_to
-              and graph_id = old.graph_id;
-
-    while true
-    loop
-        insert into purge_list
-        -- Edges dependant of those in the purge list.
-        select t_edge_id
-            from transitive_closure
-            where
-                depth > 0
-                and t_edge_id not in ( select t_edge_id from purge_list )
-                and (
-                    entry_id in ( select t_edge_id from purge_list )
-                    or exit_id in ( select t_edge_id from purge_list )
-                );
-        if not found then
-            exit;
-        end if;
-    end loop;
-
-    delete from transitive_closure
-        where t_edge_id in (
-            select t_edge_id
-            from purge_list
-        );
-
-    drop table purge_list;
-    return null;
-end;
-$$ language plpgsql;
-
-create trigger trig_remove_implied_edges after delete on edge
-    for each row execute procedure remove_implied_edges();
-
--- (1) -> (2) -> (3) -> (4)  (5)
---  \--------------------^
-
-insert into node values (1), (2), (3), (4), (5);
-insert into edge values (1,2), (2,3), (3,4), (1,4);
-
-select node_from, node_to, graph_id, depth
-    from transitive_closure
-    order by node_to, node_from, depth;
-
-delete from edge where node_from=2 and node_to=3;
-delete from edge where node_from=1 and node_to=2;
-insert into edge values (5,1);
-
--- (1) (2) (3)->(4) (5)
---  \------------^   /
---  ^---------------/
-
-select node_from, node_to, graph_id, depth
-    from transitive_closure
-    order by node_to, node_from, depth;
-
-delete from node where node_id=1;
-
--- (2) (3)->(4) (5)
-
-select node_from, node_to, graph_id, depth
-    from transitive_closure
-    order by node_to, node_from, depth;
-
-rollback;

django_dag/tests/README

-To test: ./manage.py test --settings=dag.tests.settings

django_dag/utils.py

     DuplicateEdgeError
 from sql import sql
 
+UPWARDS = """select min(tc.depth) as depth, n.id as node_id, n.content_type_id, n.object_id 
+    from dag_node as n
+    inner join dag_transitive_closure as tc
+    on n.id = tc.node_to_id 
+    where tc.node_from_id = %s
+        and tc.depth <= %s 
+    group by n.id, n.content_type_id, n.object_id, tc.depth
+    order by tc.depth"""
+
+DOWNWARDS = """select min(tc.depth) as depth, n.id as node_id, n.content_type_id, n.object_id 
+        from dag_node as n
+        inner join dag_transitive_closure as tc
+        on n.id = tc.node_from_id 
+        where tc.node_to_id = %s
+            and tc.depth <= %s 
+        group by n.id, n.content_type_id, n.object_id, tc.depth
+        order by tc.depth"""
+
 def flatten(x):
     """Flattened a set of iterables into a single list.
     
     if not node:
         # Can be called by get_children, etc., when node isn't created.
         return ()
-    query = "objects_downwards.sql" if downwards else "objects_upwards.sql"
+    query = DOWNWARDS if downwards else UPWARDS
     # Realize generator with list comprehension
     tc_query = [obj for obj in sql(query, (node.id, max_depth), using=using, 
         as_dict=True)]
 
 setup(
     name='django_dag',
-    version='0.2',
+    version='0.3',
     author='Chris Mutel',
     author_email='cmutel@gmail.com',
     url='',
-    packages=['django_dag',],
+    packages=['django_dag', 'django_dag.management', 'django_dag.tests'],
     license='LICENSE.txt',
     long_description=open('README.txt').read(),
 )

sql/objects_downwards.sql

+select min(tc.depth) as depth, n.id as node_id, n.content_type_id, n.object_id 
+    from dag_node as n
+    inner join dag_transitive_closure as tc
+    on n.id = tc.node_from_id 
+    where tc.node_to_id = %s
+        and tc.depth <= %s 
+    group by n.id, n.content_type_id, n.object_id, tc.depth
+    order by tc.depth

sql/objects_upwards.sql

+select min(tc.depth) as depth, n.id as node_id, n.content_type_id, n.object_id 
+    from dag_node as n
+    inner join dag_transitive_closure as tc
+    on n.id = tc.node_to_id 
+    where tc.node_from_id = %s
+        and tc.depth <= %s 
+    group by n.id, n.content_type_id, n.object_id, tc.depth
+    order by tc.depth

sql/transitive_closure.sql

+/*
+
+Schema and triggers for maintaining the transitive closure and acyclicity of
+an incrementally created DAG.
+
+Adapted from http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx
+which references
+
+    Guozhu Dong et al., "Maintaining Transitive Closure of Graphs in SQL"
+    http://www.comp.nus.edu.sg/~wongls/psZ/dlsw-ijit97-16.ps
+
+which in turn references other articles by the same author with proof of
+correctness.
+
+*/
+begin;
+
+create table node (
+    node_id     int,
+    primary key (node_id)
+);
+
+create table edge (
+    node_from   int         references node(node_id)
+                            on update cascade on delete cascade,
+    node_to     int         references node(node_id)
+                            on update cascade on delete cascade,
+    graph_id        int default 42,
+    primary key (node_to, node_from, graph_id),
+    check (node_to != node_from)
+);
+
+create function no_edge_updates() returns trigger as $$
+begin raise exception 'Cannot update edge-table. Delete and insert instead.'; end;
+$$ language plpgsql;
+
+create trigger trig_no_edge_updates before update on edge
+    for each row execute procedure no_edge_updates();
+
+create sequence t_edge_id;
+create table transitive_closure (
+    t_edge_id       int         default nextval('t_edge_id'),
+    graph_id            int ,
+    node_from       int         not null references node(node_id)
+                                         on delete cascade on update cascade,
+    node_to         int         not null references node(node_id)
+                                         on delete cascade on update cascade,
+    -- Auxiliary columns needed to maintain deletions:
+    -- These references justify the surrogate key t_edge_id.
+    -- The lack of foreign keys on them is due to horrible delete-performance.
+    -- It should only be the triggers modifying this table anyway.
+    entry_id        int         not null,
+    direct_id       int         not null,
+    exit_id         int         not null,
+    depth           int         not null default 0,
+    primary key (t_edge_id)
+);
+
+create index idx_trans_from_graph_to on transitive_closure(node_from, graph_id, node_to);
+create index idx_trans_to_graph      on transitive_closure(node_to, graph_id);
+
+create function enforce_acyclicity() returns trigger as
+$$
+begin
+
+if exists(select 1 from transitive_closure where node_to=NEW.node_from and node_from=NEW.node_to and graph_id=NEW.graph_id) then
+    raise exception 'Inserting (%,%) will create a loop.', NEW.node_from, NEW.node_to;
+end if;
+
+return NEW;
+
+end;
+$$ language plpgsql;
+
+create trigger trig_enforce_acyclicity before insert on edge
+    for each row execute procedure enforce_acyclicity();
+
+create function add_implied_edges() returns trigger
+as $$
+declare
+    id int;
+begin
+    id := nextval('t_edge_id');
+    insert into transitive_closure (node_from, node_to, graph_id, entry_id, direct_id, exit_id, t_edge_id) values (new.node_from, new.node_to, new.graph_id, id, id, id, id);
+
+    insert into transitive_closure (direct_id, exit_id, entry_id, node_from, node_to, graph_id, depth)
+
+        -- Incoming edges.
+        select id, id, t_edge_id, node_from, new.node_to, new.graph_id, depth + 1
+            from transitive_closure
+            where node_to = new.node_from
+                  and graph_id=new.graph_id
+
+        union
+
+        -- Outgoing edges.
+        select id, t_edge_id, id, new.node_from, node_to, new.graph_id, depth + 1
+            from transitive_closure
+            where node_from = new.node_to
+                  and graph_id=new.graph_id
+
+        union
+
+        -- Incoming to outgoing.
+        select a.t_edge_id, id, b.t_edge_id, a.node_from, b.node_to, new.graph_id, a.depth + b.depth + 1
+            from transitive_closure a
+                 cross join transitive_closure b
+            where a.node_to = new.node_from and b.node_from = new.node_to
+                  and a.graph_id=new.graph_id and b.graph_id=new.graph_id;
+
+    return null;
+end;
+$$ language plpgsql;
+
+create trigger trig_add_implied_edges after insert on edge
+    for each row execute procedure add_implied_edges();
+
+create function remove_implied_edges() returns trigger
+as $$
+begin
+
+    create temporary table purge_list as
+        -- The direct edge.
+        select direct_id as t_edge_id
+        from transitive_closure
+        where node_from = old.node_from
+              and node_to = old.node_to
+              and graph_id = old.graph_id;
+
+    while true
+    loop
+        insert into purge_list
+        -- Edges dependant of those in the purge list.
+        select t_edge_id
+            from transitive_closure
+            where
+                depth > 0
+                and t_edge_id not in ( select t_edge_id from purge_list )
+                and (
+                    entry_id in ( select t_edge_id from purge_list )
+                    or exit_id in ( select t_edge_id from purge_list )
+                );
+        if not found then
+            exit;
+        end if;
+    end loop;
+
+    delete from transitive_closure
+        where t_edge_id in (
+            select t_edge_id
+            from purge_list
+        );
+
+    drop table purge_list;
+    return null;
+end;
+$$ language plpgsql;
+
+create trigger trig_remove_implied_edges after delete on edge
+    for each row execute procedure remove_implied_edges();
+
+-- (1) -> (2) -> (3) -> (4)  (5)
+--  \--------------------^
+
+insert into node values (1), (2), (3), (4), (5);
+insert into edge values (1,2), (2,3), (3,4), (1,4);
+
+select node_from, node_to, graph_id, depth
+    from transitive_closure
+    order by node_to, node_from, depth;
+
+delete from edge where node_from=2 and node_to=3;
+delete from edge where node_from=1 and node_to=2;
+insert into edge values (5,1);
+
+-- (1) (2) (3)->(4) (5)
+--  \------------^   /
+--  ^---------------/
+
+select node_from, node_to, graph_id, depth
+    from transitive_closure
+    order by node_to, node_from, depth;
+
+delete from node where node_id=1;
+
+-- (2) (3)->(4) (5)
+
+select node_from, node_to, graph_id, depth
+    from transitive_closure
+    order by node_to, node_from, depth;
+
+rollback;