# Graphs¶

## Graph¶

class numpy_ml.utils.graphs.Graph(V, E)[source]
get_index(v)[source]

Get the internal index for a given vetex

get_vertex(v_i)[source]

Get the original vertex from a given internal index

vertices[source]
indices[source]
edges[source]
get_neighbors(v_i)[source]

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

to_matrix()[source]

Return an adjacency matrix representation of the graph

to_adj_dict()[source]

Return an adjacency dictionary representation of the graph

path_exists(s_i, e_i)[source]

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 path_exists (Boolean) – Whether or not a valid path exists between s_i and e_i.
all_paths(s_i, e_i)[source]

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 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)[source]

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[source]
reverse()[source]

Reverse the edge direction

## DiGraph¶

class numpy_ml.utils.graphs.DiGraph(V, E)[source]

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()[source]

Reverse the direction of all edges in the graph

topological_ordering()[source]

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  which may break if the graph is very large. For an iterative version, see Khan’s algorithm  .

References

  Tarjan, R. (1976), Edge-disjoint spanning trees and depth-first search, Acta Informatica, 6 (2): 171–185.
  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()[source]

Check whether the graph contains cycles

## UndirectedGraph¶

class numpy_ml.utils.graphs.UndirectedGraph(V, E)[source]

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)[source]

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. G (Graph instance) – The resulting random graph.

## random_DAG¶

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

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. G (Graph instance) – The resulting DAG.