From: Steven McDonald Date: Sun, 25 Sep 2011 11:35:37 +0000 (+1000) Subject: initialise repo X-Git-Url: http://git.steven-mcdonald.id.au/?p=debian%2Fdigraphtools.git;a=commitdiff_plain;h=821698544a5b63506c023bee6b1a9a3b43671ae6 initialise repo --- 821698544a5b63506c023bee6b1a9a3b43671ae6 diff --git a/CHANGES.txt b/CHANGES.txt new file mode 100644 index 0000000..cb277e7 --- /dev/null +++ b/CHANGES.txt @@ -0,0 +1,5 @@ +v0.2.1, Wed Sep 07 15:15:14 EST 2011 -- Fix naive bug in bracket matching. Oops. + +v0.2.0, Mon Aug 22 01:04:14 EST 2011 -- Build predicates from strings. + +v0.1.0, Sun Aug 14 22:32:03 EST 2011 -- Initial release. diff --git a/LICENSE.txt b/LICENSE.txt new file mode 100644 index 0000000..00e7080 --- /dev/null +++ b/LICENSE.txt @@ -0,0 +1,25 @@ +Copyright (c) 2011, David Basden +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + * Neither the name of the copyright holder nor the names of the contributors + may be used to endorse or promote products derived from this software + without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY +DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES +(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND +ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/PKG-INFO b/PKG-INFO new file mode 100644 index 0000000..483a04b --- /dev/null +++ b/PKG-INFO @@ -0,0 +1,97 @@ +Metadata-Version: 1.0 +Name: digraphtools +Version: 0.2.1 +Summary: Some tools for working with digraphs, partial orders and topological sorting with Python +Home-page: https://github.com/dbasden/python-digraphtools +Author: David Basden +Author-email: davidb-python@rcpt.to +License: UNKNOWN +Description: + ============ + digraphtools + ============ + + Some tools for working with directed acyclic graphs, partial orders and + topological sorting with Python + + digraphtools was written as a lightweight way of using DAGs and partial + ordering to represent, sort and traverse dependency trees in a lightweight + way. + + The code is hosted on github at https://github.com/dbasden/python-digraphtools + + Graph Representation + ==================== + + Graphs + ------ + + A graph is represented as a dict which maps a node to a list + nodes connected via the outgoing edges of that node. + + e.g. + + graph = { 1: [2,3], + 2: [3], + 3: [] } + + is a DAG represented by the edges (1,2) (1,3) (2,3) + where the edge 2tuple is in the form of (from,to) + + There are helper methods in deptools to generate graphs from a + list of edges, and vice versa + + Binary relations + ---------------- + + If a DAG represents dependencies, e.g. the edge (1,2) is taken + to mean "1 depends on 2", this is backwards from a binary relation. + (1,2) would be the relation 2P1 + + + Topological Sorting + =================== + + There are two ways of generating linear extensions / topological sorts of + dependencies (i.e. orders items must be processed in to satisfy dependency + requirements): + + deptools.dfs_topsort_traversal + ------------------------------ + + deptools.dfs_topsort_traversal will take a graph and iterate over a + single valid topologicaly sorted order + + deptools.topsort.vr_topsort + --------------------------- + + deptools.topsort.vr_topsort will generate all valid linear extensions / + topological orderings given an initial 'seed' linear extension (such as + the one generated by deptools.dfs_topsort_traversal). + + The method does not take the graph format as used by deptools as input, + but it does have a helper method to generate it's input matrix from a + partial order set (which can be generated from a graph using helpers in + deptools). + + See the examples in topsort.py and test/test_topsort.py for how to do this. + + + Authors + ======= + + digraphtools was initially written by David Basden + + + Thanks + ====== + + Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm + in topsort.py + +Platform: any +Classifier: Intended Audience :: Developers +Classifier: Development Status :: 3 - Alpha +Classifier: License :: OSI Approved :: BSD License +Classifier: Operating System :: OS Independent +Classifier: Programming Language :: Python diff --git a/README.txt b/README.txt new file mode 100644 index 0000000..c68d207 --- /dev/null +++ b/README.txt @@ -0,0 +1,82 @@ + +============ +digraphtools +============ + +Some tools for working with directed acyclic graphs, partial orders and +topological sorting with Python + +digraphtools was written as a lightweight way of using DAGs and partial +ordering to represent, sort and traverse dependency trees in a lightweight +way. + +The code is hosted on github at https://github.com/dbasden/python-digraphtools + +Graph Representation +==================== + +Graphs +------ + +A graph is represented as a dict which maps a node to a list +nodes connected via the outgoing edges of that node. + +e.g. + + graph = { 1: [2,3], + 2: [3], + 3: [] } + +is a DAG represented by the edges (1,2) (1,3) (2,3) +where the edge 2tuple is in the form of (from,to) + +There are helper methods in deptools to generate graphs from a +list of edges, and vice versa + +Binary relations +---------------- + +If a DAG represents dependencies, e.g. the edge (1,2) is taken +to mean "1 depends on 2", this is backwards from a binary relation. +(1,2) would be the relation 2P1 + + +Topological Sorting +=================== + +There are two ways of generating linear extensions / topological sorts of +dependencies (i.e. orders items must be processed in to satisfy dependency +requirements): + +deptools.dfs_topsort_traversal +------------------------------ + +deptools.dfs_topsort_traversal will take a graph and iterate over a +single valid topologicaly sorted order + +deptools.topsort.vr_topsort +--------------------------- + +deptools.topsort.vr_topsort will generate all valid linear extensions / +topological orderings given an initial 'seed' linear extension (such as +the one generated by deptools.dfs_topsort_traversal). + +The method does not take the graph format as used by deptools as input, +but it does have a helper method to generate it's input matrix from a +partial order set (which can be generated from a graph using helpers in +deptools). + +See the examples in topsort.py and test/test_topsort.py for how to do this. + + +Authors +======= + +digraphtools was initially written by David Basden + + +Thanks +====== + +Thanks to Yaakov L. Varol and Doron Rotem for the design of the algorithm +in topsort.py diff --git a/digraphtools/__init__.py b/digraphtools/__init__.py new file mode 100644 index 0000000..4868bc4 --- /dev/null +++ b/digraphtools/__init__.py @@ -0,0 +1 @@ +from digraphtools import * diff --git a/digraphtools/digraphtools.py b/digraphtools/digraphtools.py new file mode 100644 index 0000000..e5d96ba --- /dev/null +++ b/digraphtools/digraphtools.py @@ -0,0 +1,94 @@ +#! /usr/bin/env python + +'''a collection of tools for working with directed acyclic graphs + +A graph is represented as a dict which maps a node to a list +nodes connected via the outgoing edges of that node. + +e.g. + + graph = { 1: [2,3], + 2: [3], + 3: [] } + +is a DAG represented by the edges (1,2) (1,3) (2,3) +where the edge 2tuple is in the form of (from,to) + +Note: If a DAG represents dependencies, e.g. the edge (1,2) is taken + to mean "1 depends on 2", this is backwards from a binary relation. + (1,2) would be the relation 2P1 +''' +from collections import defaultdict,deque + +def graph_from_edges(edges): + '''return a graph from a set of edges + edges are a 2tuple in the form of (from_node, to_node) + ''' + graph = defaultdict(set) + for a,b in edges: + graph[a].add(b) + graph[b] + return dict((a,list(b)) for a,b in graph.items()) + +def copy_graph(graph): + '''return a copy of a graph''' + return dict((a,list(b)) for a,b in graph.items()) + +def iter_edges(graph): + '''return an iterator over every edge in a graph in the form (from,to)''' + return ((a,b) for a in graph.iterkeys() for b in graph[a]) + +def iter_partial_order(graph): + return ((a,b) for b,a in iter_edges(graph)) + +def from_partial_order(edges): return [(a,b) for (b,a) in edges] +to_partial_order = from_partial_order + +class OrderViolationException(Exception): pass + +def verify_partial_order(partial_order, items): + '''verify that the order of items supplied satisfies the dependency graph + raises OrderViolationException unless a= itempos[b]: + raise OrderViolationException("item '%s' is in the order before it's dependency '%s'" %( repr(b),repr(a)),items) + +def postorder_traversal(graph, root): + '''traverse a graph post-order and yield a list of nodes''' + for n in graph[root]: + for traversed in postorder_traversal(graph,n): + yield traversed + yield root + +def dfs_topsort_traversal(graph, root): + '''traverse a graph postorder while not traversing already seen nodes''' + seen = set() + for n in postorder_traversal(graph, root): + if n not in seen: + yield n + seen.add(n) + +def dfs_traverse_iter_path(graph, root, path=None): + '''depth first traversal of graph generating every path seen''' + if path == None: path = [] + if root in path: return + path.append(root) + yield path + for n in graph[root]: + for traversed in dfs_traverse_iter_path(graph, n, path): + yield traversed + path.pop() + +def dfs_iter_edges(graph, root): + '''traverse a graph depth-first and yield edges as they are traversed''' + for n in graph[root]: + yield root,n + for edge in dfs_iter_edges(graph,n): + yield edge + +def get_connected_subgraph(graph, root): + '''return the connected subgraph visible from supplied root node''' + return graph_from_edges( dfs_iter_edges(graph,root) ) diff --git a/digraphtools/predicate.py b/digraphtools/predicate.py new file mode 100644 index 0000000..1aea41e --- /dev/null +++ b/digraphtools/predicate.py @@ -0,0 +1,341 @@ +#! /usr/bin/env python + +'''predicates that can be chained together with boolean expressions before evaluation + +e.g. + a = predicate(lambda s: 'a' in s) + b = predicate(lambda s: 'b' in s) + c = predicate(lambda s: 'c' in s) + + anyof = a | b | c + allof = a & b & c + not_anyof = anyof != True + assert anyof('--a--') + assert allof('-abc-') + assert not_anyof('12345') + +Also, generate predicates such as above from strings + + pf = PredicateContainsFactory() + anyof2 = pf.predicate_from_string('a | b | c') + pallof2 = pf.predicate_from_string('a & b & c') + not_anyof2 = pf.predicate_from_string('!(a & b & c)') + assert anyof2('--a--') + assert allof2('-abc-') + assert not_anyof2('12345') + +These can be very useful for filtering of dependency graphs +''' + +import operator +import re + +def defer(origfunc,*argfs,**argfd): + '''defer execution of the arguments of a function + given origfunc return a function such that the code + f = defer(origfunc, arga, key=argb) + f(*newargs, **newargd) + is equivalent to: + origfunc(arga(*newargs,**newargd), key=argb(*newargs,**newargd)) + ''' + def wrapper(*args, **argd): + newargs = [argf(*args, **argd) for argf in argfs] + newargd = dict((k,argf(*args, **argd)) for k,argf in argfd.items()) + return origfunc(*newargs, **newargd) + wrapper.origfunc = origfunc + wrapper.argfs = argfs + wrapper.argfd = argfd + wrapper.__repr__ = lambda s: "defer <%s>( *(%s) **(%s)) " % (repr(origfunc),repr(argfs),repr(argfd)) + return wrapper + +def always(val): + '''returns a function that always returns val regardless of inputs''' + def alwaysf(*args, **argd): return val + alwaysf.val = val + return alwaysf + +class predicate(object): + '''chainable predicates + e.g. + a = predicate(lambda s: 'a' in s) + b = predicate(lambda s: 'b' in s) + c = predicate(lambda s: 'c' in s) + + anyof = a | b | c + allof = a & b & c + not_anyof = anyof != True + assert anyof('--a--') + assert allof('-abc-') + assert not_anyof('12345') + ''' + + def __init__(self, func): + self.func = func + def __call__(self, arg): + return self.func(arg) + def __and__(self,other): + return self.__defer_infix__(other,operator.__and__) + def __or__(self,other): + return self.__defer_infix__(other,operator.__or__) + def __ne__(self,other): + return self.__defer_infix__(other,operator.__ne__) + def __defer_infix__(self,other,op): + if isinstance(other, bool): + other = always(other) + elif not isinstance(other, predicate): + return NotImplemented + return self.__class__(defer(op, self, other)) + def __repr__(self): + return 'pred( '+repr(self.func)+' )' + +class notp(predicate): + '''exactly the same as a predicate but inverts it's __call__ output''' + def __call__(self, *args, **argd): + return not predicate.__call__(self, *args, **argd) + + + +def partition_list(items, partition): + '''works like str.partition but for lists + e.g. partition(['aa','bb','cd','ee'],'cd') == ['aa','bb'],'cd',['ee'] + partition(['aa','bb','cd','ee'],'ff') == ['aa','bb','cd','ee'],None,[] + ''' + for i,obj in enumerate(items): + if obj == partition: + return items[:i],obj,items[i+1:] + return items,None,[] + +class ParseSyntaxError(Exception): pass +class LexParse(object): + '''very simple lexer/parser''' + class _leaf(object): + def __init__(self, data): self.data = data + def __repr__(self): return '_leaf(%s)' %(repr(self.data)) + + valid_tokens = ['(',')','!','&','|'] + + def _match_bracket(self, tokens, i, bopen='(',bclose=')'): + '''find the closing bracket that matches an open bracket + return None if there is no matching bracket + otherwise the index into tokens of the close bracket that matches the opening bracket at position i + ''' + assert i < len(tokens) + assert tokens[i] == bopen + depth = 0 + for i in xrange(i,len(tokens)): + tok = tokens[i] + if tok == bopen: + depth += 1 + elif tok == bclose: + depth -= 1 + if depth < 0: return None + if depth == 0: return i + return None + + def lex(self, s): + '''returns a list of tokens from a string + tokens returned are anything inside self.valid_tokens or + any other string not containing tokens, stripped + of leading and trailing whitespace + ''' + s = s.strip() + if s == '': return [] + for tok in self.valid_tokens: + l,t,r = s.partition(tok) + if t==tok: return self.lex(l)+[tok]+self.lex(r) + return [self._leaf(s)] + + def parse(self, tokens): + '''parse a list of tokens in order of predicence and return the output''' + if len(tokens) == 0: + raise ParseSyntaxError('Cannot parse empty subexpression') + # Brackets + l,part,r = partition_list(tokens, '(') + if part != None: + if ')' in l: raise ParseSyntaxError('unmatched ) near',tokens) + r.insert(0,'(') + rindex = self._match_bracket(r, 0) + if rindex is None: raise ParseSyntaxError('unmatched ( near',tokens) + assert r[rindex] == ')' + inner = r[1:rindex] + r = r[rindex+1:] + inner = self.brackets(self.parse(inner)) + return self.parse(l+[inner]+r) + + # unary not + if tokens[0] == '!': + if len(tokens) < 2: raise ParseSyntaxError('syntax error near',tokens) + # this only works without other unary operators + if tokens[1] in self.valid_tokens: raise ParseSyntaxError('syntax error near', tokens) + argument = self.parse([ tokens[1] ]) + inv = self.notx(argument) + return self.parse([inv]+tokens[2:]) + + # and + l,part,r = partition_list(tokens, '&') + if part != None: + if not len(l) or not len(r): + raise ParseSyntaxError('syntax error near', tokens) + l,r = self.parse(l), self.parse(r) + return self.andx(l,r) + + # or + l,part,r = partition_list(tokens, '|') + if part != None: + if not len(l) or not len(r): + raise ParseSyntaxError('syntax error near', tokens) + l,r = self.parse(l), self.parse(r) + return self.orx(l,r) + + if len(tokens) == 1: + if isinstance(tokens[0], self._leaf): + return self.data(tokens[0].data) # base case + elif tokens[0] in self.valid_tokens: + raise ParseSyntaxError('syntax error near',tokens) + return tokens[0] # Already parsed + + # Nothing else is sane + print repr(tokens) + raise ParseSyntaxError('syntax error near', tokens) + + def brackets(self, expr): + '''You almost never want to override this''' + return expr + + def notx(self, expr): pass + def andx(self, expr_l, expr_r): pass + def orx(self, expr_l, expr_r): pass + def data(self, data): pass + +class BoolParse(LexParse): + '''example parser implementation + bp = BoolParse() + assert False or (False and not (True or False)) == False + inp = 'False | (False & ! (True | False))' + assert bp.parse(bp.lex(inp)) is False + ''' + notx = lambda s,expr: not expr + andx = lambda s,l,r: l and r + orx = lambda s,l,r: l or r + def data(self,data): + return not(data.lower() == 'false' or data == '0') + + +class PredicateContainsFactory(LexParse): + '''create predicates that act on the contents of a container passed to them''' + def predicate_from_string(self, definition): + tokens = self.lex(definition) + return self.parse(tokens) + def notx(self, pred): + return notp(pred) + def andx(self, pred_l, pred_r): + return pred_l & pred_r + def orx(self, pred_l, pred_r): + return pred_l | pred_r + def data(self, data): + return predicate(lambda container: data in container) + +if __name__ == "__main__": + def defer_sample(): + def a(arga, moo=None, argb=None): + return arga+argb + def b(arga, moo=None, argb=None): + return arga^argb + def c(arga, moo=None, argb=None): + return arga,argb + ooer = defer(c, a,argb=b) + result = ooer(1234,argb=4312) + assert result == (5546, 5130) + + def predicate_sample(): + a = predicate(lambda s: 'a' in s) + b = predicate(lambda s: 'b' in s) + c = predicate(lambda s: 'c' in s) + d = predicate(lambda s: 'd' in s) + + anyof = a | b | c + allof = a & b & c + + not_anyof = anyof != True + not_allof = allof != True + + + assert anyof('asdf') + assert allof('abc') + assert not anyof('1234') + assert not allof('ab') + assert not_anyof('1234') + assert not_allof('1234') + + nottest = a & b & notp( c | d ) + assert nottest('ab') + assert not nottest('abc') + assert not nottest('b') + assert not nottest('d') + assert not nottest('bd') + assert not nottest('abd') + + e = predicate(lambda n: n%2==0) + t = predicate(lambda n: n%3==0) + eset = set(filter(e, range(1000))) + tset = set(filter(t, range(1000))) + eutset = set(filter(e|t, range(1000))) + eitset = set(filter(e&t, range(1000))) + assert eutset == eset.union(tset) + assert eitset == eset.intersection(tset) + + def parser_internal_test(): + lp = LexParse() + #lp._match_bracket(self, tokens, i, bopen='(',bclose=')'): + assert lp._match_bracket('()',0) == 1 + assert lp._match_bracket('(',0) == None + assert lp._match_bracket(')))))()))))',5) == 6 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',0) == 29 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',2) == 3 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',12) == 25 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',23) == 24 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',23) == 24 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',26) == 27 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',9) == 28 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',10) == 11 + assert lp._match_bracket('((()(()))(()((()(()()))())()))',16) == 21 + + def parser_sample(): + bp = BoolParse() + assert False or (False and not (True or False)) == False + inp = 'False | (False & ! (True | False))' + assert bp.parse(bp.lex(inp)) is False + assert bp.parse(bp.lex('true & !false')) + + def predicate_factory_sample(): + pf = PredicateContainsFactory() + pred = pf.predicate_from_string('fish & !cow') + assert pred(['fish', 'bat', 'pidgeon']) + assert not pred( ['fish', 'cow', 'bat'] ) + assert not pred( [] ) + assert not pred( ['cow'] ) + assert not pred( ['bat','pig'] ) + + a = predicate(lambda s: 'a' in s) + b = predicate(lambda s: 'b' in s) + c = predicate(lambda s: 'c' in s) + anyof2 = pf.predicate_from_string('a | b | c') + allof2 = pf.predicate_from_string('a & b & c') + not_anyof2 = pf.predicate_from_string('!(a & b & c)') + assert anyof2('--a--') + assert allof2('-abc-') + assert not_anyof2('12345') + + pred = pf.predicate_from_string('( a | b | c ) & ( c | e | d )') + assert not pred('b') + assert pred('c') + assert pred('cd') + assert pred('acd') + assert not pred('ab') + assert not pred('a') + + parser_internal_test() + defer_sample() + predicate_sample() + parser_sample() + predicate_factory_sample() diff --git a/digraphtools/test/__init__.py b/digraphtools/test/__init__.py new file mode 100644 index 0000000..e69de29 diff --git a/digraphtools/test/test_digraphtools.py b/digraphtools/test/test_digraphtools.py new file mode 100755 index 0000000..decae2c --- /dev/null +++ b/digraphtools/test/test_digraphtools.py @@ -0,0 +1,58 @@ +#! /usr/bin/env python + +'''unit tests for digraphtools''' + +import unittest2 as unittest +import digraphtools + +class DigraphTests(unittest.TestCase): + def test_graph_from_edges(self): + g = digraphtools.graph_from_edges([(1,2),(1,3),(2,3)]) + self.assertEqual(set(g[1]),set([2,3])) + self.assertEqual(set(g[2]),set([3])) + self.assertEqual(set(g[3]),set()) + def test_verify_partial_order(self): + g = digraphtools.graph_from_edges([(1,2),(1,3),(2,3)]) + # Will raise an exception if incorrect + digraphtools.verify_partial_order(digraphtools.iter_partial_order(g), [3,2,1]) + self.assertRaises(digraphtools.OrderViolationException,digraphtools.verify_partial_order, digraphtools.iter_partial_order(g), [3,1,2]) + def test_iter_edges(self): + edges = set([(1,2),(1,3),(2,3)]) + g = digraphtools.graph_from_edges(edges) + gedges = set(digraphtools.iter_edges(g)) + self.assertEqual(edges,gedges) + def test_copy_graph(self): + edges = set([(1,2),(1,3),(2,3)]) + g = digraphtools.graph_from_edges(edges) + gg = digraphtools.copy_graph(g) + self.assertEqual(g,gg) + gedges = set(digraphtools.iter_edges(g)) + ggedges = set(digraphtools.iter_edges(gg)) + self.assertEqual(gedges,ggedges) + gg[2].remove(3) + self.assertNotEqual(g,gg) + gedges = set(digraphtools.iter_edges(g)) + ggedges = set(digraphtools.iter_edges(gg)) + self.assertNotEqual(gedges,ggedges) + def test_postorder_traversal(self): + edges = set([(1,2),(1,3),(2,3)]) + g = digraphtools.graph_from_edges(edges) + po = list(digraphtools.postorder_traversal(g,1)) + self.assertEqual([3,2,3,1],po) + def test_dfs_topsort_traversal(self): + edges = set([(1,2),(1,3),(2,3)]) + g = digraphtools.graph_from_edges(edges) + po = list(digraphtools.dfs_topsort_traversal(g,1)) + self.assertEqual([3,2,1],po) + def test_dfs_iter_edges(self): + g = digraphtools.graph_from_edges([(1,2),(1,3),(2,3)]) + edgeiter = digraphtools.dfs_iter_edges(g,1) + self.assertEqual([(1,2),(2,3),(1,3)],list(edgeiter)) + def test_get_connected_subgraph(self): + g = digraphtools.graph_from_edges([(1,2),(1,3),(2,3)]) + self.assertEqual(g, digraphtools.get_connected_subgraph(g,1)) + sg = digraphtools.graph_from_edges([(2,3)]) + self.assertEqual(sg, digraphtools.get_connected_subgraph(g,2)) + +if __name__ == '__main__': + unittest.main() diff --git a/digraphtools/test/test_topsort.py b/digraphtools/test/test_topsort.py new file mode 100755 index 0000000..f2e0a9a --- /dev/null +++ b/digraphtools/test/test_topsort.py @@ -0,0 +1,19 @@ +#! /usr/bin/env python + +'''unit tests for digraphtools''' + +import unittest2 as unittest +import digraphtools +import digraphtools.topsort as topsort + +class TopsortTests(unittest.TestCase): + def test_vr_topsort(self): + n = 5 + partial_order = [(1,2), (2,3), (1,5)] + g = digraphtools.graph_from_edges(digraphtools.from_partial_order(partial_order)) + grid = topsort.partial_order_to_grid(partial_order,n) + for le in topsort.vr_topsort(n,grid): + digraphtools.verify_partial_order(digraphtools.iter_partial_order(g), le) + +if __name__ == '__main__': + unittest.main() diff --git a/digraphtools/topsort.py b/digraphtools/topsort.py new file mode 100644 index 0000000..a059378 --- /dev/null +++ b/digraphtools/topsort.py @@ -0,0 +1,63 @@ +#! /usr/bin/env python + +def partial_order_to_grid(poset, n): + '''poset is given in 2tuples of indexes into a list containing a linear extension + as the indicies are into a list containing a valid topological sort, + i must be < j for every (i,j) in the poset''' + grid = [[False for j in xrange(n+1)]+[True] for i in xrange(n+2)] + for i,j in poset: + assert i