API

The TinyGraph object

class tinygraph.TinyGraph(vert_N, adj_type=<class 'numpy.float32'>, vp_types={}, ep_types={})

TinyGraph is centered around our representation of graphs through numpy arrays using the class TinyGraph. The central feature is the adjacency matrix, which defines the graph stucture under the assumption that we are using undirected, weighted graphs without self-loops. Each graph also has a set of vertex properties and a set of edge properties. We will also use numpy arrays to store the properties at each vertex or edge.

add_edge_prop(name, dtype)

Add the edge property named ‘name’ to the graph.

Inputs:

name (str): property name dtype (class): numpy dtype of property

Outputs:

None

add_vert_prop(name, dtype)

Add the vertex property named ‘name’ to the graph.

Inputs:

name (str): property name dtype (class): numpy dtype of property

Outputs:

None

add_vertex(props={}, **kwargs)

Add a vertex to a TinyGraph instance. This process can be slow because it requires reshaping the adjacency and property arrays. The new vertex will have the highest index (vert_N - 1).

Inputs:

properties are passed as key=value pairs or as a props dictionary

If a key is not recognized, it will raise an error If a key is missing, the corresponding value will be left as 0 for whatever the corresponding dtype is

Outputs:

None - modifications are made in place.

copy()

Get a copy of the TinyGraph instance.

Inputs:

None

Outputs:

new_graph (TinyGraph): Deep copy of TinyGraph instance.

edges(weight=False, edge_props=None)

Get a list of the edges by endpoint vertices, optionally with their weight and some properties.

Inputs:

weight (bool): Whether to return the weight of each edge. By default

this if false and the weight is not returned.

edge_props ([str]): A list of edge properties to return, by name.

By default this is empty and no properties are returned. Must be a list of existing properties.

Outputs:

edges ([edge]): A list of edges, where each edge is represented by a

tuple. The first two elements of the tuple are the endpoints of the edge. If weights is true, the third element is the weight of the edge. If edge_props is not empty, a dictionary mapping the properties provided to the value for the edge is the final element of the tuple.

get_edge_props(n1, n2, edge_props=None)

Get the properties at a given edge.

Inputs:

n1 (int): Endpoint vertex 1 of edge to get properties of. n2 (int): Endpoint vertex 2 of edge to get properties of. edge_props ([str]): A list of the edge properties to return, by

name.

Outputs:

props (str:prop_type): A dictionary mapping each of the edge

property names to the property at the input edge.

get_neighbors(n)

Get the neighbors of a vertex.

Inputs:

n (int): The vertex to get the neighbors of.

Outputs:

neighbors ([int]): A list of the neighbor vertices.

get_vert_props(n, vert_props=None)

Get the properties at a given vertex.

Inputs:

n (int): Vertex to get properties of. vert_props ([str]): A list of the vertex properties to return, by

name.

Outputs:

props (str:prop_type): A dictionary mapping each of the vertex

property names to the property at the input vertex.

print_full_graph()

Full representation of a graph. Includes all global, vertex and edge properties.

Inputs:

None

Outputs:

None - prints representation.

remove_edge_prop(name)

Removes the indicated edge property from the graph

Inputs:

name (str): the name of the property

Outputs:

None

remove_vert_prop(name)

Removes the indicated vertex property from the graph

Inputs:

name (str): the name of the property

Outputs:

None

remove_vertex(n)

Remove a vertex from a TinyGraph instance. This process can be slow because it requires reshaping the adjacency and property arrays. Moves up the vertices after n so that the numbering remains dense.

Inputs:

n (int): Vertex to remove. Vertices are indexed numerically

(0…vert_N-1).

Outputs:

None - modifications are made in place.

vertices(vert_props=[])

Get a list of the vertices with some of their properties.

Inputs:

vert_props ([str]): A list of vertex properties to return, by name.

By default this is empty and an empty map is returned. Must be a list of existing properties.

Outputs:

vertices ([vertex]): A list of vertices, where each vertex is

represented by a tuple. The first element of the tuple is the vertex index. The second element is a map from the provided vertex properties to the values at the vertex. Even when no properties are provided, a map is returned, since the list of vertices is simply 0…N-1, which can be retrieved more efficiently in other ways.

IO operations

tinygraph.io.basic.from_binary(fileobj)

Load TinyGraph from binary representation. Note there is minimal sanity checking here for speed.

Input:

fileobj: Python file-like object to load from.

Returns:

tg (TinyGraph): saved TinyGraph instance

tinygraph.io.basic.from_nx(ng, adj_type=<class 'numpy.float32'>, weight_prop=None, name_prop=None, vp_types={}, ep_types={}, raise_error_on_missing_prop=True)

Initialize a TinyGraph instance from a networkx graph instance. Grabs only the requested vertex and edge properties. If weight_prop is set, then the adjacency matrix will contain values from edges’ weight property.

Inputs:

ng (networkx Graph):

Graph to translate to TinyGraph.

adj_type:

the adjacency type to expect (for TinyGraph creation).

weight_prop:

Name of the weight property in the networkx graph (put in adj matrix). If None, value defaults to 1.

name_prop:

vertex property to put the networkx node name into (e.g., ‘name’). None results in discarding the vertex name.

vp_types (dictionary of prop(string)->type):

vertex properties to grab (and how much space to allocate).

ep_types (dictionary of prop(string)->type):

edge properties to grab (and how much space to allocate).

raise_error_on_missing_prop (bool):

In case properties aren’t found, we raise a KeyError by default. Setting raise_error_on_missing_prop to false would result in quietly filling in values.

Outputs:

tg (TinyGraph): TinyGraph instance corresponding to networkx graph.

tinygraph.io.basic.to_binary(g, fileobj)

Convert tiny graph to fast binary representation for storage. Note this is just a compressed npz from numpy with some help around attribute names. Note that per-graph properties are serialized as a json string. Inputs:

tg (TinyGraph): TinyGraph instance. fileobj: Python file-like object to save to.

Returns:

None

tinygraph.io.basic.to_nx(g, weight_prop=None, name_prop=None, vp_subset=None, ep_subset=None)

Get a networkx copy of the current graph. Grabs all the properties it can find and uses the node_names property for node names.

Inputs:

tg (TinyGraph): graph to translate to networkx. weight_prop (str):

key to put the adjacency matrix values into (None to interpret as unweighted).

name_prop (str):

vertex property from g to take as the node name (e.g. ‘name’). If None is supplied, the name will be the vertex number. If an invalid string (not a key of g.v) is passed, a KeyError will be raised.

vp_subset ([str]):

Vertex properties to take; None to take all. A KeyError will be raised if not all are found.

ep_subset ([str]):

Edge properties to take; None to take all. A KeyError will be raised if not all are found.

Outputs:

g (networkx Graph): networkx graph of TinyGraph instance.

Algorithms

tinygraph.algorithms.get_connected_components()

Get a list of the connected components in the TinyGraph instance.

Inputs:

tg (TinyGraph): graph to find components of.

Outputs:

cc ([{int}]): A list of connected components of tg, where each connected

component is given by a set of the vertices in the component.

tinygraph.algorithms.get_min_cycles(tg)

Determines if a vertex in a graph is part of a cycle, and if so, returns the minimum sized such cycle (by number of vertices).

Inputs:

tg (TinyGraph): graph to find cycles in.

Outputs:

cycle ([{int}]): A list of the minimum length cycle (by number of

vertices) for each vertex in tg. Cycles are represented by a set of the vertices in the cycle, and the list is order by vertex (cycle[0] is min cycle that includes vertex 0).

tinygraph.algorithms.get_shortest_paths()

Get the distance from each vertex to each other vertex on the shortest path. Uses Floyd-Warshall to calculate the distances of the shortest paths.

Inputs:

tg (TinyGraph): The graph to find the shortest paths in. weighted (bool): Whether to consider the weights of the edges, or to

consider only the lengths of the path. If weighted is true, the distance of a path is calculated by the sum of the weights on the path. If false, the distance is calculated by the number of vertices on the path.

paths (bool): Whether to also return the matrix of next steps in the paths,

which is an NxN matrix describing which node to move to next to take the shortest path from the current node to the target node. This can be used to reconstruct the path that is the shortest path between two nodes.

Outputs:

distances ([[int]]): A list of the distance to each vertex. The lists are

ordered by vertex number, so distances[0] is a list of the distances from vertex 0 to the other vertices (e.g. distances[0][3] = distance from vertex 0 to vertex 3 shortest path from 0 to 3; distances[2][2] = 0 is distance from vertex 2 to itself). If no path exists between the vertices, the result is None.

tinygraph.algorithms.is_connected(tg)

Determines if a graph is fully connected.

Inputs:

tg (TinyGraph): graph to check for connectedness.

Outputs:

connected (bool): whether the graph is fully connected.

Utilities

tinygraph.util.graph_equality(g1, g2)

Naive check for equality between two graphs. Note that this just directly compares adj matrices and the the like. This does NOT CHECK FOR ISOMORPHISM.

Inputs:

g1 (TinyGraph): First graph instance. g2 (TinyGraph): Second graph instance.

Outputs:

equal (bool): Are the two graph instances equal to each other.

tinygraph.util.merge(g1, g2)

Produces a new graph resulting from taking the (disjoint) superset of vertices in g1 and g2. Raises a TypeError in case the adjacency matrices are of different dtypes. Raises a warning in case the vertex or edge properties are different. Combines the graph properties, but in case of key collision favors g1’s value.

Inputs:

g1 (TinyGraph): Original TinyGraph - global graph properties precedence. g2 (TinyGraph): Other original TinyGraph.

Output:

new_g (TinyGraph): result of the merge. Note: data is detached from any

data living within g1 or g2.

tinygraph.util.permute(g, perm)

Permute the vertices of a graph to create a new TinyGraph instance.

Inputs:

g (TinyGraph): Original TinyGraph to permute. perm (iterable): A mapping from old vertices to new vertices, such that

perm[old_vertex] = new_vertex.

Outputs:

new_g (TinyGraph): A new TinyGraph instance with each vertex, and its

corresponding vertex and edge properties, permuted.

tinygraph.util.subgraph(g, vertices)

Returns induced subgraph of g on vertices in vert_list. Grabs all the relevant properties as well. Raises an index error in case of invalid vertices in vert_list.

Inputs:

g (TinyGraph): Original TinyGraph. vertices (iterable): iterable of indices of vertices to take

as the vertices of the subgraph.

Output:

sg (TinyGraph): induced subgraph.