Graphs

Graph

class numpy_ml.utils.graphs.Graph(V, E)

get_index(v)

Get the internal index for a given vetex

get_vertex(v_i)

Get the original vertex from a given internal index

vertices

indices

edges

get_neighbors(v_i)

Return the internal indices of the vertices reachable from the vertex with index v_i.

to_matrix()

Return an adjacency matrix representation of the graph

to_adj_dict()

Return an adjacency dictionary representation of the graph

path_exists(s_i, e_i)

Check whether a path exists from vertex index s_i to e_i.

Parameters:

• s_i (Int) – The interal index of the start vertex
• e_i (Int) – The internal index of the end vertex

Returns:

path_exists (Boolean) – Whether or not a valid path exists between s_i and e_i.

all_paths(s_i, e_i)

Find all simple paths between s_i and e_i in the graph.

Notes

Uses breadth-first search. Ignores all paths with repeated vertices.

Parameters:

• s_i (Int) – The interal index of the start vertex
• e_i (Int) – The internal index of the end vertex

Returns:

complete_paths (list of lists) – A list of all paths from s_i to e_i. Each path is represented as a list of interal vertex indices.

Edge

class numpy_ml.utils.graphs.Edge(fr, to, w=None)

A generic directed edge object.

Parameters:

• fr (int) – The id of the vertex the edge goes from
• to (int) – The id of the vertex the edge goes to
• w (float, Object instance, or None) – The edge weight, if applicable. If weight is an arbitrary Object it must have a method called ‘sample’ which takes no arguments and returns a random sample from the weight distribution. If w is None, no weight is assumed. Default is None.

weight

reverse()

Reverse the edge direction

DiGraph

class numpy_ml.utils.graphs.DiGraph(V, E)

Bases: numpy_ml.utils.graphs.Graph

A generic directed graph object.

Parameters:

• V (list) – A list of vertex IDs.
• E (list of Edge objects) – A list of directed edges connecting pairs of vertices in V.

reverse()

Reverse the direction of all edges in the graph

topological_ordering()

Returns a (non-unique) topological sort / linearization of the nodes IFF the graph is acyclic, otherwise returns None.

Notes

A topological sort is an ordering on the nodes in G such that for every directed edge \(u \rightarrow v\) in the graph, u appears before v in the ordering. The topological ordering is produced by ordering the nodes in G by their DFS “last visit time,” from greatest to smallest.

This implementation follows a recursive, DFS-based approach [1] which may break if the graph is very large. For an iterative version, see Khan’s algorithm [2] .

References

[1]	Tarjan, R. (1976), Edge-disjoint spanning trees and depth-first search, Acta Informatica, 6 (2): 171–185.

[2]	Kahn, A. (1962), Topological sorting of large networks, Communications of the ACM, 5 (11): 558–562.

Returns:ordering (list or None) – A topoligical ordering of the vertex indices if the graph is a DAG, otherwise None.

is_acyclic()

Check whether the graph contains cycles

UndirectedGraph

class numpy_ml.utils.graphs.UndirectedGraph(V, E)

Bases: numpy_ml.utils.graphs.Graph

A generic undirected graph object.

Parameters:

• V (list) – A list of vertex IDs.
• E (list of Edge objects) – A list of edges connecting pairs of vertices in V. For any edge connecting vertex u to vertex v, UndirectedGraph will assume that there exists a corresponding edge connecting v to u, even if this is not present in E.

random_unweighted_graph

numpy_ml.utils.graphs.random_unweighted_graph(n_vertices, edge_prob=0.5, directed=False)

Generate an unweighted Erdős-Rényi random graph [*].

References

[*]	Erdős, P. and Rényi, A. (1959). On Random Graphs, Publ. Math. 6, 290.

Parameters:

• n_vertices (int) – The number of vertices in the graph.
• edge_prob (float in [0, 1]) – The probability of forming an edge between two vertices. Default is 0.5.
• directed (bool) – Whether the edges in the graph should be directed. Default is False.

Returns:

G (Graph instance) – The resulting random graph.

random_DAG

numpy_ml.utils.graphs.random_DAG(n_vertices, edge_prob=0.5)

Create a ‘random’ unweighted directed acyclic graph by pruning all the backward connections from a random graph.

Parameters:

• n_vertices (int) – The number of vertices in the graph.
• edge_prob (float in [0, 1]) – The probability of forming an edge between two vertices in the underlying random graph, before edge pruning. Default is 0.5.

Returns:

G (Graph instance) – The resulting DAG.