Graph utilities

adjacency2graph

Takes an adjacency list, dict, or matrix and returns a graph.

generate_random_graph

Creates a random graph where the edges have different types.

generate_pagerank_graph

Creates a random graph where the vertex types are selected using their pagerank.

generate_transition_matrix

Generates a random transition matrix for the graph g.

graph2dict

Takes a graph and returns an adjacency list.

minimal_random_graph

Creates a connected graph with random vertex locations.

set_types_rank

Creates a stylized graph.

set_types_random

Randomly sets edge_type (edge type) properties of the graph.

QueueNetworkDiGraph

A directed graph class built to work with a QueueNetwork

QueueingToolError

Base class for exceptions in Queueing-tool.

class queueing_tool.graph.QueueNetworkDiGraph(data=None, **kwargs)[source]

Bases: DiGraph

A directed graph class built to work with a QueueNetwork

If data is a dict then adjacency2graph() is called first.

Parameters:
datanetworkx.DiGraph, numpy.ndarray, dict, etc.

Any object that networkx can turn into a DiGraph.

kwargs

Any additional arguments for networkx.DiGraph.

Notes

Not suitable for stand alone use; only use with a QueueNetwork.

Attributes:
posndarray or None

An (V, 2) array for the position for each vertex (V is the number of vertices). By default this is None.

edge_colorndarray or None

An (E, 4) array for the RGBA colors for each edge. (E is the number of edges). By default this is None.

vertex_colorndarray or None

An (V, 4) array for the RGBA colors for each vertex border. By default this is None.

vertex_fill_colorndarray or None

An (V, 4) array for the RGBA colors for the body of each vertex. By default this is None.

add_edge(*args, **kwargs)[source]

Add an edge between u and v.

The nodes u and v will be automatically added if they are not already in the graph.

Edge attributes can be specified with keywords or by directly accessing the edge’s attribute dictionary. See examples below.

Parameters:
u_of_edge, v_of_edgenodes

Nodes can be, for example, strings or numbers. Nodes must be hashable (and not None) Python objects.

attrkeyword arguments, optional

Edge data (or labels or objects) can be assigned using keyword arguments.

See also

add_edges_from

add a collection of edges

Notes

Adding an edge that already exists updates the edge data.

Many NetworkX algorithms designed for weighted graphs use an edge attribute (by default weight) to hold a numerical value.

Examples

The following all add the edge e=(1, 2) to graph G:

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> e = (1, 2)
>>> G.add_edge(1, 2)  # explicit two-node form
>>> G.add_edge(*e)  # single edge as tuple of two nodes
>>> G.add_edges_from([(1, 2)])  # add edges from iterable container

Associate data to edges using keywords:

>>> G.add_edge(1, 2, weight=3)
>>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)

For non-string attribute keys, use subscript notation.

>>> G.add_edge(1, 2)
>>> G[1][2].update({0: 5})
>>> G.edges[1, 2].update({0: 5})
draw_graph(line_kwargs=None, scatter_kwargs=None, **kwargs)[source]

Draws the graph.

Uses matplotlib, specifically LineCollection and scatter(). Gets the default keyword arguments for both methods by calling lines_scatter_args() first.

Parameters:
line_kwargsdict (optional, default: None)

Any keyword arguments accepted by LineCollection

scatter_kwargsdict (optional, default: None)

Any keyword arguments accepted by scatter().

bgcolorlist (optional, keyword only)

A list with 4 floats representing a RGBA color. Defaults to [1, 1, 1, 1].

figsizetuple (optional, keyword only, default: (7, 7))

The width and height of the figure in inches.

kwargs

Any keyword arguments used by savefig().

Raises:
ImportError

If Matplotlib is not installed then an ImportError is raised.

Notes

If the fname keyword is passed, then the figure is saved locally.

get_edge_type(edge_type)[source]

Returns all edges with the specified edge type.

Parameters:
edge_typeint

An integer specifying what type of edges to return.

Returns:
outlist of 2-tuples

A list of 2-tuples representing the edges in the graph with the specified edge type.

Examples

Lets get type 2 edges from the following graph

>>> import queueing_tool as qt
>>> adjacency = {
...     0: {1: {'edge_type': 2}},
...     1: {2: {'edge_type': 1},
...         3: {'edge_type': 4}},
...     2: {0: {'edge_type': 2}},
...     3: {3: {'edge_type': 0}}
... }
>>> G = qt.QueueNetworkDiGraph(adjacency)
>>> ans = G.get_edge_type(2)
>>> ans.sort()
>>> ans
[(0, 1), (2, 0)]
lines_scatter_args(line_kwargs=None, scatter_kwargs=None, pos=None)[source]

Returns the arguments used when plotting.

Takes any keyword arguments for LineCollection and scatter() and returns two dictionaries with all the defaults set.

Parameters:
line_kwargsdict (optional, default: None)

Any keyword arguments accepted by LineCollection.

scatter_kwargsdict (optional, default: None)

Any keyword arguments accepted by scatter().

Returns:
tuple

A 2-tuple of dicts. The first entry is the keyword arguments for LineCollection and the second is the keyword args for scatter().

Notes

If a specific keyword argument is not passed then the defaults are used.

Graph generation

queueing_tool.graph.adjacency2graph(adjacency, edge_type=None, adjust=1, **kwargs)[source]

Takes an adjacency list, dict, or matrix and returns a graph.

The purpose of this function is take an adjacency list (or matrix) and return a QueueNetworkDiGraph that can be used with a QueueNetwork instance. The Graph returned has the edge_type edge property set for each edge. Note that the graph may be altered.

Parameters:
adjacencydict or ndarray

An adjacency list as either a dict, or an adjacency matrix.

adjustint {1, 2} (optional, default: 1)

Specifies what to do when the graph has terminal vertices (nodes with no out-edges). Note that if adjust is not 2 then it is assumed to be 1. There are two choices:

  • adjust = 1: A loop is added to each terminal node in the graph, and their edge_type of that loop is set to 0.

  • adjust = 2: All edges leading to terminal nodes have their edge_type set to 0.

**kwargs

Unused.

Returns:
outnetworkx.DiGraph

A directed graph with the edge_type edge property.

Raises:
TypeError

Is raised if adjacency is not a dict or ndarray.

Examples

If terminal nodes are such that all in-edges have edge type 0 then nothing is changed. However, if a node is a terminal node then a loop is added with edge type 0.

>>> import queueing_tool as qt
>>> adj = {
...     0: {1: {}},
...     1: {2: {},
...         3: {}},
...     3: {0: {}}}
>>> eTy = {0: {1: 1}, 1: {2: 2, 3: 4}, 3: {0: 1}}
>>> # A loop will be added to vertex 2
>>> g = qt.adjacency2graph(adj, edge_type=eTy)
>>> ans = qt.graph2dict(g)
>>> sorted(ans.items())     
[(0, {1: {'edge_type': 1}}),
 (1, {2: {'edge_type': 2}, 3: {'edge_type': 4}}), 
 (2, {2: {'edge_type': 0}}),
 (3, {0: {'edge_type': 1}})]

You can use a dict of lists to represent the adjacency list.

>>> adj = {0 : [1], 1: [2, 3], 3: [0]}
>>> g = qt.adjacency2graph(adj, edge_type=eTy)
>>> ans = qt.graph2dict(g)
>>> sorted(ans.items())     
[(0, {1: {'edge_type': 1}}),
 (1, {2: {'edge_type': 2}, 3: {'edge_type': 4}}),
 (2, {2: {'edge_type': 0}}),
 (3, {0: {'edge_type': 1}})]

Alternatively, you could have this function adjust the edges that lead to terminal vertices by changing their edge type to 0:

>>> # The graph is unaltered
>>> g = qt.adjacency2graph(adj, edge_type=eTy, adjust=2)
>>> ans = qt.graph2dict(g)
>>> sorted(ans.items())     
[(0, {1: {'edge_type': 1}}),
 (1, {2: {'edge_type': 0}, 3: {'edge_type': 4}}),
 (2, {}),
 (3, {0: {'edge_type': 1}})]
queueing_tool.graph.generate_random_graph(num_vertices=250, prob_loop=0.5, **kwargs)[source]

Creates a random graph where the edges have different types.

This method calls minimal_random_graph(), and then adds a loop to each vertex with prob_loop probability. It then calls set_types_random() on the resulting graph.

Parameters:
num_verticesint (optional, default: 250)

The number of vertices in the graph.

prob_loopfloat (optional, default: 0.5)

The probability that a loop gets added to a vertex.

**kwargs

Any parameters to send to minimal_random_graph() or set_types_random().

Returns:
QueueNetworkDiGraph

A graph with the position of the vertex set as a property. The position property is called pos. Also, the edge_type edge property is set for each edge.

Examples

The following generates a directed graph with 50 vertices where half the edges are type 1 and 1/4th are type 2 and 1/4th are type 3:

>>> import queueing_tool as qt
>>> pTypes = {1: 0.5, 2: 0.25, 3: 0.25}
>>> g = qt.generate_random_graph(100, proportions=pTypes, seed=17)
>>> non_loops = [e for e in g.edges() if e[0] != e[1]]
>>> p1 = np.sum([g.ep(e, 'edge_type') == 1 for e in non_loops])
>>> float(p1) / len(non_loops) 
0.486...
>>> p2 = np.sum([g.ep(e, 'edge_type') == 2 for e in non_loops])
>>> float(p2) / len(non_loops) 
0.249...
>>> p3 = np.sum([g.ep(e, 'edge_type') == 3 for e in non_loops])
>>> float(p3) / len(non_loops) 
0.264...

To make an undirected graph with 25 vertices where there are 4 different edge types with random proportions:

>>> p = np.random.rand(4)
>>> p = p / sum(p)
>>> p = {k + 1: p[k] for k in range(4)}
>>> g = qt.generate_random_graph(num_vertices=25, is_directed=False, proportions=p)

Note that none of the edge types in the above example are 0. It is recommended use edge type indices starting at 1, since 0 is typically used for terminal edges.

queueing_tool.graph.generate_pagerank_graph(num_vertices=250, **kwargs)[source]

Creates a random graph where the vertex types are selected using their pagerank.

Calls minimal_random_graph() and then set_types_rank() where the rank keyword argument is given by networkx.pagerank().

Parameters:
num_verticesint (optional, the default is 250)

The number of vertices in the graph.

**kwargs

Any parameters to send to minimal_random_graph() or set_types_rank().

Returns:
QueueNetworkDiGraph

A graph with a pos vertex property and the edge_type edge property.

Notes

This function sets the edge types of a graph to be either 1, 2, or 3. It sets the vertices to type 2 by selecting the top pType2 * g.number_of_nodes() vertices given by the pagerank() of the graph. A loop is added to all vertices identified this way (if one does not exist already). It then randomly sets vertices close to the type 2 vertices as type 3, and adds loops to these vertices as well. These loops then have edge types that correspond to the vertices type. The rest of the edges are set to type 1.

queueing_tool.graph.generate_transition_matrix(g, seed=None)[source]

Generates a random transition matrix for the graph g.

Parameters:
gnetworkx.DiGraph, numpy.ndarray, dict, etc.

Any object that DiGraph accepts.

seedint (optional)

An integer used to initialize numpy’s psuedo-random number generator.

Returns:
matndarray

Returns a transition matrix where mat[i, j] is the probability of transitioning from vertex i to vertex j. If there is no edge connecting vertex i to vertex j then mat[i, j] = 0.

queueing_tool.graph.minimal_random_graph(num_vertices, seed=None, **kwargs)[source]

Creates a connected graph with random vertex locations.

Parameters:
num_verticesint

The number of vertices in the graph.

seedint (optional)

An integer used to initialize numpy’s psuedorandom number generators.

**kwargs

Unused.

Returns:
QueueNetworkDiGraph

A graph with a pos vertex property for each vertex’s position.

Notes

This function first places num_vertices points in the unit square randomly (using the uniform distribution). Then, for every vertex v, all other vertices with Euclidean distance less or equal to r are connect by an edge — where r is the smallest number such that the graph ends up connected.

queueing_tool.graph.set_types_rank(g, rank, pType2=0.1, pType3=0.1, seed=None, **kwargs)[source]

Creates a stylized graph. Sets edge and types using pagerank.

This function sets the edge types of a graph to be either 1, 2, or 3. It sets the vertices to type 2 by selecting the top pType2 * g.number_of_nodes() vertices given by the pagerank() of the graph. A loop is added to all vertices identified this way (if one does not exist already). It then randomly sets vertices close to the type 2 vertices as type 3, and adds loops to these vertices as well. These loops then have edge types the correspond to the vertices type. The rest of the edges are set to type 1.

Parameters:
gnetworkx.DiGraph, ndarray, dict, etc.

Any object that DiGraph accepts.

ranknumpy.ndarray

An ordering of the vertices.

pType2float (optional, default: 0.1)

Specifies the proportion of vertices that will be of type 2.

pType3float (optional, default: 0.1)

Specifies the proportion of vertices that will be of type 3 and that are near pType2 vertices.

seedint (optional)

An integer used to initialize numpy’s psuedo-random number generator.

**kwargs

Unused.

Returns:
QueueNetworkDiGraph

Returns the a graph with an edge_type edge property.

Raises:
TypeError

Raised when the parameter g is not of a type that can be made into a DiGraph.

queueing_tool.graph.set_types_random(g, proportions=None, loop_proportions=None, seed=None, **kwargs)[source]

Randomly sets edge_type (edge type) properties of the graph.

This function randomly assigns each edge a type. The probability of an edge being a specific type is proscribed in the proportions, loop_proportions variables.

Parameters:
gnetworkx.DiGraph, numpy.ndarray, dict, etc.

Any object that DiGraph accepts.

proportionsdict (optional, default: {k: 0.25 for k in range(1, 4)})

A dictionary of edge types and proportions, where the keys are the types and the values are the proportion of non-loop edges that are expected to be of that type. The values can must sum to one.

loop_proportionsdict (optional, default: {k: 0.25 for k in range(4)})

A dictionary of edge types and proportions, where the keys are the types and the values are the proportion of loop edges that are expected to be of that type. The values can must sum to one.

seedint (optional)

An integer used to initialize numpy’s psuedorandom number generator.

**kwargs

Unused.

Returns:
QueueNetworkDiGraph

Returns the a graph with an edge_type edge property.

Raises:
TypeError

Raised when the parameter g is not of a type that can be made into a networkx.DiGraph.

ValueError

Raises a ValueError if the pType values do not sum to one.

Notes

If pTypes is not explicitly specified in the arguments, then it defaults to four types in the graph (types 0, 1, 2, and 3). It sets non-loop edges to be either 1, 2, or 3 33% chance, and loops are types 0, 1, 2, 3 with 25% chance.

Miscellaneous functions

queueing_tool.graph.graph2dict(g, return_dict_of_dict=True)[source]

Takes a graph and returns an adjacency list.

Parameters:
gnetworkx.DiGraph, networkx.Graph, etc.

Any object that networkx can turn into a DiGraph.

return_dict_of_dictbool (optional, default: True)

Specifies whether this function will return a dict of dicts or a dict of lists.

Returns:
adjdict

An adjacency representation of graph as a dictionary of dictionaries, where a key is the vertex index for a vertex v and the values are dicts with keys for the vertex index and values as edge properties.

Examples

>>> import queueing_tool as qt
>>> import networkx as nx
>>> adj = {0: [1, 2], 1: [0], 2: [0, 3], 3: [2]}
>>> g = nx.DiGraph(adj)
>>> qt.graph2dict(g, return_dict_of_dict=True)
...  
{0: {1: {}, 2: {}},
1: {0: {}},
2: {0: {}, 3: {}},
3: {2: {}}}
>>> qt.graph2dict(g, return_dict_of_dict=False)
{0: [1, 2], 1: [0], 2: [0, 3], 3: [2]}

Exceptions

exception queueing_tool.network.QueueingToolError[source]

Base class for exceptions in Queueing-tool.