utool.experimental package

Submodules

utool.experimental.bytecode_optimizations module

utool.experimental.dynamic_connectivity module

class utool.experimental.dynamic_connectivity.BinaryNode(value, parent=None, left=None, right=None)

Bases: object

left

right

set_child(other, dir_)

class utool.experimental.dynamic_connectivity.DummyEulerTourForest(nodes=None)

Bases: object

maintain a forests of euler tour trees

This is a bad implementation, but will let us use the DynConnGraph api

add_edge(u, v)

add_node(node)

components()

find_root(node)

has_edge(u, v)

remove_edge(u, v)

subtree(node)

to_networkx()

class utool.experimental.dynamic_connectivity.DynConnGraph(graph)

Bases: object

Stores a spanning forest with Euler Tour Trees

References

https://courses.csail.mit.edu/6.851/spring14/lectures/L20.pdf https://courses.csail.mit.edu/6.851/spring14/lectures/L20.html http://cs.stackexchange.com/questions/33595/what-is-the-most-efficient-algorithm-and-data-structure-for-maintaining-connecte

https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Poly%20logarithmic.pdf

DEFINES ET-Trees http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.8615&rep=rep1&type=pdf

https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Poly%20logarithmic.pdf http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdf http://courses.csail.mit.edu/6.854/16/Projects/B/dynamic-graphs-survey.pdf http://dl.acm.org/citation.cfm?id=502095 http://delivery.acm.org/10.1145/510000/502095/p723-holm.pdf?ip=128.213.17.14&id=502095&acc=ACTIVE%20SERVICE&key=7777116298C9657D%2EAF047EA360787914%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35&CFID=905563744&CFTOKEN=37809688&__acm__=1488222284_4ae91dd7a761430ee714f0c69c17b772

Notes

Paper uses level 0 at top, but video lecture uses floor(log(n)) as top. All edges start at level floor(log(n)). The level of each edge will change over time, but cannot decrease below zero. Let G[i] = subgraph graph at level i. (contains only edges of level i or greater) Let F[i] be Euler tour forest to correspond with G[i]. G[log(n)] = full graph Invariant 1 Every connected component of G_i has at most 2^i vertices. Invariant 2 F[0] ⊆ F[1] ⊆ F[2] ⊆ … ⊆ F[log(n)].

In other words: F[i] = F[log(n)] ∩ G_i, and F[log(n)] is the minimum spanning forest of G_{log(n)}, where the weight of an edge is its level. F[0] is a maximum spanning forest if using 0 as top level

CommandLine:

python -m utool.experimental.dynamic_connectivity DynConnGraph –show

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.dynamic_connectivity import *  # NOQA
>>> import networkx as nx
>>> import utool as ut
>>> import wbia.plottool as pt
>>> graph = nx.Graph([
>>>    (0, 1), (0, 2), (0, 3), (1, 3), (2, 4), (3, 4), (2, 3),
>>>    (5, 6), (5, 7), (5, 8), (6, 8), (7, 9), (8, 9), (7, 8),
>>> ])
>>> graph = nx.generators.cycle_graph(5)
>>> self = DynConnGraph(graph)
>>> pt.qtensure()
>>> pt.show_nx(self.graph, fnum=1)
>>> self.show_internals(fnum=2)
>>> self.remove_edge(1, 2)
>>> self.show_internals(fnum=3)
>>> self.remove_edge(3, 4)
>>> self.show_internals(fnum=4)
>>> ut.show_if_requested()

add_edge(u, v)

O(log(n))

is_connected(u, v)

Check if vertices u and v are connected. Query top level forest F[0] to see if u and v are in the same tree. This can be done by checking F_{log(n)} if Findroot(u) = Findroot(v). This costs O(log(n) / log(log(n))) using B-tree based Euler-Tour trees. but this trades off with a O(log^2(n)/log(log(n))) update This is O(log(n)) otherwise

remove_edge(u, v)

Using notation where 0 is top level

Intuitively speaking, when the level of a nontree edge is increased, it is because we have discovered that its end points are close enough in F to fit in a smaller tree on a higher level.

show_internals(fnum=None)

class utool.experimental.dynamic_connectivity.EulerTourForest

Bases: object

add_edge(u, v)

self = EulerTourForest() self.add_node(1) self.add_node(2) u, v = 1, 2

add_node(node)

find_root(node)

has_node(node)

reroot(old, new)

class utool.experimental.dynamic_connectivity.EulerTourList(iterable, load=1000)

Bases: object

load-list representation of an Euler tour inspired by sortedcontainers

this doesnt work for the same reason keyed bintrees dont work

the indexing needs to be implicit, but this has explicit indexes

append(value)

join(other)

Parameters:other –

CommandLine:

python -m sortedcontainers.sortedlist join2

Example

>>> from utool.experimental.dynamic_connectivity import *  # NOQA
>>> self = EulerTourList([1, 2, 3, 2, 4, 2, 1], load=3)
>>> other = EulerTourList([0, 5, 9, 5, 0], load=3)
>>> result = self.join(other)
>>> print(result)

split(pos, idx)

update(iterable)

class utool.experimental.dynamic_connectivity.EulerTourTree

Bases: object

CommandLine:

python -m utool.experimental.dynamic_connectivity EulerTourTree –show

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.dynamic_connectivity import *  # NOQA
>>> #mst = nx.balanced_tree(2, 2)
>>> edges = [
>>>     ('R', 'A'), ('R', 'B'),
>>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
>>>     ('B', 'F'), ('B', 'G'),
>>> ]
>>> mst = nx.Graph(edges)
>>> self = EulerTourTree.from_tree(mst)
>>> import wbia.plottool as pt
>>> pt.qt4ensure()
>>> fnum = 1
>>> pnum_ = pt.make_pnum_nextgen(1, 3)
>>> pt.show_nx(mst, pnum=pnum_(), fnum=fnum)
>>> pt.show_nx(self.to_networkx(), pnum=pnum_(), fnum=fnum)
>>> pt.show_nx(self.tour_tree.to_networkx(labels=['key', 'value']), pnum=pnum_(), fnum=fnum)
>>> print(self.tour)
>>> print(self.first_lookup)
>>> print(self.last_lookup)
>>> ut.show_if_requested()

cut(a, b, bstjoin=False)

cuts edge (a, b) into two parts because this is a tree

a, b = (2, 5) print(self.first_lookup[a] > self.first_lookup[b]) tree = self.tour_tree list(tree.item_slice(k1, k2))

find_root(node)

classmethod from_tour(tour, fast=False, start=0)

classmethod from_tree(mst, fast=True, start=0)

join(other)

reroot(s)

s = 3 s = ‘B’

Let os denote any occurrence of s. Splice out the first part of the sequence ending with the occurrence before os, remove its first occurrence (or), and tack this on to the end of the sequence which now begins with os. Add a new occurrence os to the end.

to_networkx()

class utool.experimental.dynamic_connectivity.TestETT

Bases: object

raise NotImplementedError()

hg clone https://bitbucket.org/mozman/bintrees

git clone git@github.com:Erotemic/bintrees.git

References

https://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.8615&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.208.2351&rep=rep1&type=pdf https://en.wikipedia.org/wiki/Euler_tour_technique

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.dynamic_connectivity import *  # NOQA
>>> edges = [(1, 2), (1, 6), (1, 5), (2, 3), (2, 4)]
>>> edges = [
>>>     ('R', 'A'), ('R', 'B'),
>>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
>>>     ('B', 'F'), ('B', 'G'),
>>> ]
>>> mst = nx.Graph(edges)
>>> #mst = nx.balanced_tree(2, 11)
>>> self = TestETT.from_tree(mst)
>>> import wbia.plottool as pt
>>> pt.qt4ensure()
>>> pt.show_nx(mst)

>>> mst = nx.balanced_tree(2, 4)

delete_edge_bst_version(a, b, bstjoin=False)

a, b = (2, 5) print(self.first_lookup[a] > self.first_lookup[b]) tree = self.tour_tree list(tree.item_slice(k1, k2))

delete_edge_list_version(a, b)

classmethod from_tour(tour, version='bst', fast=True)

classmethod from_tree(mst, version='bst', fast=True)

>>> # DISABLE_DOCTEST
>>> from utool.experimental.dynamic_connectivity import *  # NOQA
>>> mst = nx.balanced_tree(2, 4)
>>> self = TestETT.from_tree(mst)
>>> import wbia.plottool as pt
>>> pt.qt4ensure()
>>> pt.show_nx(self.to_networkx(), pnum=(2, 1, 1), fnum=1)

>>> a, b = 2, 5
>>> other = self.delete_edge_bst_version(a, b)
>>> pt.show_nx(other.to_networkx(), pnum=(2, 1, 1), fnum=2)

join_trees(t1, t2, e)

reroot(s)

s = 3 s = ‘B’

Let os denote any occurrence of s. Splice out the first part of the sequence ending with the occurrence before os, remove its first occurrence (or), and tack this on to the end of the sequence which now begins with os. Add a new occurrence os to the end.

to_networkx()

utool.experimental.dynamic_connectivity.comparison()

CommandLine:

python -m utool.experimental.dynamic_connectivity comparison –profile python -m utool.experimental.dynamic_connectivity comparison

utool.experimental.dynamic_connectivity.euler_tour_dfs(G, source=None)

adaptation of networkx dfs

utool.experimental.euler_tour_tree_avl module

class utool.experimental.euler_tour_tree_avl.EulerTourTree(iterable=None, root=None)

Bases: utool.util_dev.NiceRepr

TODO: generalize out the binary tree sequence part

CommandLine:

python -m utool.experimental.euler_tour_tree_avl EulerTourTree

References

Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation Henzinger and King 1995 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.8615&rep=rep1&type=pdf

Ignore:

>>> # DISABLE_DOCTEST
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> ETT = EulerTourTree
>>> self = ETT(['a', 'b', 'c', 'b', 'd', 'b', 'a'])
>>> self._assert_nodes()
>>> other = ETT(['E', 'F', 'G', 'F', 'E'])
>>> other2 = ETT(['E', 'F', 'G', 'F', 'E'])
>>> new = self + other + other2
>>> print(self)
>>> print(other)
>>> print(self + other)
>>> print(new)
>>> print(new + self + self)
>>> self.print_tree()
>>> #other.print_tree()
>>> #self.print_tree()

Ignore:

>>> # DISABLE_DOCTEST
>>> import networkx as nx
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> edges = [
>>>     ('R', 'A'), ('R', 'B'),
>>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
>>>     ('B', 'F'), ('B', 'G'),
>>> ]
>>> tour = euler_tour(nx.Graph(edges))
>>> print(tour)
>>> self = EulerTourTree(tour)
>>> print(self)
>>> assert list(self) == tour

copy()

get_ascii_tree()

get_node(index)

join(other)

min_elem()

print_tree()

repr_tree

reconstruct represented tree as a DiGraph to preserve the current rootedness

reroot(first_node, last_node)

Notes

● Pick any occurrence of the new root r. ● Split the tour into A and B, where B is the part of the tour before r. ● Delete the first node of A and append r. ● Concatenate B and A.

To change the root of T from r to s:

Let os denote any occurrence of s. Splice out the first part of the sequence ending with the occurrence before or, remove its first occurrence (or), and tack this on to the end of the sequence which now begins with os. Add a new occurrence os to the end.

CommandLine:

python -m utool.experimental.euler_tour_tree_avl reroot

Ignore:

>>> # DISABLE_DOCTEST
>>> import networkx as nx
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> edges = [
>>>     ('R', 'A'), ('R', 'B'),
>>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
>>>     ('B', 'F'), ('B', 'G'),
>>> ]
>>> edges = list(nx.balanced_tree(2, 2).edges())
>>> tour = euler_tour(nx.Graph(edges))
>>> self = EulerTourTree(tour)
>>> print('old_tour = %r' % (self,))
>>> nodes = list(self._traverse_nodes())
>>> self.first_lookup = {node.value: node for node in nodes[::-1]}
>>> self.last_lookup = {node.value: node for node in nodes}
>>> new_root_val = list(self)[445 % (len(tour) - 1)]
>>> new_root_val = 5
>>> print('new_root_val = %r' % (new_root_val,))
>>> first_node = self.first_lookup[new_root_val]
>>> last_node = self.last_lookup[new_root_val]
>>> self.reroot(first_node, last_node)
>>> print('new_tour = %r' % (self,))
>>> ut.quit_if_noshow()
>>> ut.show_if_requested()

show_nx(labels=['value'], edge_labels=False, fnum=None)

to_networkx(labels=None, edge_labels=False)

Get a networkx representation of the binary search tree.

values()

class utool.experimental.euler_tour_tree_avl.Node(key=None, value=None)

Bases: utool.util_dev.NiceRepr

Internal object, represents a tree node.

free()

Remove all references.

kids

set_child(direction, other)

val

xdata

compatibility with the C node_t struct

utool.experimental.euler_tour_tree_avl.ascii_tree(root, name=None)

utool.experimental.euler_tour_tree_avl.avl_insert_dir(root, new_node, direction=1)

Inserts a single node all the way to the left (direction=1) or right (direction=1)

CommandLine:

python -m utool.experimental.euler_tour_tree_avl avl_insert_dir –show python -m utool.experimental.euler_tour_tree_avl avl_insert_dir

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> import utool as ut
>>> root = Node(value='A')
>>> new_node = Node(value='B')
>>> new_root = avl_insert_dir(root, new_node, direction=1)
>>> new_root = avl_insert_dir(root, Node(value='Z'), direction=1)
>>> EulerTourTree(root=new_root)._assert_nodes()
>>> for v in ut.chr_range(5, base='C'):
>>>     new_root = avl_insert_dir(new_root, Node(value=v), direction=1)
>>>     self = EulerTourTree(root=new_root)
>>>     self._assert_nodes()
>>> new = EulerTourTree(root=new_root)
>>> print(new)
>>> ut.quit_if_noshow()
>>> ut.qtensure()
>>> new.show_nx(edge_labels=True)
>>> ut.show_if_requested()
>>> #ascii_tree(root)
>>> #print(result)

utool.experimental.euler_tour_tree_avl.avl_join(t1, t2, node)

Joins two trees t1 and t1 with an intermediate key-value pair

CommandLine:

python -m utool.experimental.euler_tour_tree_avl avl_join

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> self = EulerTourTree(['a', 'b', 'c', 'b', 'd', 'b', 'a'])
>>> other = EulerTourTree(['E', 'F', 'G', 'F', 'E'])
>>> node = Node(value='Q')
>>> root = avl_join(self.root, other.root, node)
>>> new = EulerTourTree(root=root)
>>> print('new = %r' % (new,))
>>> ut.quit_if_noshow()
>>> self.print_tree()
>>> other.print_tree()
>>> new.print_tree()

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> self = EulerTourTree(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'])
>>> other = EulerTourTree(['X'])
>>> node = Node(value='Q')
>>> root = avl_join(self.root, other.root, node)
>>> new = EulerTourTree(root=root)
>>> print('new = %r' % (new,))
>>> ut.quit_if_noshow()
>>> ut.qtensure()
>>> #self.show_nx(fnum=1)
>>> #other.show_nx(fnum=2)
>>> new.show_nx()

Running Time:

O(abs(r(t1) - r(t2))) O(abs(height(t1) - height(t2)))

utool.experimental.euler_tour_tree_avl.avl_join2(t1, t2)

join two trees without any intermediate key

Returns:new_root Return type:Node

O(log(n) + log(m)) = O(r(t1) + r(t2))

For AVL-Trees the rank r(t1) = height(t1) - 1

utool.experimental.euler_tour_tree_avl.avl_join_dir_recursive(t1, t2, node, direction)

Recursive version of join_left and join_right TODO: make this iterative using a stack

utool.experimental.euler_tour_tree_avl.avl_new_top(t1, t2, top, direction=0)

if direction == 0:

(t1, t2) is (left, right)

if direction == 1:

(t1, t2) is (right, left)

utool.experimental.euler_tour_tree_avl.avl_release_kids(node)

splits a node from its kids maintaining parent pointers

utool.experimental.euler_tour_tree_avl.avl_release_parent(node)

removes the parent of a child

utool.experimental.euler_tour_tree_avl.avl_rotate_double(root, direction)

Double rotation, either 0 (left) or 1 (right).

utool.experimental.euler_tour_tree_avl.avl_rotate_single(root, direction)

Single rotation, either 0 (left) or 1 (right).

utool.experimental.euler_tour_tree_avl.avl_split(root, node)

O(log(n))

Parameters:

• root (Node) – tree root
• node (Node) – node to split at

Returns:

(tl, tr, node)

tl contains all keys in the tree less than node tr contains all keys in the tree greater than node node is the node we split out

Return type:

puple

CommandLine:

python -m utool.experimental.euler_tour_tree_avl avl_split

Ignore:

>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> self = EulerTourTree(ut.chr_range(10))
>>> self.print_tree()
>>> node = self.get_node(5)
>>> part1, part2, bnode = avl_split(self.root, node)
>>> ascii_tree(part1)
>>> ascii_tree(part2)
>>> ascii_tree(bnode)

Ignore:

>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> test_avl_split(verbose=2)

utool.experimental.euler_tour_tree_avl.avl_split_first(root)

Removes the minimum element from the tree

Returns:new_root, first_node Return type:tuple

O(log(n)) = O(height(root))

utool.experimental.euler_tour_tree_avl.avl_split_last(root)

Removes the maximum element from the tree

Returns:new_root, last_node Return type:tuple

O(log(n)) = O(height(root))

utool.experimental.euler_tour_tree_avl.avl_split_old(root, key)

utool.experimental.euler_tour_tree_avl.backtrace_root(node)

Ignore:

>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> self = EulerTourTree(range(10))
>>> self._assert_nodes()
>>> root = self.root
>>> node = self.get_node(5)
>>> self.print_tree()
>>> print('node = %r' % (node,))
>>> rpath = backtrace_root(node)
>>> print('rpath = %r' % (rpath,))

utool.experimental.euler_tour_tree_avl.euler_tour(G, node=None, seen=None, visited=None)

definition from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.8615&rep=rep1&type=pdf

Example

>>> # DISABLE_DOCTEST
>>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
>>> edges = [
>>>     ('R', 'A'), ('R', 'B'),
>>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
>>>     ('B', 'F'), ('B', 'G'),
>>> ]
>>> G = nx.Graph(edges)
>>> node = list(G.nodes())[0]
>>> et1 = euler_tour(G, node)
>>> et2 = euler_tour_dfs(G, node)

utool.experimental.euler_tour_tree_avl.euler_tour_dfs(G, source=None)

adaptation of networkx dfs

utool.experimental.euler_tour_tree_avl.height(node)

utool.experimental.euler_tour_tree_avl.test_avl_split(verbose=1)

utool.experimental.pandas_highlight module

utool.experimental.pandas_highlight.monkey_to_str_columns(self, latex=False)

utool.experimental.pandas_highlight.pandas_repr(df)

utool.experimental.pandas_highlight.to_string_monkey(df, highlight_cols=None, latex=False)

monkey patch to pandas to highlight the maximum value in specified cols of a row

Ignore:

>>> from utool.experimental.pandas_highlight import *
>>> import pandas as pd
>>> df = pd.DataFrame(
>>>     np.array([[ 0.9,         0.86886931,  0.86842073,  0.9       ],
>>>               [ 0.34196218,  0.34289191,  0.34206377,  0.34252863],
>>>               [ 0.34827074,  0.34827074,  0.34827074,  0.34827074],
>>>               [ 0.76979453,  0.77214855,  0.77547518,  0.38850962]]),
>>>     columns=['sum(fgweights)', 'sum(weighted_ratio)', 'len(matches)', 'score_lnbnn_1vM'],
>>>     index=['match_state(match-v-rest)', 'match_state(nomatch-v-rest)', 'match_state(notcomp-v-rest)', 'photobomb_state']
>>> )
>>> highlight_cols = 'all'
>>> print(to_string_monkey(df, highlight_cols))
>>> print(to_string_monkey(df, highlight_cols, latex=True))

ut.editfile(pd.io.formats.printing.adjoin)

Module contents