Background
Spatial Networks for Locations
Locations are connected via roads (we assume traders can travel in both
directions!) These locations form a spatial network. As traders used horses for travelling, they couldn’t travel too far!
Pottery Trade
Pottery trade was very active at that times. Each location had its own supply and demandfor pottery. The supply and demand were communicated by traders who also formed their
own networks. They also potentially communicated the prices, but in these project wewill
disregard this information.
Social Networks for Traders
Traders living in some locations know each other and exchange information about supplyand demand via postal services. These traders for a social network.
How to Represent Networks
Each network can be presented as a graph. In this project, we will focus on undirectedgraphs: both social and spatial networks can be represented as graphs:
1. Spatial networks: nodes correspond to locations, and edges —to roads betweenthem (both directions)
2. Social networks: nodes correspond to traders, and edges connect those who
know each other (communicate)
Networks/graphs can be very different!
Project Questions
1. Represent road maps and trader networks as graphs
2. Find the shortest path between any two locations (return the shortest path andthedistance)
3. (Static traders) Find the best trading options for a particular trader residing in aparticular location. Core concepts: Itineraries
Itineraries provide the basis for our spatial network. They are provided as a list of (L1,L2, distance) tuples; listed in any order. L1 and L2 are provided as strings, distance is an integer number (miles).
In the example:
>>> itineraries = [('L1', 'L2', 20), ('L2', 'L3', 10), ('L1', 'L4', 15), ('L4','L5',5), ('L4', 'L8', 20), ('L5', 'L8', 22), ('L5', 'L6', 6), ('L6', 'L7', 20)]
Supply and Demand of Goods (Pottery)
Each location has its own supply and demand in pottery: supply is provided as a positivenumber, demand — as a negative. Locations with the highest demand should be servedfirst. Assume both numbers are integers. This is provided as a dictionary (in no particular order)
>>> status = {'L1':50, 'L2':-5, 'L4':-40, 'L3':5, 'L5':5, 'L8':10, 'L6':10, 'L7':-30}Trader Locations
Traders reside in some but not all locations. Only locations where traders are present cantrade. Each location can have maximum a single trader. Traders are provided as strings.
Trader locations are provided as a dictionary (in no particular order). In the example:
>>> trader_locations = {'T1':'L1', 'T2': 'L3', 'T3':'L4', 'T4':'L8', 'T5':'L7','T6':'L5'}
Social network of Traders
Traders also form a social network. A trader only trades within their own network
(considers friends only). Traders also have access to supplies and demands in the
corresponding locations. Trader friendships are provided as a list of tuples (in no particular order):
>>> traders = [('T1','T2'), ('T2', 'T5'), ('T3', 'T1'), ('T3', 'T5'), ('T3', 'T6')]Q1
Write a function create_spatial_network(itineraries) that takes itineraries (a list of
tuples) and returns for each location its neighbors and distances to them. A location is
considered to be a neighbour of another location if it can be reached by a single road (oneedge).
Input:
itineraries: a list of tuples, where each tuple is of the
form (location1, location2, distance). location1 and location2 are the stringlabels for these locations and distance is an integer. Your function should return a list of tuples, where each tuple is of the
form (location, neighbours). neighbours should be of the
form [(neighbour1, distance1), (neighbour2, distance2), ...] and be sorted by their
distances (in the increasing order). If two or more neighbors have the same distance tothe location, tie-break by alphanumeric order on their labels. Note that in addition to the neighbors, the overall list has to be sorted. You may assume: Distances are non-negative integer values
Inputs are correctly formatted data structures and types
There are no duplicate entries itineraries, and in each neighbor pair only appear
once (i.e. no [('L1', 'L2', 20), ('L2', 'L1', 20)])
Here is a diagram of an example network:
For the network above, this would be a possible itineraries and the function should
return the following:
>>> itineraries = [('L1', 'L2', 20), ('L2', 'L3', 10), ('L1', 'L4', 15), ('L4','L5',5), ('L4', 'L8', 20), ('L5', 'L8', 22), ('L5', 'L6', 6), ('L6', 'L7', 20)]
>>> create_spatial_network(itineraries)
[('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1', 20)]), ('L3', [('L2',10)]),('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4', 5), ('L6', 6), ('L8', 22)]),('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8', [('L4', 20), ('L5', 22)])]A different example (not pictured):
>>> itineraries = [('L4', 'L1', 2), ('L3', 'L1', 5), ('L1', 'L5', 5), ('L2', 'L5',1)]>>> create_spatial_network(itineraries)
[('L1', [('L4', 2), ('L3', 5), ('L5', 5)]), ('L2', [('L5', 1)]), ('L3', [('L1',5)]),('L4', [('L1', 2)]), ('L5', [('L2', 1), ('L1', 5)])]
Q2
Write a function sort_demand_supply(status) that takes a dictionary of demands andsupplies and returns the information as a list of tuples sorted by the value so that locationswith greatest demands (the most negative number) are provided first.
Input: status: a dictionary of demands and supplies. The keys are the location labels
(strings) and the values are integers, where a positive value represents supply
and a negative value represents demand. Your function should return a list of tuples, where each tuple is of the
form (location, demand_supply), and the list should be sorted in ascending order by
their demand_supply (i.e. greatest demand to greatest supply). If two or more locationshave the same demand or supply, tie-break by alphanumeric order on their labels. You may assume: Inputs are correctly formatted data structures and types
>>> status = {'L1':50, 'L2':-5, 'L4':-40, 'L3':5, 'L5':5, 'L8':10, 'L6':10, 'L7':-30}>>> sort_demand_supply(status)
[('L4', -40), ('L7', -30), ('L2', -5), ('L3', 5), ('L5', 5), ('L6', 10), ('L8',10),('L1', 50)]
Another example:
>>> status = {'L1':30, 'L2':-20, 'L4':100, 'L3':-50, 'L5':-60}
>>> sort_demand_supply(status)
[('L5', -60), ('L3', -50), ('L2', -20), ('L1', 30), ('L4', 100)]
Q3
Write a function create_social_network(traders) that takes traders, a list of tuples
specifing trader connections (edges in the trader social network) and returns a list
containing (trader, direct_connections) for each trader in traders.
Input: traders: a list of tuples specifing trader connections (edges in the trader social
network). Each tuple is of the
form (trader1, trader2) where trader1 and trader2 are string names of
each trader.
Your function should return list of tuples in alphanumeric order of trader name, where
each tuple is of the form (trader, direct_connections), and direct_connections is analphanumerically sorted list of that trader's direct connections (i.e. there exists an edgebetween them in the trader social network). You may assume: Inputs are correctly formatted data structures and types. Just like Q1a, you don't
need to guard against something like [('T1', 'T2'), ('T2', 'T1')] or duplicate
entries.
The pictured example:
>>> traders = [('T1','T2'), ('T2', 'T5'), ('T3', 'T1'), ('T3', 'T5'), ('T3', 'T6')]>>> create_social_network(traders)
[('T1', ['T2', 'T3']), ('T2', ['T1', 'T5']), ('T3', ['T1', 'T5', 'T6']), ('T5', ['T2','T3']),('T6', ['T3'])]
Another example (not pictured):
>>> traders = [('T1', 'T5'), ('T2', 'T6'), ('T3', 'T7'), ('T4', 'T8'), ('T1', 'T6'),('T2', 'T7'), ('T3', 'T8'), ('T4', 'T5'), ('T1', 'T7'), ('T2', 'T8'), ('T3', 'T5'),('T4','T6')]
>>> create_social_network(traders)
[('T1', ['T5', 'T6', 'T7']), ('T2', ['T6', 'T7', 'T8']), ('T3', ['T5', 'T7', 'T8']),('T4', ['T5', 'T6', 'T8']), ('T5', ['T1', 'T3', 'T4']), ('T6', ['T1', 'T2', 'T4']),('T7',['T1', 'T2', 'T3']), ('T8', ['T2', 'T3', 'T4'])]
Q4
Write a function shortest_path(spatial_network, source, target, max_bound) that
takes a spatial network, initial (source) location, target location and the maximumdistance(that a trader located in the initial location can travel) as its input and returns a tuple withashortest path and its total distance.
Input: spatial_network: a list of tuples, where each tuple is of the
form (location, neighbours) and neighbours is of the
form [(neighbour1, distance1), (neighbour2, distance2), ...]. This
corresponds with the output of the function you wrote for Q1a. source: the location label (string) of the initial location. target: the location label (string) of the target location. max_bound: an integer (or None) that specifies the maximum total distance that
your trader can travel. If max_bound is None then always return the path withminimum distance. Your function should return a tuple (path, total_distance), where path is a string of
each location label in the path separated by a - hyphen character, and total_distanceisthe total of the distances along the path.
If there's two paths with the same minimum total distance, choose the path with morelocations on it. If there's two paths with the same minimum total distance and they havethe same number of locations on the path then choose alphanumerically smaller pathstring.
If there is no path with a total distance within the max_bound then your function shouldreturn (None, None). You may assume:
Inputs are correctly formatted data structures and types. Distances are non-negative integer values. The network is connected, so a path always exists, although it may not have atotal distance within the maximum bound.
>>> spatial_network = [('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1',20)]),('L3', [('L2', 10)]), ('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4',5),('L6', 6), ('L8', 22)]), ('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8',[('L4', 20), ('L5', 22)])]
>>> shortest_path(spatial_network, 'L1', 'L3', 50)
('L1-L2-L3', 30)
>>> shortest_path(spatial_network, 'L1', 'L3', 0)
(None, None)
>>> shortest_path(spatial_network, 'L1', 'L3', 10)
(None, None)
>>> shortest_path(spatial_network, 'L1', 'L3', None)
('L1-L2-L3', 30)
Q5
In this question you will be writing a
function trade(spatial_network, status_sorted, trader_locations, trader_network, max_dist_per_unit=3) that makes a single trade.
Input:
spatial_network: a list of tuples, where each tuple is of the
form (location, neighbours) and neighbours is of the
form [(neighbour1, distance1), (neighbour2, distance2), ...]. This
corresponds with the output of the function you wrote for Q1a. status_sorted: a list of tuples, where each tuple is of the
form (location, demand_supply), and the list is sorted in ascending order by
their demand_supply (i.e. greatest demand to greatest supply) with ties brokenalphanumerically on location label. This corresponds with the output of the
function you wrote for Q1b. trader_locations: a dictionary of trader locations. The structure of this
is trader_name: trader_location, where
both trader_name and trader_location are strings. trader_network: a list of tuples in alphanumeric order of trader name, whereeach tuple is of the form (trader, direct_connections), and direct_connections is an alphanumerically sorted list of that trader's direct
connections (i.e. there exists an edge between them in the trader social network). This corresponds with the output of the function you wrote for Q1c. max_dist_per_unit: a float or integer value that represents the maximumthetrader is willing to travel per unit. This parameter should have a default of 3in your
function. Your function should return a single trade as a
tuple (supplier_location, consumer_location, amount) where supplier_locationand consumer_location are location labels (strings) and amount is a positive integer. If notrade is possible return (None, None, None).
Traders from the locations with highest demand contact their social network asking for
help. Then they choose the contacts worth travelling to, based on distance and the
amount of supply there. The trade shoud be determined as follows:
1. Find the location with the highest demand, this will be the consumer location. 2. Find the trader at the consumer location (skip this location and go back to step1if
there are no traders at this location) and consider the trader's connections. 3. A supplier location can only supply to the consumer location if their status is
positive (i.e. they have items to supply) and can supply an amount up to this value(i.e. they can't supply so much that they result in having a demand for the itemthey are supplying). 4. If a supplier location is directly neighbouring by a single road (adjacent) to theconsumer location then the distance used is the direct distance between the twolocations, even if there exists a shorter route via other locations. If the supplier andconsumer are not adjacent then the shortest_path function should be used todetermine the distance. 5. The trader will trade with the connection that has the highest amount of units tosupply, subject to meeting the max_dist_per_unit of the distance/units ratio. 6. Then if no trade is possible in this location, consider the next location. Return (None, None, None) if all locations have been considered. You may assume: Inputs are correctly formatted data structures and types. Distances are non-negative integer values. There will be at most one trader at any particular location.
Consider the spatial and trader network in the image above. With a
default max_dist_per_unit of 3, the trader will only consider travelling maximum3 milesfor each unit (one direction), i.e. they will agree to travel 6 miles for get 2 pottery units but
not a single one.
In the example, we have 'L4' as the location with the highest demand of 40 units
(demand_supply=-40) and the trader 'T3' who resides there. 'T3''s direct connectionsare ['T1', 'T5', 'T6']. We can't trade with 'T5' because at their location ('L7') there is
also demand for the items. We compare the units able to be supplied and the distance-units ratio for each potential
supplier: T1:
o location: L1
o supply max: 50
o distance: 15
o so they could supply all 40 units that are demanded at L4
o distance/units = 15/40 = 0.375
T6:
o location: L5
o supply max: 5
o distance: 5
o so they could supply 5 of the units that are demanded at L4
o distance/units = 5/5 = 1.0
Since T1 has the largest amount of units able to be supplied, and the distance/units ratiois below the maximum (3), this trade goes ahead and the function would
return ('L1', 'L4', 40). >>> spatial_network = [('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1',20)]),('L3', [('L2', 10)]), ('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4',5),('L6', 6), ('L8', 22)]), ('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8',[('L4', 20), ('L5', 22)])]
>>> status_sorted = [('L4', -40), ('L7', -30), ('L2', -5), ('L3', 5), ('L5', 5), ('L6',10), ('L8', 10), ('L1', 50)]
>>> trader_locations = {'T1':'L1', 'T2': 'L3', 'T3':'L4', 'T4':'L8', 'T5':'L7','T6':'L5'}
>>> trader_network = [('T1', ['T2', 'T3']), ('T2', ['T1', 'T5']), ('T3', ['T1','T5','T6']), ('T5', ['T2', 'T3']),('T6', ['T3'])]
>>> trade(spatial_network, status_sorted, trader_locations, trader_network)
('L1', 'L4', 40)
More examples:
>>> spatial_network = [('L1', [('L4', 2), ('L3', 5), ('L5', 5)]), ('L2', [('L5',1)]),('L3', [('L1', 5)]), ('L4', [('L1', 2)]), ('L5', [('L2', 1), ('L1', 5)])]
>>> status = {'L1':30, 'L2':-20, 'L4':100, 'L3':-50, 'L5':-60}
>>> status_sorted = [('L5', -60), ('L3', -50), ('L2', -20), ('L1', 30), ('L4',100)]>>> trader_locations = {'T1': 'L1', 'T2': 'L2'}
>>> trader_network = [('T1', ['T2']), ('T2', ['T1'])]
>>> trade(spatial_network, status_sorted, trader_locations, trader_network)
('L1', 'L2', 20)
>>> trade(spatial_network, status_sorted, trader_locations, trader_network,
max_dist_per_unit=0.001)
(None, None, None)
Q6
In this part you'll be using the trade() function from part 3a iteratively to determine thestatus after several trades. Write a
function trade_iteratively(num_iter, spatial_network, status, trader_locations, trader_network, max_dist_per_unit=3) that takes the number of iterations to perform,
the spatial network, status dictionary, trader locations dictionary, trader network, and
maximum distance per unit and returns a tuple containing the sorted status list
after num_iter trades along with a list of trades performed.
Input: num_iter: the number of iterations to perform as an integer or None if the
iteration should continue until no further trades can be made. spatial_network: a list of tuples, where each tuple is of the
form (location, neighbours) and neighbours is of the
form [(neighbour1, distance1), (neighbour2, distance2), ...]. This
corresponds with the output of the function you wrote for Q1a. status: a dictionary of demands and supplies. The keys are the location labels
(strings) and the values are integers, where a positive value represents supply
and a negative value represents demand. trader_locations: a dictionary of trader locations. The structure of this
is trader_name: trader_location, where
both trader_name and trader_location are strings. trader_network: a list of tuples in alphanumeric order of trader name, whereeach tuple is of the form (trader, direct_connections), and direct_connections is an alphanumerically sorted list of that trader's direct
connections (i.e. there exists an edge between them in the trader social network). This corresponds with the output of the function you wrote for Q1c.
max_dist_per_unit: a float or integer value that represents the maximumthetrader is willing to travel per unit. This parameter should have a default of 3in your
function. At each iteration, the next trade to be performed is determined by the process in part 3a. We strongly suggest using the provided trade() function to find this trade. Your functionshould update the status dictionary at each iteration. Your function should return a tuple (final_supply_sorted, trades) containing the sorteddemand-supply status after num_iter trades along with a list of trades performed. The final_supply_sorted should be a list of tuples, where each tuple is of the
form (location, demand_supply), and the list should be sorted in ascending order by
their demand_supply (i.e. greatest demand to greatest supply). If two or more locationshave the same demand or supply, tie-break by alphanumeric order on their
labels. trades should be a list of each trade performed, where a trade is of the
form (supplier_location, consumer_location, amount) where supplier_locationandconsumer_location are location labels (strings) and amount is a positive integer. You may assume: Inputs are correctly formatted data structures and types. Distances are non-negative integer values. There will be at most one trader at any particular location.
In the example pictured, only one trade can occur:
>>> spatial_network = [('L1', [('L4', 15), ('L2', 20)]), ('L2', [('L3', 10), ('L1',20)]),('L3', [('L2', 10)]), ('L4', [('L5', 5), ('L1', 15), ('L8', 20)]), ('L5', [('L4',5),('L6', 6), ('L8', 22)]), ('L6', [('L5', 6), ('L7', 20)]), ('L7', [('L6', 20)]), ('L8',[('L4', 20), ('L5', 22)])]
>>> status = {'L1': 50, 'L2': -5, 'L4': -40, 'L3': 5, 'L5': 5, 'L8': 10, 'L6': 10,'L7':-30}
>>> trader_locations = {'T1': 'L1', 'T2': 'L3', 'T3': 'L4', 'T4': 'L8', 'T5': 'L7','T6':'L5'}
>>> trader_network = [('T1', ['T2', 'T3']), ('T2', ['T1', 'T5']), ('T3', ['T1','T5','T6']), ('T5', ['T2', 'T3']),('T6', ['T3'])]
>>> trade_iteratively(1, spatial_network, status, trader_locations, trader_network)([('L7', -30), ('L2', -5), ('L4', 0), ('L3', 5), ('L5', 5), ('L1', 10), ('L6', 10),('L8',10)], [('L1', 'L4', 40)])
>>> trade_iteratively(None, spatial_network, status, trader_locations, trader_network)([('L7', -30), ('L2', -5), ('L4', 0), ('L3', 5), ('L5', 5), ('L1', 10), ('L6', 10),('L8',10)], [('L1', 'L4', 40)])