traversal

add2edges

gunfolds.solvers.traversal.add2edges(g, e, p)

Break edge e[0] -> e[1] into two pieces e[0] -> p and p -> e[1] and add them to g

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

addaAedge

gunfolds.solvers.traversal.addaAedge(g, v, b)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

Returns:

Return type:

addacedge

gunfolds.solvers.traversal.addacedge(g, v, b)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

Returns:

Return type:

addanedge

gunfolds.solvers.traversal.addanedge(g, e)

Add edge e[0] -> e[1] to g

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

Returns:

Return type:

addapath

gunfolds.solvers.traversal.addapath(g, v, b)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

Returns:

Return type:

addavedge

gunfolds.solvers.traversal.addavedge(g, v, b)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

Returns:

Return type:

addaVpath

gunfolds.solvers.traversal.addaVpath(g, v, b)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

Returns:

Return type:

check3

gunfolds.solvers.traversal.check3(e1, e2, e3, j1, j2, j3, g2, f=[], c=[])

Parameters:

• e1 –

• e2 –

• e3 –

• j1 –

• j2 –

• j3 –

• g2 –

• f –

• c –

Returns:

Return type:

checkable

gunfolds.solvers.traversal.checkable(g2)

Parameters:

g2 –

Returns:

Return type:

checkAedge

gunfolds.solvers.traversal.checkAedge(v, g2)

Nodes to check to merge the virtual nodes of A ( b->a<-c )

Parameters:

• v –

• g2 –

Returns:

Return type:

checkApath

gunfolds.solvers.traversal.checkApath(p, g2)

Parameters:

• p –

• g2 –

Returns:

Return type:

checkbedges

gunfolds.solvers.traversal.checkbedges(v, bel, g2)

Parameters:

• v –

• bel –

• g2 –

Returns:

Return type:

checkcedge

gunfolds.solvers.traversal.checkcedge(c, g2)

Nodes to check to merge the virtual nodes of c ( a->b->c )

Parameters:

• c –

• g2 –

Returns:

Return type:

checkedge

gunfolds.solvers.traversal.checkedge(e, g2)

Parameters:

• e –

• g2 –

Returns:

Return type:

checker

gunfolds.solvers.traversal.checker(n, ee)

Parameters:

• n –

• ee –

Returns:

Return type:

checkerDS

gunfolds.solvers.traversal.checkerDS(n, ee)

Parameters:

• n –

• ee –

Returns:

Return type:

checkvedge

gunfolds.solvers.traversal.checkvedge(v, g2)

Nodes to check to merge the virtual nodes of v ( b<-a->c )

Parameters:

• v –

• g2 –

Returns:

Return type:

childrenedges

gunfolds.solvers.traversal.childrenedges(n, c, el)

Parameters:

• n ((guess)string) – single node string

• c – mutable list of children of node n (will be changed as a side effect)

• el – list of edges available for construction (side effect change)

Returns:

Return type:

chunks

gunfolds.solvers.traversal.chunks(l, n)

Yield successive n-sized chunks from l.

Parameters:

• l –

• n (integer) –

cleanedges

gunfolds.solvers.traversal.cleanedges(e, p, g, mask)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• mask –

cleanVedges

gunfolds.solvers.traversal.cleanVedges(g, e, p, mask)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

• mask –

cloneempty

gunfolds.solvers.traversal.cloneempty(g)

Parameters:

g (dictionary (gunfolds graphs)) – gunfolds graph

Returns:

Return type:

conformanceDS

gunfolds.solvers.traversal.conformanceDS(g2, gg, order, f=[], c=[])

Parameters:

• g2 –

• gg –

• order –

• f –

• c –

Returns:

Return type:

del2edges

gunfolds.solvers.traversal.del2edges(g, e, p, mask)

Restore the graph as it was before adding e[0]->p and p->e[1]

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

• mask –

Returns:

Return type:

del_empty

gunfolds.solvers.traversal.del_empty(d)

Parameters:

d –

Returns:

Return type:

delaAedge

gunfolds.solvers.traversal.delaAedge(g, v, b, mask)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

• mask –

delacedge

gunfolds.solvers.traversal.delacedge(g, v, b, mask)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

• mask –

delanedge

gunfolds.solvers.traversal.delanedge(g, e, mask)

Delete edge e[0] -> e[1] from g if it was not there before

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• mask –

Returns:

Return type:

delapath

gunfolds.solvers.traversal.delapath(g, v, b, mask)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

• mask –

delavedge

gunfolds.solvers.traversal.delavedge(g, v, b, mask)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

• mask –

delaVpath

gunfolds.solvers.traversal.delaVpath(g, v, b, mask)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• v –

• b –

• mask –

Returns:

Return type:

edge_function_idx

gunfolds.solvers.traversal.edge_function_idx(edge)

Parameters:

edge –

Returns:

Return type:

edge_increment_ok

gunfolds.solvers.traversal.edge_increment_ok(s, m, e, g, g2)

Parameters:

• s – start

• m – middle

:param e : end :type e:

Parameters:

• g –

• g2 –

Returns:

Return type:

esig

gunfolds.solvers.traversal.esig(l, n)

Turns edge list into a hash string

Parameters:

• l –

• n –

Returns:

Return type:

integer

forks

gunfolds.solvers.traversal.forks(n, c, el, bl, doempty=<function <lambda>>)

Parameters:

• n ((guess)string) – single node string

• c – mutable list of children of node n (will be changed as a side effect)

• el – list of edges available for construction (side effect change)

• bl – list of bidirected edges

• doempty –

Returns:

Return type:

gpurgepath

gunfolds.solvers.traversal.gpurgepath(g, path)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• path –

gsig

gunfolds.solvers.traversal.gsig(g)

Turns input graph g into a hash string using edges

Parameters:

g (dictionary (gunfolds graphs)) – gunfolds graph

Returns:

Return type:

inorder_check2

gunfolds.solvers.traversal.inorder_check2(e1, e2, j1, j2, g2, f=[], c=[])

Parameters:

• e1 –

• e2 –

• j1 –

• j2 –

• g2 –

• f –

• c –

Returns:

Return type:

inorder_checks

gunfolds.solvers.traversal.inorder_checks(g2, gg)

Parameters:

• g2 –

• gg –

Returns:

Return type:

invertCDSelement

gunfolds.solvers.traversal.invertCDSelement(d_i)

Parameters:

d_i –

Returns:

Return type:

isAedge

gunfolds.solvers.traversal.isAedge(v)

Parameters:

v –

Returns:

Return type:

isApath

gunfolds.solvers.traversal.isApath(v)

Parameters:

v –

Returns:

Return type:

isCedge

gunfolds.solvers.traversal.isCedge(v)

Parameters:

v –

Returns:

Return type:

isedge

gunfolds.solvers.traversal.isedge(v)

Parameters:

v –

Returns:

Return type:

isvedge

gunfolds.solvers.traversal.isvedge(v)

Parameters:

v –

Returns:

Return type:

length_d_loopy_paths

gunfolds.solvers.traversal.length_d_loopy_paths(G, s, dt, p)

Iterate over nodes in G reachable from s in exactly d steps

Parameters:

• G (dictionary (gunfolds graphs)) – gunfolds format graph

• s –

• dt –

• p –

Returns:

Return type:

length_d_paths

gunfolds.solvers.traversal.length_d_paths(G, s, d)

Iterate over nodes in G reachable from s in exactly d steps

Parameters:

• G –

• s –

• d –

Returns:

Return type:

longpaths_pick

gunfolds.solvers.traversal.longpaths_pick(l)

Parameters:

l –

Returns:

Return type:

make_allforks_and_rest

gunfolds.solvers.traversal.make_allforks_and_rest(g, el, bl, dofullforks=True)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• el – list of edges available for construction (side effect change)

• bl – (GUESS)list of bidirected edges

• dofullforks –

Returns:

Return type:

make_emptyforks

gunfolds.solvers.traversal.make_emptyforks(n, c, el, bl)

An empty fork is a fork without the bidirected edge

Parameters:

• n ((guess)string) – single node string

• c – mutable list of children of node n (will be changed as a side effect)

• el – list of edges available for construction (side effect change)

• bl – list of bidirected edges

Returns:

Return type:

make_fullforks

gunfolds.solvers.traversal.make_fullforks(n, c, el, bl)

Parameters:

• n ((guess)string) – single node string

• c – mutable list of children of node n (will be changed as a side effect)

• el – list of edges available for construction (side effect change)

• bl – list of bidirected edges

Returns:

Return type:

make_longpaths

gunfolds.solvers.traversal.make_longpaths(g, el)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• el – (GUESS)list of edges available for construction (side effect change)

Returns:

Return type:

makechains

gunfolds.solvers.traversal.makechains(l)

Greedily construct 2 edge chains from edge list

Parameters:

l –

Returns:

Return type:

makesink

gunfolds.solvers.traversal.makesink(es)

Parameters:

es –

Returns:

Return type:

makesinks

gunfolds.solvers.traversal.makesinks(l)

Greedily construct 2 edge sinks ( b->a<-c ) from edge list

Parameters:

l –

Returns:

Return type:

mask2edges

gunfolds.solvers.traversal.mask2edges(g, e, p)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

maskaAedge

gunfolds.solvers.traversal.maskaAedge(g, e, p)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

maskaCedge

gunfolds.solvers.traversal.maskaCedge(g, e, p)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

maskanedge

gunfolds.solvers.traversal.maskanedge(g, e)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

Returns:

Return type:

maskapath

gunfolds.solvers.traversal.maskapath(g, e, p)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

maskavedge

gunfolds.solvers.traversal.maskavedge(g, e, p)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

maskaVpath

gunfolds.solvers.traversal.maskaVpath(g, e, p)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• e –

• p –

Returns:

Return type:

memo_no_return

gunfolds.solvers.traversal.memo_no_return(func)

Parameters:

func –

Returns:

Return type:

ok2add2edges

gunfolds.solvers.traversal.ok2add2edges(e, p, g, g2)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

Returns:

Return type:

ok2addaAedge

gunfolds.solvers.traversal.ok2addaAedge(e, p, g, g2)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

Returns:

Return type:

boolean

ok2addacedge

gunfolds.solvers.traversal.ok2addacedge(e, p, g, g2)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

Returns:

Return type:

boolean

ok2addanedge

gunfolds.solvers.traversal.ok2addanedge(s, e, g, g2, rate=1)

:param s : start :type s:

:param e : end :type e:

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

• rate –

Returns:

Return type:

ok2addanedge1

gunfolds.solvers.traversal.ok2addanedge1(s, e, g, g2, rate=1)

:param s : start :type s:

:param e : end :type e:

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

• rate –

Returns:

Return type:

ok2addanedge2

gunfolds.solvers.traversal.ok2addanedge2(s, e, g, g2, rate=1)

:param s : start :type s:

:param e : end :type e:

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

• rate –

Returns:

Return type:

ok2addapath

gunfolds.solvers.traversal.ok2addapath(e, p, g, g2)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

Returns:

Return type:

boolean

ok2addavedge

gunfolds.solvers.traversal.ok2addavedge(e, p, g, g2)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

Returns:

Return type:

boolean

ok2addaVpath

gunfolds.solvers.traversal.ok2addaVpath(e, p, g, g2, rate=2)

Parameters:

• e –

• p –

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

• rate –

Returns:

Return type:

boolean

prune_sort_CDS

gunfolds.solvers.traversal.prune_sort_CDS(cds, pool)

Parameters:

• cds –

• pool –

Returns:

Return type:

prunepaths_1D

gunfolds.solvers.traversal.prunepaths_1D(g2, path, conn)

Parameters:

• g2 –

• path –

• conn –

Returns:

Return type:

purgepath

gunfolds.solvers.traversal.purgepath(path, l)

Parameters:

• path –

• l –

selfloops

gunfolds.solvers.traversal.selfloops(l, g)

Parameters:

• l –

• g (dictionary (gunfolds graphs)) – gunfolds graph

Returns:

Return type:

signature

gunfolds.solvers.traversal.signature(g, edges)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• edges –

Returns:

Return type:

single_nodes

gunfolds.solvers.traversal.single_nodes(v, g2)

Returns a list of singleton nodes allowed for merging with v

Parameters:

• v –

• g2 –

Returns:

a list of singleton nodes allowed for merging with v

Return type:

supergraphs_in_eq

gunfolds.solvers.traversal.supergraphs_in_eq(g, g2, rate=1)

Find all supergraphs of g that are also in the same equivalence class with respect to g2 and the rate. Currently works only for bfu.undersample by 1

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• g2 –

• rate –

Returns:

Return type:

threedges_pick

gunfolds.solvers.traversal.threedges_pick(l)

Parameters:

l –

Returns:

Return type:

try_till_d_path

gunfolds.solvers.traversal.try_till_d_path(g, d, gt, order=None)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• d –

• gt –

• order –

Returns:

Return type:

try_till_path

gunfolds.solvers.traversal.try_till_path(g, gt)

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• gt –

Returns:

Return type:

twoedges_pick

gunfolds.solvers.traversal.twoedges_pick(l)

Parameters:

l –

Returns:

Return type:

v2g22g1

gunfolds.solvers.traversal.v2g22g1(g2, capsize=None, verbose=True)

Computes all g1 that are in the equivalence class for g2

Parameters:

• g2 –

• capsize –

• verbose –

Returns:

Return type:

vedgelist

gunfolds.solvers.traversal.vedgelist(g, pathtoo=False)

Returns a list of tuples for edges of g and forks a superugly organically grown function that badly needs refactoring

Parameters:

• g (dictionary (gunfolds graphs)) – gunfolds graph

• pathtoo –

Returns:

Return type: