graphkit

_normed_OCE

gunfolds.utils.graphkit._normed_OCE(g1, g2)

Return omission and comission errors for directed and bidirected edges.

Omission error is normalized by the number of edges present in the ground truth. Commision error is normalized by the number of possible edges minus the number of edges present in the ground truth.

Parameters:

• g1 (dictionary (gunfolds graph)) – the graph to check

• g2 (dictionary (gunfolds graph)) – the ground truth graph

Returns:

normalized omission and comission errors for directed and bidirected edges.

Return type:

dictionary

_normed_undirected_OCE

gunfolds.utils.graphkit._normed_undirected_OCE(g1, g2)

Return omission and comission errors for undirected edges.

Omission error is normalized by the number of edges present in the ground truth. Commision error is normalized by the number of possible edges minus the number of edges present in the ground truth.

Parameters:

• g1 (dictionary (gunfolds graph)) – the graph to check

• g2 (dictionary (gunfolds graph)) – the ground truth graph

Returns:

omission and comission errors for normalized undirected edges

Return type:

dictionary

_OCE

gunfolds.utils.graphkit._OCE(g1, g2)

Omission/commision error of g1 referenced to g2

Parameters:

• g1 (dictionary (gunfolds graph)) – the graph to check

• g2 (dictionary (gunfolds graph)) – the ground truth graph

Returns:

Omission/commision error for directed and bidirected edges

Return type:

dictionary

_undirected_OCE

gunfolds.utils.graphkit._undirected_OCE(g1, g2)

Returns omission/commision error of g1 referenced to g2 if both are undirected graphs.

Parameters:

• g1 (dictionary (gunfolds graph)) – the graph to check

• g2 (dictionary (gunfolds graph)) – the ground truth graph

Returns:

omission and comission errors for undirected edges

Return type:

dictionary

addanedge

gunfolds.utils.graphkit.addanedge(g, e)

Adds an edge e from the given graph g

Parameters:

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

• e (pair of integers) – edge to be added

addAring

gunfolds.utils.graphkit.addAring(g)

Add a ring to g in place

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

addedges

gunfolds.utils.graphkit.addedges(g, es)

Adds the edges in the list es for given graph g.

Parameters:

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

• es (list of pairs of integers) – list of edges to be added

bedgelist

gunfolds.utils.graphkit.bedgelist(g)

Bidirected edge list with flips

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

a list of tuples for bidirected edges of g

Return type:

list of tuples

bidirected_no_fork

gunfolds.utils.graphkit.bidirected_no_fork(g)

(Ask)

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

Return type:

boolean

bp_mean_degree_graph

gunfolds.utils.graphkit.bp_mean_degree_graph(node_num, degree, seed=None)

Generates a random bipartite graph with node_num, nodes and mean outgoing degree (degree)

Parameters:

• node_num (integer) – number of nodes

• degree (float) – degree

• seed (integer) – random seed

Returns:

a random bipartite graph with node_num, nodes and mean outgoing degree of degree

Return type:

dictionary(gunfolds graph)

bp_pow_degree_graph

gunfolds.utils.graphkit.bp_pow_degree_graph(node_num, degree, prob=0.7)

Generates a bipartite graph by powerlaw sequence of degree constructed using the Havel-Hakimi algorithm.

Parameters:

• node_num (integer) – number of nodes

• degree (integer) – degree

• prob (float) – probability

Returns:

a bipartite graph constructed using the Havel-Hakimi algorithm.

Return type:

dictionary(gunfolds graph)

cerror

gunfolds.utils.graphkit.cerror(d)

Returns normalized comission error

Parameters:

d (dictionary) – calculated error

Returns:

normalized comission error

Return type:

float

clean_leaf_nodes

gunfolds.utils.graphkit.clean_leaf_nodes(g)

Removes leaf_nodes of the given graph g

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

complement

gunfolds.utils.graphkit.complement(G)

Returns the complement of G

Parameters:

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

Returns:

the complement of G

Return type:

dictionary (gunfolds graph)

degree_ring

gunfolds.utils.graphkit.degree_ring(n, d)

Generate a ring graph with n nodes and average degree d

Parameters:

• n (integer) – number of nodes

• d (integer) – degree

Returns:

a ring graph with n nodes and average degree d

Return type:

dictionary(gunfolds graph)

delanedge

gunfolds.utils.graphkit.delanedge(g, e)

Deletes an edge e from the given graph g

Parameters:

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

• e (pair of integers) – edge to be deleted

deledges

gunfolds.utils.graphkit.deledges(g, es)

Deletes the edges in the list es for given graph g.

Parameters:

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

• es (list of pairs of integers) – list of edges to be deleted

density

gunfolds.utils.graphkit.density(g)

Returns the density of the directed part of the graph g.

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

the density of the directed part of the graph

Return type:

float

digonly

gunfolds.utils.graphkit.digonly(H)

Returns a subgraph of H contatining all directed edges of H

Parameters:

H (dictionary (gunfolds graph)) – gunfolds graph

Returns:

a subgraph of H contatining all directed edges of H

Return type:

dictionary (gunfolds graph)

edgelist

gunfolds.utils.graphkit.edgelist(g)

Returns a list of tuples for edges of g

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

a list of tuples for edges of g

Return type:

list of tuples

ensure_gcd1

gunfolds.utils.graphkit.ensure_gcd1(scc)

If scc’s loop structure is not gcd=1 pick a random node and add a self-loop

Parameters:

scc (dictionary (gunfolds graph)) – a strongly connected component

Returns:

a graph with gcd=1

Return type:

dictionary (gunfolds graph)

ensure_graph_gcd1

gunfolds.utils.graphkit.ensure_graph_gcd1(g, ignore_singletons=True)

This function takes any graph, breaks it into SCCs and make sure each SCC has a gcd of 1

Parameters:

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

• ignore_singletons (boolean) – ignores singleton SCCs when adding a self-loop to make gcd=1

Returns:

a graph with gcd=1

Return type:

dictionary (gunfolds graph)

fullyconnected

gunfolds.utils.graphkit.fullyconnected(n)

Returns a graph with all possible directed edges

Parameters:

n (integer) – number of nodes

Returns:

a graph with all possible directed edges

Return type:

dictionary(gunfolds graph)

gcd1_bp_mean_degree_graph

gunfolds.utils.graphkit.gcd1_bp_mean_degree_graph(node_num, degree, seed=None)

Returns a random graph with gcd=1

Parameters:

• node_num (integer) – number of nodes

• degree (float) – degree

• seed (integer) – random seed

Returns:

a random graph with gcd=1

Return type:

dictionary (gunfolds graph)

gcd4scc

gunfolds.utils.graphkit.gcd4scc(SCC)

Returns the greatest common divisor of the strongly connected component

Parameters:

SCC (dictionary (gunfolds graph)) – a strongly connected component

Returns:

the greatest common divisor of the strongly connected component

Return type:

integer

gtranspose

gunfolds.utils.graphkit.gtranspose(G)

Transpose (rev. edges of) G

Parameters:

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

Returns:

Transpose of given graph

Return type:

dictionary (gunfolds graph)

inbedgelist

gunfolds.utils.graphkit.inbedgelist(g)

Iterate over the list of tuples for edges of g

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

inedgelist

gunfolds.utils.graphkit.inedgelist(g)

Iterate over the list of tuples for edges of g

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

isdedgesubset

gunfolds.utils.graphkit.isdedgesubset(g2star, g2)

Checks if g2star directed edges are a subset of those of g2

Parameters:

• g2star (dictionary (gunfolds graph)) – gunfolds graph to be checked

• g2 (dictionary (gunfolds graph)) – gunfolds graph

Returns:

True, if g2star directed edges are a subset of those of g2 and vice versa

Return type:

boolean

isedgesubset

gunfolds.utils.graphkit.isedgesubset(g2star, g2)

Checks if all g2star edges are a subset of those of g2

Parameters:

• g2star (dictionary (gunfolds graph)) – gunfolds graph to be checked

• g2 (dictionary (gunfolds graph)) – gunfolds graph

Returns:

True, if all g2star edges are a subset of those of g2 and vice versa

Return type:

boolean

mean_degree_graph

gunfolds.utils.graphkit.mean_degree_graph(node_num, degree)

Generates a random graph with node_num, nodes and mean outgoing degree of degree.

Parameters:

• node_num (integer) – number of nodes

• degree (integer) – degree

Returns:

a random graph with mean outgoing degree of the given graph

Return type:

dictionary(gunfolds graph)

merge_graphs

gunfolds.utils.graphkit.merge_graphs(glist)

Merge a list of graphs at u=1 into a single new graph g

Parameters:

glist (list of dictionaries (gunfolds graphs)) – a list of graphs that are undersampled versions of the same system

Returns:

a new graph by merging a list of graphs at u=1

Return type:

dictionary (gunfolds graph)

merge_list

gunfolds.utils.graphkit.merge_list(glist)

Merge the graphs in the list

Parameters:

glist (list of dictionaries (gunfolds graphs)) – a list of graphs that are undersampled versions of the same system

Returns:

merged graph of a list

Return type:

dictionary(gunfolds graph)

no_children

gunfolds.utils.graphkit.no_children(g)

Checks if there exists a node that has no children in the given graph g.

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

True, if there exists a node with no children. False, otherwise.

Return type:

boolean

no_parents

gunfolds.utils.graphkit.no_parents(g)

Checks if there exists a node that has no parents in the given graph g.

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

True, if there exists a node with no parents. False, otherwise.

Return type:

boolean

OCE

gunfolds.utils.graphkit.OCE(g1, g2, normalized=False, undirected=False)

Return omission and comission errors for graphs.

Parameters:

• g1 (dictionary (gunfolds graph)) – the graph to check

• g2 (dictionary (gunfolds graph)) – the ground truth graph

• normalized (boolean) – If True, returns normalized error and vice versa

• undirected (boolean) – If True, returns undirected error and vice versa

Returns:

omission and comission errors for graphs

Return type:

dictionary

oerror

gunfolds.utils.graphkit.oerror(d)

Returns normalized omission error

Parameters:

d (dictionary) – calculated error

Returns:

normalized omission error

Return type:

float

pow_degree_graph

gunfolds.utils.graphkit.pow_degree_graph(node_num, degree)

Generates a graph by powerlaw sequence of degree constructed using the Havel-Hakimi algorithm.

Parameters:

• node_num (integer) – number of nodes

• degree (integer) – degree

Returns:

a graph constructed using the Havel-Hakimi algorithm.

Return type:

dictionary(gunfolds graph)

randH

gunfolds.utils.graphkit.randH(n, d1, d2)

Generate a random H with n nodes

Parameters:

• n (integer) – number of nodes

• d1 (integer) – number of additional edges to the ring

• d2 (integer) – (ask) number of random permutations

Returns:

a random graph with n nodes

Return type:

dictionary (gunfolds graph)

randomDAG

gunfolds.utils.graphkit.randomDAG(N, degree=5, connected=True)

Generates a random DAG

Parameters:

• N (integer) – number of nodes

• degree (integer) – degree

• connected (boolean) – If true, returns a connected DAG

Returns:

a random DAG

Return type:

NetworkX graph

randomTRIL

gunfolds.utils.graphkit.randomTRIL(N, degree=5, connected=False)

Generate a random triangular matrix

https://stackoverflow.com/a/56514463

Parameters:

• N (integer) – size of the matrix

• degree (integer) – degree

• connected (boolean) – (Ask)

Returns:

a random triangular adjacency matrix

Return type:

numpy array

remove_loop

gunfolds.utils.graphkit.remove_loop(G, dag)

Removes the loops from G according to dag

Parameters:

• G (NetworkX graph) – graph

• dag (NetworkX graph) – DAG

Returns:

graph with removed loop according to DAG

Return type:

NetworkX graph

remove_tril_singletons

gunfolds.utils.graphkit.remove_tril_singletons(T)

Ensure that the DAG resulting from this matrix will not have singleton nodes not connected to anything.

Parameters:

T (numpy array) – lower triangular matrix representing a DAG

Returns:

adjacency matrix where no singleton nodes are connected to anything

Return type:

numpy array

ring

gunfolds.utils.graphkit.ring(n)

Create a Ring Graph with n number of nodes

Parameters:

n (integer) – number of nodes

Returns:

a Ring Graph with n number of nodes

Return type:

dictionary (gunfolds graph)

ring_sccs

gunfolds.utils.graphkit.ring_sccs(num, num_sccs, dens=0.5, degree=3, max_cross_connections=3)

Generate a random graph with num_sccs SCCs, n-nodes each

Parameters:

• num (integer) – number of nodes in each sec

• num_sccs (integer) – number of secs

• dens (float) – density of each sac

• degree (integer) – degree of the connecting DAG

• max_cross_connections (integer) – maximum number of connections per each edge in DAG

Returns:

a random graph with num_sccs SCCs, n-nodes each

Return type:

dictionary (gunfolds graph)

ringarcs

gunfolds.utils.graphkit.ringarcs(g, n)

(Ask)

Parameters:

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

• n (integer) – (ask)

Returns:

Return type:

dictionary (gunfolds graph)

ringmore

gunfolds.utils.graphkit.ringmore(n, m)

Returns a n node ring graph with m additional edges

Parameters:

• n (integer) – number of nodes

• m (integer) – number of additional edges

Returns:

a n node ring graph with m additional edges

Return type:

dictionary (gunfolds graph)

scale_free

gunfolds.utils.graphkit.scale_free(n, alpha=0.7, beta=0.25, delta_in=0.2, delta_out=0.2)

(Copied from scale_free function in networkx should i need to add any citation)

Parameters:

• n (integer) – number of nodes

• alpha (float) – probability for adding a new node connected to an existing node

• beta (float) – probability for adding an edge between two existing nodes.

• delta_in (float) – bias for choosing nodes from in-degree

• delta_out (float) – bias for choosing nodes from out-degree distribution.

Returns:

Return type:

scc_unreachable

gunfolds.utils.graphkit.scc_unreachable(g)

Checks if there exists a strongly connected component in the given graph g that is unreachable.

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

True, if there exists SCC that is unreachable. False, otherwise.

Return type:

boolean

selfloop

gunfolds.utils.graphkit.selfloop(n, g)

Checks if g has a self loop at node n

Parameters:

• n (integer) – node

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

Returns:

True if g has a self loop at node n and vice versa

Return type:

boolean

shift_labels

gunfolds.utils.graphkit.shift_labels(g, shift)

Returns same graph with shifted labels

Parameters:

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

• shift (integer) – number of vertices to be shifted

Returns:

same graph with shifted labels

Return type:

dictionary(gunfolds graph)

shift_list_labels

gunfolds.utils.graphkit.shift_list_labels(glist)

Shifts the labels for a list of graphs

Parameters:

glist (list of dictionaries (gunfolds graphs)) – a list of graphs that are undersampled versions of the same system

Returns:

shifted list of graphs

Return type:

list

subgraph

gunfolds.utils.graphkit.subgraph(g, nodes)

Returns a subgraph of g that consists of nodes and their interconnections.

Parameters:

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

• nodes (list) – integer valued nodes to include

Returns:

a subgraph of g that consists of nodes and their interconnections.

Return type:

dictionary(gunfolds graph)

superclique

gunfolds.utils.graphkit.superclique(n)

Returns a Graph with all possible edges

Parameters:

n (integer) – number of nodes

Returns:

a Graph with all possible edges

Return type:

dictionary (gunfolds graph)

udensity

gunfolds.utils.graphkit.udensity(g)

Returns the density of a undersampled graph that simultaneously accounts for directed and bidirected edges of g.

Parameters:

g (dictionary (gunfolds graph)) – gunfolds graph

Returns:

the density of the given undersampled graph

Return type:

float

undedgelist

gunfolds.utils.graphkit.undedgelist(g, exclude_bi=False)

Returns a list of tuples for undirected edges of g with nodes sorted in ascending order.

Parameters:

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

• exclude_bi (boolean) – if True, only converts directed edges to undirected edges. If False, converts directed and bidirected edges to undirected edges

Returns:

a list of tuples for undirected edges of g with nodes sorted in ascending order

Return type:

list

upairs

gunfolds.utils.graphkit.upairs(n, k)

Returns n unique nonsequential pairs

Parameters:

• n (integer) – (ask)

• k (integer) – (ask)

Returns:

n unique nonsequential pairs

Return type:

list

update_graph

gunfolds.utils.graphkit.update_graph(g, g2)

Update g with connections (or nodes) from g2. Both must be at u=1

Parameters:

• g (dictionary (gunfolds graph)) – graph to be updated

• g2 (dictionary (gunfolds graph)) – reference graph

Returns:

updated g with respect to g2

Return type:

dictionary (gunfolds graph)