instances.request_graph

instances.request_graph(G, s, t, request_pairs)[source]

Generates PDP version of input graph G.

Output graph H contains additional information on the source, target, and request nodes and is metrically closed by use of the triangle inequality.

Parameters:
  • G (NetworkX graph) – The original NetworkX input graph. Graph is weighted, undirected, and satisfies the triangle inequality.
  • s (node) – Source node chosen from G.
  • t (node) – Target node chosen from G.
  • request_pairs (list) – Request pairs chosen from G. Each request_pair entry is (origin, destination). No node can be repeated in multiple entries.
Returns:

H – Request graph version of G.
Return type:

NetworkX graph
Raises:

AssertionError – If more nodes are given than exist in G. If s, t, or request nodes are not contained in G.

Examples

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_weighted_edges_from([('ORD', 'LAX', 800), ('ORD', 'ATL', 500),
>>> ...                        ('ATL', 'MIA', 400), ('MIA', 'DFW', 350),
>>> ...                        ('LAX', 'SFO', 200), ('DFW', 'LAX', 500)])
>>> H = request_graph(G, 'MIA', 'ORD', [('SFO', 'LAX'), ('DFW', 'ATL')])