Graph utilities¶
Takes an adjacency list, dict, or matrix and returns a graph. |
|
Creates a random graph where the edges have different types. |
|
Creates a random graph where the vertex types are selected using their pagerank. |
|
Generates a random transition matrix for the graph |
|
Takes a graph and returns an adjacency list. |
|
Creates a connected graph with random vertex locations. |
|
Creates a stylized graph. |
|
Randomly sets |
|
A directed graph class built to work with a |
|
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:
- data
networkx.DiGraph
,numpy.ndarray
, dict, etc. Any object that networkx can turn into a
DiGraph
.- kwargs
Any additional arguments for
networkx.DiGraph
.
- data
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
.
- pos
- 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
andscatter()
. Gets the default keyword arguments for both methods by callinglines_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()
.
- line_kwargsdict (optional, default:
- 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
andscatter()
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()
.
- line_kwargsdict (optional, default:
- Returns:
- tuple
A 2-tuple 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:
- 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 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 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 withprob_loop
probability. It then callsset_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()
orset_types_random()
.- Returns:
QueueNetworkDiGraph
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_verticesint (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:
QueueNetworkDiGraph
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.- seedint (optional)
An integer used to initialize numpy’s psuedo-random 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_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 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.
- 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 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.- 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 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 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:
- g
networkx.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 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]}