util Package

util Package

Utility functions used systemwide.

class galaxy.util.Params(params, sanitize=True)

Bases: object

Stores and ‘sanitizes’ parameters. Alphanumeric characters and the non-alphanumeric ones that are deemed safe are let to pass through (see L{valid_chars}). Some non-safe characters are escaped to safe forms for example C{>} becomes C{__lt__} (see L{mapped_chars}). All other characters are replaced with C{X}.

Operates on string or list values only (HTTP parameters).

>>> values = { 'status':'on', 'symbols':[  'alpha', '<>', '$rm&#!' ]  }
>>> par = Params(values)
>>> par.status
'on'
>>> par.value == None      # missing attributes return None
True
>>> par.get('price', 0)
0
>>> par.symbols            # replaces unknown symbols with X
['alpha', '__lt____gt__', 'XrmX__pd__!']
>>> par.flatten()          # flattening to a list
[('status', 'on'), ('symbols', 'alpha'), ('symbols', '__lt____gt__'), ('symbols', 'XrmX__pd__!')]

NEVER_SANITIZE = ['file_data', 'url_paste', 'URL', 'filesystem_paths']

flatten()

Creates a tuple list from a dict with a tuple/value pair for every value that is a list

get(key, default)

update(values)

class galaxy.util.ParamsWithSpecs(specs=None, params=None)

Bases: collections.defaultdict

galaxy.util.asbool(obj)

galaxy.util.commaify(amount)

galaxy.util.compare_urls(url1, url2, compare_scheme=True, compare_hostname=True, compare_path=True)

galaxy.util.docstring_trim(docstring)

Trimming python doc strings. Taken from: http://www.python.org/dev/peps/pep-0257/

galaxy.util.file_iter(fname, sep=None)

This generator iterates over a file and yields its lines splitted via the C{sep} parameter. Skips empty lines and lines starting with the C{#} character.

>>> lines = [ line for line in file_iter(__file__) ]
>>> len(lines) !=  0
True

galaxy.util.file_reader(fp, chunk_size=65536)

This generator yields the open fileobject in chunks (default 64k). Closes the file at the end

galaxy.util.force_symlink(source, link_name)

galaxy.util.galaxy_directory()

galaxy.util.get_charset_from_http_headers(headers, default=None)

galaxy.util.get_file_size(value, default=None)

galaxy.util.in_directory(file, directory, local_path_module=<module 'posixpath' from '/home/docs/checkouts/readthedocs.org/user_builds/jmchilton-galaxy/envs/stable/lib/python2.7/posixpath.pyc'>)

Return true, if the common prefix of both is equal to directory e.g. /a/b/c/d.rst and directory is /a/b, the common prefix is /a/b

galaxy.util.is_binary(value, binary_chars=None)

File is binary if it contains a null-byte by default (e.g. behavior of grep, etc.). This may fail for utf-16 files, but so would ASCII encoding. >>> is_binary( string.printable ) False >>> is_binary( ‘xcex94’ ) False >>> is_binary( ‘000’ ) True

galaxy.util.is_multi_byte(chars)

galaxy.util.is_uuid(value)

This method returns True if value is a UUID, otherwise False. >>> is_uuid( “123e4567-e89b-12d3-a456-426655440000” ) True >>> is_uuid( “0x3242340298902834” ) False

galaxy.util.listify(item, do_strip=False)

Make a single item a single item list, or return a list if passed a list. Passing a None returns an empty list.

galaxy.util.merge_sorted_iterables(operator, *iterables)

>>> operator = lambda x: x
>>> list( merge_sorted_iterables( operator, [1,2,3], [4,5] ) )
[1, 2, 3, 4, 5]
>>> list( merge_sorted_iterables( operator, [4, 5], [1,2,3] ) )
[1, 2, 3, 4, 5]
>>> list( merge_sorted_iterables( operator, [1, 4, 5], [2], [3] ) )
[1, 2, 3, 4, 5]

galaxy.util.mkstemp_ln(src, prefix='mkstemp_ln_')

From tempfile._mkstemp_inner, generate a hard link in the same dir with a random name. Created so we can persist the underlying file of a NamedTemporaryFile upon its closure.

galaxy.util.move_merge(source, target)

galaxy.util.nice_size(size)

Returns a readably formatted string with the size

>>> nice_size(100)
'100 bytes'
>>> nice_size(10000)
'9.8 KB'
>>> nice_size(1000000)
'976.6 KB'
>>> nice_size(100000000)
'95.4 MB'

galaxy.util.object_to_string(obj)

galaxy.util.parse_xml(fname)

Returns a parsed xml tree

galaxy.util.parse_xml_string(xml_string)

galaxy.util.pretty_print_json(json_data, is_json_string=False)

galaxy.util.pretty_print_xml(elem, level=0)

galaxy.util.read_build_sites(filename, check_builds=True)

read db names to ucsc mappings from file, this file should probably be merged with the one above

galaxy.util.read_dbnames(filename)

Read build names from file

galaxy.util.ready_name_for_url(raw_name)

General method to convert a string (i.e. object name) to a URL-ready slug.

>>> ready_name_for_url( "My Cool Object" )
'My-Cool-Object'
>>> ready_name_for_url( "!My Cool Object!" )
'My-Cool-Object'
>>> ready_name_for_url( "Hello₩◎ґʟⅾ" )
'Hello'

galaxy.util.recursively_stringify_dictionary_keys(d)

galaxy.util.relativize_symlinks(path, start=None, followlinks=False)

galaxy.util.restore_text(text, character_map={'@': '__at__', '\t': '__tc__', '\n': '__cn__', '\r': '__cr__', '[': '__ob__', ']': '__cb__', '#': '__pd__', '"': '__dq__', "'": '__sq__', '{': '__oc__', '}': '__cc__', '<': '__lt__', '>': '__gt__'})

Restores sanitized text

galaxy.util.roundify(amount, sfs=2)

Take a number in string form and truncate to ‘sfs’ significant figures.

galaxy.util.rst_to_html(s)

Convert a blob of reStructuredText to HTML

galaxy.util.safe_str_cmp(a, b)

galaxy.util.sanitize_for_filename(text, default=None)

Restricts the characters that are allowed in a filename portion; Returns default value or a unique id string if result is not a valid name. Method is overly aggressive to minimize possible complications, but a maximum length is not considered.

galaxy.util.sanitize_lists_to_string(values, valid_characters=set(['!', ' ', ')', '(', '+', '*', '-', ', ', '/', '.', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8', ':', '=', '?', 'A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'K', 'J', 'M', 'L', 'O', 'N', 'Q', 'P', 'S', 'R', 'U', 'T', 'W', 'V', 'Y', 'X', 'Z', '_', '^', 'a', 'c', 'b', 'e', 'd', 'g', 'f', 'i', 'h', 'k', 'j', 'm', 'l', 'o', 'n', 'q', 'p', 's', 'r', 'u', 't', 'w', 'v', 'y', 'x', 'z']), character_map={'@': '__at__', '\t': '__tc__', '\n': '__cn__', '\r': '__cr__', '[': '__ob__', ']': '__cb__', '#': '__pd__', '"': '__dq__', "'": '__sq__', '{': '__oc__', '}': '__cc__', '<': '__lt__', '>': '__gt__'}, invalid_character='X')

galaxy.util.sanitize_param(value, valid_characters=set(['!', ' ', ')', '(', '+', '*', '-', ', ', '/', '.', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8', ':', '=', '?', 'A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'K', 'J', 'M', 'L', 'O', 'N', 'Q', 'P', 'S', 'R', 'U', 'T', 'W', 'V', 'Y', 'X', 'Z', '_', '^', 'a', 'c', 'b', 'e', 'd', 'g', 'f', 'i', 'h', 'k', 'j', 'm', 'l', 'o', 'n', 'q', 'p', 's', 'r', 'u', 't', 'w', 'v', 'y', 'x', 'z']), character_map={'@': '__at__', '\t': '__tc__', '\n': '__cn__', '\r': '__cr__', '[': '__ob__', ']': '__cb__', '#': '__pd__', '"': '__dq__', "'": '__sq__', '{': '__oc__', '}': '__cc__', '<': '__lt__', '>': '__gt__'}, invalid_character='X')

Clean incoming parameters (strings or lists)

galaxy.util.sanitize_text(text, valid_characters=set(['!', ' ', ')', '(', '+', '*', '-', ', ', '/', '.', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8', ':', '=', '?', 'A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'K', 'J', 'M', 'L', 'O', 'N', 'Q', 'P', 'S', 'R', 'U', 'T', 'W', 'V', 'Y', 'X', 'Z', '_', '^', 'a', 'c', 'b', 'e', 'd', 'g', 'f', 'i', 'h', 'k', 'j', 'm', 'l', 'o', 'n', 'q', 'p', 's', 'r', 'u', 't', 'w', 'v', 'y', 'x', 'z']), character_map={'@': '__at__', '\t': '__tc__', '\n': '__cn__', '\r': '__cr__', '[': '__ob__', ']': '__cb__', '#': '__pd__', '"': '__dq__', "'": '__sq__', '{': '__oc__', '}': '__cc__', '<': '__lt__', '>': '__gt__'}, invalid_character='X')

Restricts the characters that are allowed in text; accepts both strings and lists of strings; non-string entities will be cast to strings.

galaxy.util.send_mail(frm, to, subject, body, config)

Sends an email.

galaxy.util.shrink_stream_by_size(value, size, join_by='..', left_larger=True, beginning_on_size_error=False, end_on_size_error=False)

galaxy.util.shrink_string_by_size(value, size, join_by='..', left_larger=True, beginning_on_size_error=False, end_on_size_error=False)

galaxy.util.size_to_bytes(size)

Returns a number of bytes if given a reasonably formatted string with the size

galaxy.util.smart_str(s, encoding='utf-8', strings_only=False, errors='strict')

Returns a bytestring version of ‘s’, encoded as specified in ‘encoding’.

If strings_only is True, don’t convert (some) non-string-like objects.

Adapted from an older, simpler version of django.utils.encoding.smart_str.

galaxy.util.string_as_bool(string)

galaxy.util.string_as_bool_or_none(string)

Returns True, None or False based on the argument:

True if passed True, ‘True’, ‘Yes’, or ‘On’ None if passed None or ‘None’ False otherwise

Note: string comparison is case-insensitive so lowecase versions of those function equivalently.

galaxy.util.string_to_object(s)

galaxy.util.stringify_dictionary_keys(in_dict)

galaxy.util.synchronized(func)

This wrapper will serialize access to ‘func’ to a single thread. Use it as a decorator.

galaxy.util.umask_fix_perms(path, umask, unmasked_perms, gid=None)

umask-friendly permissions fixing

galaxy.util.unicodify(value, encoding='utf-8', error='replace', default=None)

Returns a unicode string or None

galaxy.util.unique_id(KEY_SIZE=128)

Generates an unique id

>>> ids = [ unique_id() for i in range(1000) ]
>>> len(set(ids))
1000

galaxy.util.xml_element_compare(elem1, elem2)

galaxy.util.xml_element_list_compare(elem_list1, elem_list2)

galaxy.util.xml_element_to_dict(elem)

galaxy.util.xml_text(root, name=None)

Returns the text inside an element

galaxy.util.xml_to_string(elem, pretty=False)

Returns a string from an xml tree

aliaspickler Module

class galaxy.util.aliaspickler.AliasPickleModule(aliases)

Bases: object

dump(obj, fileobj, protocol=0)

dumps(obj, protocol=0)

load(fileobj)

loads(string)

class galaxy.util.aliaspickler.AliasUnpickler(aliases, *args, **kw)

Bases: pickle.Unpickler

find_class(module, name)

bunch Module

class galaxy.util.bunch.Bunch(**kwds)

Bases: object

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52308

Often we want to just collect a bunch of stuff together, naming each item of the bunch; a dictionary’s OK for that, but a small do-nothing class is even handier, and prettier to use.

get(key, default=None)

items()

keys()

values()

debugging Module

class galaxy.util.debugging.SimpleProfiler(log=None)

Bases: object

Simple profiler that captures the duration between calls to report and stores the results in a list.

REPORT_FORMAT = '%20f: %s'

get_reports()

report(msg)

start(msg=None)

galaxy.util.debugging.stack_trace_string(max_depth=None, line_format='{index}:{file}:{function}:{line}')

Returns a string representation of the current stack.

Parameters:depth – positive integer to control how many levels of the stack are

returned. max_depth=None returns the entire stack (default).

expressions Module

Expression evaluation support.

For the moment this depends on python’s eval. In the future it should be replaced with a “safe” parser.

class galaxy.util.expressions.ExpressionContext(dict, parent=None)

Bases: object, UserDict.DictMixin

hash_util Module

Utility functions for bi-directional Python version compatibility. Python 2.5 introduced hashlib which replaced sha in Python 2.4 and previous versions.

galaxy.util.hash_util.hmac_new(key, value)

galaxy.util.hash_util.is_hashable(value)

galaxy.util.hash_util.new_secure_hash(text_type=None)

Returns either a sha1 hash object (if called with no arguments), or a hexdigest of the sha1 hash of the argument text_type.

heartbeat Module

class galaxy.util.heartbeat.Heartbeat(name='Heartbeat Thread', period=20, fname='heartbeat.log')

Bases: threading.Thread

Thread that periodically dumps the state of all threads to a file

get_interesting_stack_frame(stack_frames)

Scans a given backtrace stack frames, returns a single quadraple of [filename, line, function-name, text] of the single, deepest, most interesting frame.

Interesting being:

inside the galaxy source code ("/lib/galaxy"),
prefreably not an egg.

print_nonsleeping(threads_object_dict)

run()

shutdown()

thread_is_sleeping(last_stack_frame)

Returns True if the given stack-frame represents a known sleeper function (at least in python 2.5)

galaxy.util.heartbeat.get_current_thread_object_dict()

Get a dictionary of all ‘Thread’ objects created via the threading module keyed by thread_id. Note that not all interpreter threads have a thread objects, only the main thread and any created via the ‘threading’ module. Threads created via the low level ‘thread’ module will not be in the returned dictionary.

HACK: This mucks with the internals of the threading module since that

module does not expose any way to match ‘Thread’ objects with intepreter thread identifiers (though it should).

inflection Module

class galaxy.util.inflection.Base

Locale inflectors must inherit from this base class inorder to provide the basic Inflector functionality

camelize(word)

Returns given word as CamelCased Converts a word like “send_email” to “SendEmail”. It will remove non alphanumeric character from the word, so “who’s online” will be converted to “WhoSOnline”

classify(table_name)

Converts a table name to its class name according to rails naming conventions. Example: Converts “people” to “Person”

cond_plural(number_of_records, word)

Returns the plural form of a word if first parameter is greater than 1

demodulize(module_name)

foreignKey(class_name, separate_class_name_and_id_with_underscore=1)

Returns class_name in underscored form, with “_id” tacked on at the end. This is for use in dealing with the database.

humanize(word, uppercase='')

Returns a human-readable string from word Returns a human-readable string from word, by replacing underscores with a space, and by upper-casing the initial character by default. If you need to uppercase all the words you just have to pass ‘all’ as a second parameter.

modulize(module_description)

ordinalize(number)

Converts number to its ordinal English form. This method converts 13 to 13th, 2 to 2nd ...

string_replace(word, find, replace)

This function returns a copy of word, translating all occurrences of each character in find to the corresponding character in replace

tableize(class_name)

Converts a class name to its table name according to rails naming conventions. Example. Converts “Person” to “people”

titleize(word, uppercase='')

Converts an underscored or CamelCase word into a English sentence. The titleize function converts text like “WelcomePage”, “welcome_page” or “welcome page” to this “Welcome Page”. If second parameter is set to ‘first’ it will only capitalize the first character of the title.

unaccent(text)

Transforms a string to its unaccented version. This might be useful for generating “friendly” URLs

underscore(word)

Converts a word “into_it_s_underscored_version” Convert any “CamelCased” or “ordinary Word” into an “underscored_word”. This can be really useful for creating friendly URLs.

urlize(text)

Transform a string its unaccented and underscored version ready to be inserted in friendly URLs

variablize(word)

Same as camelize but first char is lowercased Converts a word like “send_email” to “sendEmail”. It will remove non alphanumeric character from the word, so “who’s online” will be converted to “whoSOnline”

class galaxy.util.inflection.English

Bases: galaxy.util.inflection.Base

Inflector for pluralize and singularize English nouns.

This is the default Inflector for the Inflector obj

pluralize(word)

Pluralizes English nouns.

singularize(word)

Singularizes English nouns.

class galaxy.util.inflection.Inflector(Inflector=<class galaxy.util.inflection.English>)

Inflector for pluralizing and singularizing nouns.

It provides methods for helping on creating programs based on naming conventions like on Ruby on Rails.

camelize(word)

Returns given word as CamelCased Converts a word like “send_email” to “SendEmail”. It will remove non alphanumeric character from the word, so “who’s online” will be converted to “WhoSOnline”

classify(table_name)

Converts a table name to its class name according to rails naming conventions. Example: Converts “people” to “Person”

cond_plural(number_of_records, word)

Returns the plural form of a word if first parameter is greater than 1

demodulize(module_name)

foreignKey(class_name, separate_class_name_and_id_with_underscore=1)

Returns class_name in underscored form, with “_id” tacked on at the end. This is for use in dealing with the database.

humanize(word, uppercase='')

Returns a human-readable string from word Returns a human-readable string from word, by replacing underscores with a space, and by upper-casing the initial character by default. If you need to uppercase all the words you just have to pass ‘all’ as a second parameter.

modulize(module_description)

ordinalize(number)

Converts number to its ordinal form. This method converts 13 to 13th, 2 to 2nd ...

pluralize(word)

Pluralizes nouns.

singularize(word)

Singularizes nouns.

tableize(class_name)

Converts a class name to its table name according to rails naming conventions. Example. Converts “Person” to “people”

titleize(word, uppercase='')

Converts an underscored or CamelCase word into a sentence. The titleize function converts text like “WelcomePage”, “welcome_page” or “welcome page” to this “Welcome Page”. If the “uppercase” parameter is set to ‘first’ it will only capitalize the first character of the title.

unaccent(text)

Transforms a string to its unaccented version. This might be useful for generating “friendly” URLs

underscore(word)

Converts a word “into_it_s_underscored_version” Convert any “CamelCased” or “ordinary Word” into an “underscored_word”. This can be really useful for creating friendly URLs.

urlize(text)

Transform a string to its unaccented and underscored version ready to be inserted in friendly URLs

variablize(word)

Same as camelize but first char is lowercased Converts a word like “send_email” to “sendEmail”. It will remove non alphanumeric character from the word, so “who’s online” will be converted to “whoSOnline”

json Module

galaxy.util.json.dumps(obj, skipkeys=False, ensure_ascii=True, check_circular=True, allow_nan=True, cls=None, indent=None, separators=None, encoding='utf-8', default=None, sort_keys=False, **kw)

Serialize obj to a JSON formatted str.

If skipkeys is false then dict keys that are not basic types (str, unicode, int, long, float, bool, None) will be skipped instead of raising a TypeError.

If ensure_ascii is false, all non-ASCII characters are not escaped, and the return value may be a unicode instance. See dump for details.

If check_circular is false, then the circular reference check for container types will be skipped and a circular reference will result in an OverflowError (or worse).

If allow_nan is false, then it will be a ValueError to serialize out of range float values (nan, inf, -inf) in strict compliance of the JSON specification, instead of using the JavaScript equivalents (NaN, Infinity, -Infinity).

If indent is a non-negative integer, then JSON array elements and object members will be pretty-printed with that indent level. An indent level of 0 will only insert newlines. None is the most compact representation. Since the default item separator is ', ', the output might include trailing whitespace when indent is specified. You can use separators=(',', ': ') to avoid this.

If separators is an (item_separator, dict_separator) tuple then it will be used instead of the default (', ', ': ') separators. (',', ':') is the most compact JSON representation.

encoding is the character encoding for str instances, default is UTF-8.

default(obj) is a function that should return a serializable version of obj or raise TypeError. The default simply raises TypeError.

If sort_keys is True (default: False), then the output of dictionaries will be sorted by key.

To use a custom JSONEncoder subclass (e.g. one that overrides the .default() method to serialize additional types), specify it with the cls kwarg; otherwise JSONEncoder is used.

galaxy.util.json.loads(s, encoding=None, cls=None, object_hook=None, parse_float=None, parse_int=None, parse_constant=None, object_pairs_hook=None, **kw)

Deserialize s (a str or unicode instance containing a JSON document) to a Python object.

If s is a str instance and is encoded with an ASCII based encoding other than utf-8 (e.g. latin-1) then an appropriate encoding name must be specified. Encodings that are not ASCII based (such as UCS-2) are not allowed and should be decoded to unicode first.

object_hook is an optional function that will be called with the result of any object literal decode (a dict). The return value of object_hook will be used instead of the dict. This feature can be used to implement custom decoders (e.g. JSON-RPC class hinting).

object_pairs_hook is an optional function that will be called with the result of any object literal decoded with an ordered list of pairs. The return value of object_pairs_hook will be used instead of the dict. This feature can be used to implement custom decoders that rely on the order that the key and value pairs are decoded (for example, collections.OrderedDict will remember the order of insertion). If object_hook is also defined, the object_pairs_hook takes priority.

parse_float, if specified, will be called with the string of every JSON float to be decoded. By default this is equivalent to float(num_str). This can be used to use another datatype or parser for JSON floats (e.g. decimal.Decimal).

parse_int, if specified, will be called with the string of every JSON int to be decoded. By default this is equivalent to int(num_str). This can be used to use another datatype or parser for JSON integers (e.g. float).

parse_constant, if specified, will be called with one of the following strings: -Infinity, Infinity, NaN, null, true, false. This can be used to raise an exception if invalid JSON numbers are encountered.

To use a custom JSONDecoder subclass, specify it with the cls kwarg; otherwise JSONDecoder is used.

galaxy.util.json.safe_dumps(*args, **kwargs)

This is a wrapper around dumps that encodes Infinity and NaN values. It’s a fairly rare case (which will be low in request volume). Basically, we tell json.dumps to blow up if it encounters Infinity/NaN, and we ‘fix’ it before re-encoding.

galaxy.util.json.json_fix(val)

galaxy.util.json.validate_jsonrpc_request(request, regular_methods, notification_methods)

galaxy.util.json.validate_jsonrpc_response(response, id=None)

galaxy.util.json.jsonrpc_request(method, params=None, id=None, jsonrpc='2.0')

galaxy.util.json.jsonrpc_response(request=None, id=None, result=None, error=None, jsonrpc='2.0')

lrucache Module

Kanwei Li, 03/2010

Simple LRU cache that uses a dictionary to store a specified number of objects at a time.

class galaxy.util.lrucache.LRUCache(num_elements)

clear()

Clears/initiates storage variables

memdump Module

class galaxy.util.memdump.Memdump(signum=10, fname='memdump.log')

Bases: object

dump(signum, stack)

get(update=False)

setref()

none_like Module

Objects with No values

class galaxy.util.none_like.NoneDataset(datatypes_registry=None, ext='data', dbkey='?')

Bases: galaxy.util.none_like.RecursiveNone

missing_meta()

class galaxy.util.none_like.RecursiveNone

odict Module

Ordered dictionary implementation.

class galaxy.util.odict.odict(dict=None)

Bases: UserDict.UserDict

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747

This dictionary class extends UserDict to record the order in which items are added. Calling keys(), values(), items(), etc. will return results in this order.

clear()

copy()

insert(index, key, item)

items()

iteritems()

iterkeys()

itervalues()

keys()

popitem()

reverse()

setdefault(key, failobj=None)

update(dict)

values()

sanitize_html Module

HTML Sanitizer (ripped from feedparser)

galaxy.util.sanitize_html.sanitize_html(htmlSource, encoding='utf-8', type='text/html')

shed_util Module

shed_util_common Module

streamball Module

A simple wrapper for writing tarballs as a stream.

class galaxy.util.streamball.StreamBall(mode, members=None)

Bases: object

add(file, relpath, check_file=False)

stream(environ, start_response)

class galaxy.util.streamball.ZipBall(tmpf, tmpd)

Bases: object

stream(environ, start_response)

template Module

galaxy.util.template.fill_template(template_text, context=None, **kwargs)

topsort Module

Topological sort.

From Tim Peters, see:

http://mail.python.org/pipermail/python-list/1999-July/006660.html

topsort takes a list of pairs, where each pair (x, y) is taken to mean that x <= y wrt some abstract partial ordering. The return value is a list, representing a total ordering that respects all the input constraints. E.g.,

topsort( [(1,2), (3,3)] )

Valid topological sorts would be any of (but nothing other than)

[3, 1, 2] [1, 3, 2] [1, 2, 3]

... however this variant ensures that ‘key’ order (first element of tuple) is preserved so the following will be result returned:

[1, 3, 2]

because those are the permutations of the input elements that respect the “1 precedes 2” and “3 precedes 3” input constraints. Note that a constraint of the form (x, x) is really just a trick to make sure x appears somewhere in the output list.

If there’s a cycle in the constraints, say

topsort( [(1,2), (2,1)] )

then CycleError is raised, and the exception object supports many methods to help analyze and break the cycles. This requires a good deal more code than topsort itself!

exception galaxy.util.topsort.CycleError(sofar, numpreds, succs)

Bases: exceptions.Exception

get_elements()

get_pairlist()

get_partial()

get_pred_counts()

get_preds()

get_succs()

pick_a_cycle()

galaxy.util.topsort.topsort(pairlist)

galaxy.util.topsort.topsort_levels(pairlist)

Subpackages

• backports Package
  • backports Package
  • Subpackages
    • importlib Package
      • importlib Package