Home Page > > Details

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)])

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Ghostwriter Cs1b Spring 2024 Tth Hw08h... 2024-04-19
- Help With Managing Financial Risk Prob... 2024-04-19
- Ghostwriter Cs 0449 – Project 5: /Dev/ 2024-04-19
- Ghostwriter Elec 2141 Digital Circuit ... 2024-04-19
- Help With Csc171 — Videogame Projecthe 2024-04-19
- Help With Comp3411 Artificial Intellig 2024-04-19
- Help With Stat3061: Random Processes &... 2024-04-19
- Ghostwriter Accounting 452, Spring 202... 2024-04-19
- Ghostwriter Finc5001 Foundations In Fi... 2024-04-19
- Ghostwriter 7Ssmm712 – Topics In Appli 2024-04-19
- Help With Com 337 - Film Studies For T... 2024-04-19
- Ghostwriter Mes202tc - Digital Vlsi Sy... 2024-04-19
- Ghostwriter Geography 2041B Distance S... 2024-04-19
- Ghostwriter Ecos3006 International Tra... 2024-04-19
- Help With Fit5225 2024 Sm1 Creating An... 2024-04-19
- Help With Cit 593: Introduction To Com... 2024-04-19
- Help With Math 4931: Take Home Examgho... 2024-04-19
- Ghostwriter Csci 547|Info 533: Systems... 2024-04-19
- Ghostwriter Cs536-S24 Intro To Pls And... 2024-04-19
- Help With Fit5212 - Assignment 1Ghostw... 2024-04-19

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！