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 Queueingtool. 

class
queueing_tool.graph.
QueueNetworkDiGraph
(data=None, **kwargs)[source]¶ Bases:
networkx.classes.digraph.DiGraph
A directed graph class built to work with a
QueueNetwork
If data is a dict then
adjacency2graph()
is called first.Parameters: data :
networkx.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
pos ( ndarray
orNone
) An(V, 2)
array for the position for each vertex (V
is the number of vertices). By default this isNone
.edge_color ( ndarray
orNone
) An(E, 4)
array for the RGBA colors for each edge. (E
is the number of edges). By default this isNone
.vertex_color ( ndarray
orNone
) An(V, 4)
array for the RGBA colors for each vertex border. By default this isNone
.vertex_fill_color ( ndarray
orNone
) An(V, 4)
array for the RGBA colors for the body of each vertex. By default this isNone
.
draw_graph
(line_kwargs=None, scatter_kwargs=None, **kwargs)[source]¶ Draws the graph.
Uses matplotlib, specifically
LineCollection
andscatter()
. Gets the default keyword arguments for both methods by callinglines_scatter_args()
first.Parameters: line_kwargs : dict (optional, default:
None
)Any keyword arguments accepted by
LineCollection
scatter_kwargs : dict (optional, default:
None
)Any keyword arguments accepted by
scatter()
.bgcolor : list (optional, keyword only)
A list with 4 floats representing a RGBA color. Defaults to
[1, 1, 1, 1]
.figsize : tuple (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_type : int
An integer specifying what type of edges to return.
Returns: out : list of 2tuples
A list of 2tuples 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
andscatter()
and returns two dictionaries with all the defaults set.Parameters: line_kwargs : dict (optional, default:
None
)Any keyword arguments accepted by
LineCollection
.scatter_kwargs : dict (optional, default:
None
)Any keyword arguments accepted by
scatter()
.Returns: tuple
A 2tuple of dicts. The first entry is the keyword arguments for
LineCollection
and the second is the keyword args forscatter()
.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 aQueueNetwork
instance. The Graph returned has theedge_type
edge property set for each edge. Note that the graph may be altered.
Parameters: adjacency : dict or
ndarray
An adjacency list as either a dict, or an adjacency matrix.
adjust : int
{1, 2}
(optional, default: 1)Specifies what to do when the graph has terminal vertices (nodes with no outedges). 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 theiredge_type
of that loop is set to 0.adjust = 2
: All edges leading to terminal nodes have theiredge_type
set to 0.**kwargs :
Unused.
Returns: out :
networkx.DiGraph
A directed graph with the
edge_type
edge property.Raises: TypeError
Is raised if
adjacency
is not a dict orndarray
.Examples
If terminal nodes are such that all inedges 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) >>> ans {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) >>> ans {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) >>> ans {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 withprob_loop
probability. It then callsset_types_random()
on the resulting graph.
Parameters: num_vertices : int (optional, default: 250)
The number of vertices in the graph.
prob_loop : float (optional, default: 0.5)
The probability that a loop gets added to a vertex.
**kwargs :
Any parameters to send to
minimal_random_graph()
orset_types_random()
.Returns: A graph with the position of the vertex set as a property. The position property is called
pos
. Also, theedge_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 thenset_types_rank()
where therank
keyword argument is given bynetworkx.pagerank()
.
Parameters: num_vertices : int (optional, the default is 250)
The number of vertices in the graph.
**kwargs :
Any parameters to send to
minimal_random_graph()
orset_types_rank()
.Returns: A graph with a
pos
vertex property and theedge_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 thepagerank()
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: g :
networkx.DiGraph
,numpy.ndarray
, dict, etc.Any object that
DiGraph
accepts.seed : int (optional)
An integer used to initialize numpy’s psuedorandom number generator.
Returns: mat :
ndarray
Returns a transition matrix where
mat[i, j]
is the probability of transitioning from vertexi
to vertexj
. If there is no edge connecting vertexi
to vertexj
thenmat[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_vertices : int
The number of vertices in the graph.
seed : int (optional)
An integer used to initialize numpy’s psuedorandom number generators.
**kwargs :
Unused.
Returns: 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 vertexv
, all other vertices with Euclidean distance less or equal tor
are connect by an edge — wherer
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 thepagerank()
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: g :
networkx.DiGraph
,ndarray
, dict, etc.Any object that
DiGraph
accepts.rank :
numpy.ndarray
An ordering of the vertices.
pType2 : float (optional, default: 0.1)
Specifies the proportion of vertices that will be of type 2.
pType3 : float (optional, default: 0.1)
Specifies the proportion of vertices that will be of type 3 and that are near pType2 vertices.
seed : int (optional)
An integer used to initialize numpy’s psuedorandom number generator.
**kwargs :
Unused.
Returns: 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 aDiGraph
.
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: g :
networkx.DiGraph
,numpy.ndarray
, dict, etc.Any object that
DiGraph
accepts.proportions : dict (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 nonloop edges that are expected to be of that type. The values can must sum to one.
loop_proportions : dict (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.
seed : int (optional)
An integer used to initialize numpy’s psuedorandom number generator.
**kwargs :
Unused.
Returns: 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 anetworkx.DiGraph
.ValueError
Raises a
ValueError
if thepType
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 nonloop 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: g :
networkx.DiGraph
,networkx.Graph
, etc.Any object that networkx can turn into a
DiGraph
.return_dict_of_dict : bool (optional, default:
True
)Specifies whether this function will return a dict of dicts or a dict of lists.
Returns: adj : dict
An adjacency representation of graph as a dictionary of dictionaries, where a key is the vertex index for a vertex
v
and the values aredicts
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]}