straph.EulerTourForest package

Submodules

straph.etf.ChainedTreap module

class straph.etf.ChainedTreap.CTreapNode(data=None, parent=None, pred=None, suc=None, size=None, left=None, right=None)

Bases: object

A node of a Treap (priority is determined at random and used to balance the Treap)

clear()

find_root()

Find the root of the current node.

Returns

left_rotation()

Perform a left rotation on the Treap with the current TreapNode as the root https://en.wikipedia.org/wiki/Tree_rotation Note : This doesn’t change the cyclic order, successor and predecessor unchanged

Returns

New root (aka the right child)

right_rotation()

Perform a right rotation on the Treap with the current TreapNode as the root https://en.wikipedia.org/wiki/Tree_rotation Note : This doesn’t change the cyclic order, successor and predecessor unchanged

Returns

New root ( aka the left child)

property tree_number

update_size()

Used to keep the size

Returns

straph.etf.EulerTourForest module

class straph.etf.EulerTourForest.ETFCollections

Bases: object

Collection of Spanning Euler Forest (1 for each level of the algorithm)

insert(e)

Insert and edge in the Forest at the level 0

Parameters

e –

Returns

remove(e)

REMOVE AN EDGE in the current forest

Parameters

e –

Returns

replace(e, level)

REPLACE A TREE EDGE

Parameters

• e – edge

• level – level of the edge to replace in the forest

Returns

search(e)

class straph.etf.EulerTourForest.EulerTourForest(trees=None, tree_edge_2_node=None, non_tree_edges_al=None)

Bases: object

Custom Data Structure Consisting in a Forest of Euler Tour Trees In the same manner as a Spanning Forest if composed of Spanning Trees

add_edge_to_tree(E, present_node, node_to_add)

We assume that present_node is in E and we just add node_to_add.

Parameters

• E –

• present_node –

• node_to_add –

Returns

check_edge_endpoints(e)

Check if one of the endpoints is present in the forest

Parameters

e –

Returns

check_edge_presence(e)

Check if the edge is in the current spanning forest

Parameters

e –

Returns

insert_edge(l, SCC=None, format='cluster', exception=False, streaming_output=None)

Insert an edge in the Euler Tour Forest

Parameters

• l –

• SCC –

• format –

• exception –

• streaming_output –

Returns

is_tree_edge(e)

Return True if e is a tree edge, False otherwise

Parameters

e – an edge

Returns

link_euler_tour_trees(E1, E2, e)

Merge two euler tour tree

Parameters

• E1 – An euler tour tree

• E2 – An euler tour tree

• e – An edge

Returns

plot(title=None)

Plot the Euler Tour Trees in the Euler Tour Forest

Parameters

title – An optional title

Returns

remove_edge(l, SCC=None, format='cluster', exception=False, streaming_output=None)

Remove an edge from the Euler Tour Forest

Parameters

• l –

• SCC –

• format –

• exception –

• streaming_output –

Returns

replace_edge(E1, E2)

Find is there is a non tree edge linking E1 and E2

Parameters

• E1 – An euler tour tree

• E2 – An euler tour tree

Returns

a replacement edge if found, false otherwise

replacement_edge(E1, E2)

straph.etf.EulerTourForest.add_to_scc(T, SCC, format='streaming', exception=False, streaming_output=None)

Add the current tree T (aka a connected component) to SCC

Parameters

• format –

• exception –

• streaming_output –

• T – An Euler Tour Tree

• SCC – list of Strongly Connected Components

Returns

Updated SCC

straph.etf.EulerTourForest.construct_euler_tour_forest(edge_list)

Construct an Euler Tour Forest from an edge list (the initial graph may be disconnected).

Parameters

edge_list –

Returns

straph.etf.EulerTourForest.spanning_forest_from_edge_list(edge_list)

Construct a spanning forest from an edge list (graph may be disconnected)

Parameters

edge_list – [(u1,u2),(u0,u2),….]

Returns

Spanning Forest, which is a list of tuple : [(tree edge, non tree edge),…]

straph.etf.EulerTourForest.strongly_connected_components_ETF(S, isolated_nodes=True, format='cluster', streaming_output=None, free_memory=False)

straph.etf.EulerTourTree module

class straph.etf.EulerTourTree.EulerTourTree(root=None, first=None, last=None, weight=None, begin_time=None, end_time=None)

Bases: object

https://en.wikipedia.org/wiki/Euler_tour_technique

balance_down()

Balance the Treap to respect the Heap invariant, from root to leaves (full browsing)

Returns

check_heap_invariant()

Check the heap invariant of the Treap

Returns

True if invariant respected, False otherwise

cut(nodes)

Remove and edge from the Euler Tour Tree. [first,…,node_0,after_node_0,….,node_1,after_node_1,…,last] -> [first,…,before_node_0,node_0] [after_node_0,…,node_1,last] -> [first,…,before_node_0] [after_node_0,…,before_node_1] [after_node_1,…,last] -> [first,…,before_node_0,after_node_1,…,last] [after_node_0,before_node_1]

Parameters

nodes –

Returns

find_first()

find_last()

get_data_in_priority_order()

get_euler_tour()

Return the induced euler tour representation of the Tree

Returns

get_internal_structure()

insert(where=None, data=None, inlast=False, priority=None)

plot(title=None)

releaf(where)

remove(node)

Remove the node

Parameters

node – Node to remove

Returns

split(where)

Split the Euler Tour Tree according to the split in its Euler Tour. [first,…,where,after_where,…,last] -> [first,…,where] [after_where,…last] Note : The left subtree contains at least the node where whereas the right subtree can be empty.

Parameters

where – The split is effectuated just after where

Returns

Left subtree and Right subtree

straph.etf.EulerTourTree.construct_euler_tour_tree(edge_list)

Construct an Euler Tour Tree from an edge list

Parameters

edge_list – An edge list

Returns

An euler tour tree

straph.etf.EulerTourTree.euler_tour_from_edge_list(edge_list)

Compute the euler tour of a graph ( with edges, including self loops, instead of nodes). https://en.wikipedia.org/wiki/Euler_tour_technique

Parameters

edge_list – An edge list.

Returns

A list containing the euler tour.

straph.etf.EulerTourTree.find_root(node)

Find the root of the current node.

Parameters

node –

Returns

straph.etf.EulerTourTree.union_treap(T1, T2)

Module contents