Introduction

Welcome to the Off the Beaten Path Xeek Challenge!

This is a fun and unique variation of the traditional travelling salesman problem.

In the traditional travelling salesman problem, the goal is to optimize the route that the “salesman” has to walk. This challenge introduces additional constraints and additional degrees of freedom (variables) to the problem. Not only will you be considering the distance to travel, but additional factors like simulation duration, budget, amount of rewards extracted from a particular site, and the cost of a worker. The solution to the challenge is not only the plan, but also an algorithm that will be tested on other problem setups (different graphs to explore, different values of constraints), therefore you have to keep in mind, that you are developing a universal tool for finding a solution.

The Xeek team has built a unique and powerful tool, called lyra_graphtool, to help you skip the graph setup part of the challenge and get to the important part; generating an algorithm to optimize the problem! This notebook, as well as a random walk exmaple solution and API Documentation will serve as your documenation and learning resources for the challenge.

Please use the links below if you would like to jump to a specific Object in this notebook, as well as a starter notebook with an example solution!

Initial Setup

Upon starting this challenge, competitors will need to download the required matrials from the Off the Beaten Path challenge page.

The Xeek team will provide:

• An arguments file that will contain information to set up the problem. All participants will recieve the same arguments file. This file will contain information like total budget, site rewards, and duration of the simulation.

• A graph JSON file. All participants will recieve the same graph.json file. This will be loaded into the lyra_graphtool.Graph object to set up the graph vertices and site information.

• A starter notebook, similar to the example solution, but without the example solution. This notebook will be your playground to write an algorithm to solve the Off the Beaten Path Challenge!

Note: Ensure that the lyra_graphtool folder is saved in your project folder to avoid import issues

Now let’s get started!

Run the next 3 code cells in order to setup graphs, budgets, worker costs, rewards, and duration. Double check to make sure the file paths for the lgtool.ProcessArgs.load() are correct.

import random
from copy import deepcopy
from random import randint
import pprint as pp

import lyra_graphtool as lgtool
from lyra_graphtool import Configuration, Config_Single_Time, Edge, Graph, Graph_Type, Parameters, Vertex, Worker_Type, Vertex_Type

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 6
      3 from random import randint
      4 import pprint as pp
----> 6 import lyra_graphtool as lgtool
      7 from lyra_graphtool import Configuration, Config_Single_Time, Edge, Graph, Graph_Type, Parameters, Vertex, Worker_Type, Vertex_Type

ModuleNotFoundError: No module named 'lyra_graphtool'

pargs = lgtool.ProcessArgs.load(arguments_file='../lyra-challenge/ready_setups/args_random', graph_file='../lyra-challenge/ready_setups/graph_random.json')

params = lgtool.Parameters(pargs.graph, 
                           budget = pargs.args_trial.budget, 
                           duration_time = pargs.args_trial.duration,
                           cost_rate = pargs.worker_cost_rate
                           )

cfg = lgtool.Configuration(params)

cfg.load_from_json('./solutions/solution_random.json')

ProcessArgs Object

The ProcessArgs object will be used in the intial setup of the problem. Xeek will provide the setup parameters for the graph and arguments file for the challenge. Challengers do, however, have the tools to create their own argument files. Remember, the final scoring will occur on a different argument file than what is provided, so it is to your advantage to create your own argument file(s) and test your algorithm to see if it is effiecient for all scenarios. Below will explore the functionality of the ProceesArgs object, by building a test arguments/graph file.

duration = 50 # amount of timesteps in problem
duration = str(int(duration))
arg_list_new = [
    '--trial_name', 'trial1',    # name of trial
    '--budget', '10000',          # budget that will be used by hiring workers of different types
    '--duration', duration,      # amount of timesteps in problem
    '--worker1_cost', '200',     # Worker_Type.WORKER1 cost/timestep which reduces our budget
    '--worker2_cost', '400',     # Worker_Type.WORKER2 cost/timestep which reduces our budget
    '--worker3_cost', '600',     # Worker_Type.WORKER3 cost/timestep which reduces our budget
    ################## BELOW GRAPH ARGUMENTS ####################
    '--filename_graph', '',      # if loading graph, max_x, max_y, num_verts, graph_type, num_site[k] (k=1,2,3) ignored
    '--max_x', '10',             # max x coordinate during random or grid graph creation
    '--max_y', '10',             # max y coordinate during random or grid graph creation
    '--num_verts', '30',         # amount of vertices (travel points) that the graph will have
    '--graph_type', 'grid',    # type of graph, either 'random' or 'grid' the difference between these is shown further in notebook
    '--num_site1', '3',          # amount of Vertex_Type.SITE1 on the graph mind that amount of all sites cannot be greater than 'num_verts-1'
    '--num_site2', '2',          # amount of Vertex_Type.SITE2 on the graph mind that amount of all sites cannot be greater than 'num_verts-1'
    '--num_site3', '5',          # amount of Vertex_Type.SITE3 on the graph mind that amount of all sites cannot be greater than 'num_verts-1'
    '--site1_acquire_time', '2',    # if args starting with 'site' are specified, they are imposed on loaded graph
    '--site2_acquire_time', '4',    # timesteps needed to extract Vertex_Type.SITE2 reward
    '--site3_acquire_time', '6',    # timesteps needed to extract Vertex_Type.SITE3 reward
    '--site1_reward', '100',     # reward from extracting Vertex_Type.SITE1
    '--site2_reward', '200',     # reward from extracting Vertex_Type.SITE2
    '--site3_reward', '300',     # reward from extracting Vertex_Type.SITE3
]

Create a ProcessArgs object and pass the new argument file through it

new_pargs = lgtool.ProcessArgs(arg_list_new)

ProcessArgs.save()

Save the new arguments file for future use

new_pargs.save(f'ready_setups/args_{new_pargs.args_trial.trial_name}')

ProcessArgs.load()

Load the new argument and graph files into ProcessArgs() using load()

new_pargs_from_load = lgtool.ProcessArgs.load(arguments_file='../lyra-challenge/ready_setups/args_args_trial1'
                                            ,graph_file='../lyra-challenge/ready_setups/graph_trial1.json')

load_graph()

Loading graph from filename into Site_Structures

# code here, need to figure out how to use this

ProcessArgs.values_to_args()

Finally, return the new arguments into a list and compare to what was created at the top, using values_to_args()

new_pargs_list = new_pargs.values_to_args() 
pp.pprint(new_pargs_list)

['--trial_name',
 'trial1',
 '--max_x',
 '10',
 '--max_y',
 '10',
 '--num_verts',
 '30',
 '--graph_type',
 'grid',
 '--num_site1',
 '3',
 '--num_site2',
 '2',
 '--num_site3',
 '5',
 '--site1_acquire_time',
 '2',
 '--site2_acquire_time',
 '4',
 '--site3_acquire_time',
 '6',
 '--site1_reward',
 '100.0',
 '--site2_reward',
 '200.0',
 '--site3_reward',
 '300.0',
 '--site1_mult_time',
 '1',
 '--site2_mult_time',
 '1',
 '--site3_mult_time',
 '1',
 '--site1_mult_time_active',
 '0, 50',
 '--site2_mult_time_active',
 '0, 50',
 '--site3_mult_time_active',
 '0, 50',
 '--site1_mult_workers',
 '1, 1, 1',
 '--site2_mult_workers',
 '1, 1, 1',
 '--site3_mult_workers',
 '1, 1, 1',
 '--site1_exp_time',
 '50',
 '--site2_exp_time',
 '50',
 '--site3_exp_time',
 '50',
 '--worker1_cost',
 '200.0',
 '--worker2_cost',
 '400.0',
 '--worker3_cost',
 '600.0',
 '--budget',
 '10000.0',
 '--duration',
 '50']

---

Parameters Object

The loaded arguments and graph can be wrapped with lgtool.Parameters class which can be further passed to the lgtool.Configuration() object.

params = lgtool.Parameters(graph = pargs.graph
                           ,budget = pargs.args_trial.budget
                           ,duration_time = pargs.args_trial.duration
                           ,cost_rate = pargs.worker_cost_rate)

display()

Use the display() function to view the check the arguments that were passed through lgtool.Parameters

params.display()

{'budget': 1000.0, 'duration_time': 20, 'graph': <lyra_graphtool.graph.Graph object at 0x11842faf0>, 'worker_cost_rate': {<Worker_Type.WORKER1: 0>: 100.0, <Worker_Type.WORKER2: 1>: 200.0, <Worker_Type.WORKER3: 2>: 500.0}}

Or call each individual argument passed through lgtools.Parameters() object

print(params.budget)
print(params.duration_time)
print(params.graph)
print(params.worker_cost_rate)

1000.0
20
<lyra_graphtool.graph.Graph object at 0x11842faf0>
{<Worker_Type.WORKER1: 0>: 100.0, <Worker_Type.WORKER2: 1>: 200.0, <Worker_Type.WORKER3: 2>: 500.0}

---

Configuration Object

The lgtool.Configuration() object contains not only the graph to be optimized, but also problem constraints and setup like budget, duration, and worker cost rates. Pass the arguments run through the lgtool.Parameters() section for set up. This module will be the workhorse to solve the challenge because it allows users to add, update, and extract most parameters for the challenge.

params = lgtool.Parameters(pargs.graph, 
                           budget = pargs.args_trial.budget, 
                           duration_time = pargs.args_trial.duration,
                           cost_rate = pargs.worker_cost_rate
                           )

cfg = lgtool.Configuration(params)

add_sched()

Add a specific schedule for a Worker_Type (wt) and number of those worker (wn). To access the configuration dictionary, call .config on the Configuration object created in the intial setup. Users can access this information using this format: Configuration.config[Worker_Type][worker number]

In the example below, .config is called on the Configuration object. We define that we want a Worker_Type = WORKER1 and we want 1 of those workers.

schedule_add = cfg.config[0][1]
print(schedule_add)
cfg.add_sched(wt = Worker_Type.WORKER1, wn=2, sched=schedule_add)

{0: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f3a9b40>, 1: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262d40>, 2: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262da0>, 3: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262e00>, 4: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262e60>, 5: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262ec0>, 6: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262f20>, 7: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262f80>, 8: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f262fe0>, 9: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263040>, 10: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f2630a0>, 11: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263100>, 12: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263160>, 13: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f2631c0>, 14: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263220>, 15: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263280>, 16: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f2632e0>, 17: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263340>, 18: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f2633a0>, 19: <lyra_graphtool.configuration.Config_Single_Time object at 0x11f263400>}

budget_feasible()

Here we test whether the entire solution configuration stays within the budget contraints set in the arguments. This can be called on the Configuration object with no input arugments.

cfg.budget_feasible()

True

cost()

This will return the cost of the entire configuration. Remember, profit will be used to score the solution(profit = revenue - cost), so its important to not only increase revenue, but also be mindful of costs. It can be called on the Configuration object with no input arguments.

cfg.cost()

900.0

cost_sched()

Users can calculate the cost of a single-worker schedule by inputting.

schedule = cfg.config
cfg.cost_sched(sched = schedule[0][1],worker=Worker_Type.WORKER1)

0

feasible()

Method to determine overall feasibility of the configuration in terms of space, buget, and access

cfg.feasible()

True

get_accessed_sites()

Method to return the sites that were accessed in a schedule

schedule = cfg.config
cfg.get_accessed_sites(schedule)

({(3.0, 0.0): 0,
  (3.0, 2.0): 0,
  (3.0, 4.0): 0,
  (2.0, 5.0): 0,
  (4.0, 6.0): 0,
  (1.0, 2.0): 0,
  (1.0, 3.0): 0,
  (7.0, 0.0): 0,
  (7.0, 3.0): 0,
  (5.0, 6.0): 0},
 'Log of accesses:\n')

get_current_workers()

Method to return a dictionary of the the workers used in the configuration. This requires the full configuration schedule as an input.

cfg.get_current_workers(schedule)

{<Worker_Type.WORKER1: 0>: 1,
 <Worker_Type.WORKER2: 1>: 0,
 <Worker_Type.WORKER3: 2>: 0}

get_max_revenue()

Get the maximum revenue earned for a particular graph configuration

cfg.get_max_revenue()

2200.0

get_sched_path_length()

This is used to determine the length of one worker schedule (how many steps was the worker active). It requires a single schedule as an input

cfg.get_sched_path_length(schedule[0][9])

0

get_vertices_start()

Returns the list vertices from which a worker’s path must start

start = cfg.get_vertices_start()
print(start)

[<lyra_graphtool.vertex.Vertex object at 0x11fbee0b0>]

get_worker()

Method to return a Worker object. The worker object has rates compliant with the configuration

cfg.get_worker(Worker_Type.WORKER1)

<lyra_graphtool.worker.Worker at 0x12fcb9e10>

is_empty()

Determine if a single worker schedule is empty

schedule = cfg.config
cfg.is_empty(schedule[0][1])

True

load_from_json()

Loading the configuration from a .json

cfg.load_from_json(file_name='./solutions/solution_random.json')

revenue()

This is a method to calculate the revenue for the entire schedule configuration

cfg.revenue()

0

save()

Save the configuration solution as a pickle file

cfg.save(file_name='./ready_setups/test_config_save')

save_to_json()

Save the configuration solution as a .json file

cfg.save_to_json('./ready_setups/test_config_save.json')

sched_all_feasible_access_sites()

This method determines if a schedules’s access properties are feasible

cfg.sched_all_feasible_access_sites()

True

sched_all_feasible_space()

This is a method to determine if all schedules are spatially feasible

cfg.sched_all_feasible_space()

True

sched_feasible_access_sites()

This method determines if a single schedule’s access/extract properties are feasible. It requires the input of a single schedule and the Worker_Type class to test.

schedule = cfg.config
cfg.sched_feasible_access_sites(sched= schedule[0][1], worker_type= Worker_Type.WORKER1)

True

sched_feasible_space()

This tests whether the whole configuration is spatially feasible and requires an input of a single schedule.

schedule = cfg.config
cfg.sched_feasible_space(sched=schedule[0][1])

True

sched_info()

Prints information about specific workers schedule in the form: [timestep, (x_coordinate, y_coordinate), Vertex_Type, accessed/not accessed]

schedule = cfg.config
cfg.sched_info(schedule[0][2])

['[t=0, (None,None), vtype=None, acc=False ]',
 '[t=1, (None,None), vtype=None, acc=False ]',
 '[t=2, (None,None), vtype=None, acc=False ]',
 '[t=3, (None,None), vtype=None, acc=False ]',
 '[t=4, (None,None), vtype=None, acc=False ]',
 '[t=5, (None,None), vtype=None, acc=False ]',
 '[t=6, (None,None), vtype=None, acc=False ]',
 '[t=7, (None,None), vtype=None, acc=False ]',
 '[t=8, (None,None), vtype=None, acc=False ]',
 '[t=9, (None,None), vtype=None, acc=False ]',
 '[t=10, (None,None), vtype=None, acc=False ]',
 '[t=11, (None,None), vtype=None, acc=False ]',
 '[t=12, (None,None), vtype=None, acc=False ]',
 '[t=13, (None,None), vtype=None, acc=False ]',
 '[t=14, (None,None), vtype=None, acc=False ]',
 '[t=15, (None,None), vtype=None, acc=False ]',
 '[t=16, (None,None), vtype=None, acc=False ]',
 '[t=17, (None,None), vtype=None, acc=False ]',
 '[t=18, (None,None), vtype=None, acc=False ]',
 '[t=19, (None,None), vtype=None, acc=False ]']

sched_revenue()

This method requires a single schedule as an input and returns the revenue of that particular schedule

cfg.sched_revenue(schedule[0][2])

0

site_accessed()

This method determines whether or not the site was accessed in the configuration. It reuqired a Vertex object as an input.

v_orig = cfg.graph.get_vertices_type(lgtool.Vertex_Type.ORIGIN)[0]
cfg.site_accessed(v=v_orig)

False

site_accessed_at_time()

This method requires a Vertex as an input and returns whether of not that site was accessed at a given time. This example uses timestep=5. You can see that this site was not accessed at timestep=5.

v_orig = cfg.graph.get_vertices_type(lgtool.Vertex_Type.SITE1)[0]
cfg.site_accessed_at_time(v=v_orig, t=5)

False

---

Edge Object

Edge.info()

Edge.info() returns the edge information about a given Edge object

verts = pargs.graph.vertices
v1 = verts[0]
v2 = verts[-1]

edge_obj = lgtool.Edge(v1=v1,v2=v2)
edge_obj.info()

[(3.0, 0.0), (5.0, 0.0)]

in_graph()

This method determines if the edge is allowed to travel in 1 timestep

verts = pargs.graph.vertices
v1 = verts[0]
v2 = verts[-1]

edge_obj = lgtool.Edge(v1=v1,v2=v2)
edge_obj.in_graph()

False

nearest_neighbor()

This method requires an input of two vertices on the graph and determines if they are near each other.

verts = pargs.graph.vertices
v1 = verts[0]
v2 = verts[-1]

edge_obj = lgtool.Edge(v1=v1,v2=v2)
edge_obj.nearest_neighbor()

False

---

Graph Object

add_vertex()

add_vertex() allows users to manually add a vertex to the graph configuration

verts = lgtool.Vertex(1, 1, Vertex_Type.SITE3, reward=1000)

print(verts)
cfg.graph.add_vertex(v=verts)

<lyra_graphtool.vertex.Vertex object at 0x1285a21d0>
after translations in x and y, no reduction in components
components:
{(9, 7): (<Vertex_Type.SITE3: 4>, 1)}

adjacent_vertices()

This method returns which vertices are adjacent to a given vertex

cfg.graph.adjacent_vertices(v=verts)

[<lyra_graphtool.vertex.Vertex at 0x10b57b670>,
 <lyra_graphtool.vertex.Vertex at 0x10b57b610>,
 <lyra_graphtool.vertex.Vertex at 0x10bc1c400>,
 <lyra_graphtool.vertex.Vertex at 0x10bc1c520>,
 <lyra_graphtool.vertex.Vertex at 0x10bc1c5e0>]

closest_vertices()

closest_vertices() returns a list the closet vertices to a given vertex

closest_verts_list = cfg.graph.closest_vertices(v=verts)
pp.pprint(closest_verts_list)

[<lyra_graphtool.vertex.Vertex object at 0x11f7efd60>,
 <lyra_graphtool.vertex.Vertex object at 0x11f7efdf0>,
 <lyra_graphtool.vertex.Vertex object at 0x11f7eea40>,
 <lyra_graphtool.vertex.Vertex object at 0x11f7ee950>]

connected_components()

connected_components() returns a list of vertices that are connected

cfg.graph.connected_components()

[[<lyra_graphtool.vertex.Vertex at 0x10b57b670>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c400>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c430>,
  <lyra_graphtool.vertex.Vertex at 0x10b57b610>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c3d0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c370>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c490>,
  <lyra_graphtool.vertex.Vertex at 0x10b57bc40>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c3a0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c460>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c5b0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c610>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c640>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c670>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c550>,
  <lyra_graphtool.vertex.Vertex at 0x10bd45e10>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c4f0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c7f0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c820>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c520>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c580>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c4c0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c7c0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c760>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c6a0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c700>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c790>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c850>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c730>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c6d0>,
  <lyra_graphtool.vertex.Vertex at 0x10bc1c5e0>]]

depth_first_search()

This is a general, useful tool to consturct spanning trees and other things in graphs. This method will get connected components to a graph.

# updating

distance()

This method takes two sets of vertices and returns the edge of minimum distance between the two vertices

#updating

get_edges_at_vertex()

The get_edges_at_vertex() method will return a list of edges at a given vertex. Here we define our vertex using get_vertex_xy() with coordinates (x=2,y=3)

verts = cfg.graph.get_vertex_xy(x=2,y=3)
vert_edges = cfg.graph.get_edges_at_vertex(v=verts)
pp.pprint(vert_edges)

[<lyra_graphtool.edge.Edge object at 0x11771aa70>,
 <lyra_graphtool.edge.Edge object at 0x11771ad10>,
 <lyra_graphtool.edge.Edge object at 0x11771ae30>,
 <lyra_graphtool.edge.Edge object at 0x11771aef0>]

edges_info()

This method will return the edges for the entire graph

edge_list = cfg.graph.edges_info()
pp.pprint(edge_list)

{((0.0, 7.0), (0.0, 6.0)): 1,
 ((0.0, 8.0), (0.0, 7.0)): 1,
 ((1.0, 2.0), (1.0, 3.0)): 1,
 ((1.0, 5.0), (0.0, 6.0)): 1,
 ((1.0, 7.0), (0.0, 6.0)): 1,
 ((1.0, 7.0), (0.0, 7.0)): 1,
 ((1.0, 7.0), (0.0, 8.0)): 1,
 ((2.0, 0.0), (1.0, 0.0)): 1,
 ((2.0, 0.0), (2.0, 1.0)): 1,
 ((2.0, 1.0), (1.0, 0.0)): 1,
 ((2.0, 1.0), (1.0, 2.0)): 1,
 ((2.0, 3.0), (1.0, 2.0)): 1,
 ((2.0, 3.0), (1.0, 3.0)): 1,
 ((2.0, 5.0), (1.0, 5.0)): 1,
 ((2.0, 8.0), (1.0, 7.0)): 1,
 ((3.0, 0.0), (2.0, 0.0)): 1,
 ((3.0, 0.0), (2.0, 1.0)): 1,
 ((3.0, 0.0), (4.0, 1.0)): 1,
 ((3.0, 2.0), (2.0, 1.0)): 1,
 ((3.0, 2.0), (2.0, 3.0)): 1,
 ((3.0, 2.0), (4.0, 1.0)): 1,
 ((3.0, 4.0), (2.0, 3.0)): 1,
 ((3.0, 4.0), (2.0, 5.0)): 1,
 ((3.0, 6.0), (2.0, 5.0)): 1,
 ((3.0, 6.0), (3.0, 7.0)): 1,
 ((3.0, 6.0), (4.0, 6.0)): 1,
 ((3.0, 7.0), (2.0, 8.0)): 1,
 ((3.0, 7.0), (4.0, 6.0)): 1,
 ((4.0, 1.0), (5.0, 0.0)): 1,
 ((4.0, 1.0), (5.0, 2.0)): 1,
 ((4.0, 6.0), (5.0, 6.0)): 1,
 ((4.0, 6.0), (5.0, 7.0)): 1,
 ((5.0, 6.0), (5.0, 7.0)): 1,
 ((6.0, 0.0), (5.0, 0.0)): 1,
 ((6.0, 2.0), (5.0, 2.0)): 1,
 ((7.0, 0.0), (6.0, 0.0)): 1,
 ((7.0, 1.0), (6.0, 0.0)): 1,
 ((7.0, 1.0), (6.0, 2.0)): 1,
 ((7.0, 1.0), (7.0, 0.0)): 1,
 ((7.0, 3.0), (6.0, 2.0)): 1,
 ((7.0, 4.0), (7.0, 3.0)): 1}

get_vertex_xy()

This method returns the vertex object at given (x,y) coordinates

specified_verts = cfg.graph.get_vertex_xy(x=3,y=4)
print(specified_verts.info())

[(3.0, 4.0), <Vertex_Type.SITE1: 2>]

get_vertices_type()

We can use this method to extract vertices of a specific Vertex_Type

site1_vert_list = cfg.graph.get_vertices_type(v_type=Vertex_Type.SITE1)
pp.pprint(site1_vert_list)

[<lyra_graphtool.vertex.Vertex object at 0x10bc1c370>,
 <lyra_graphtool.vertex.Vertex object at 0x10bc1c580>,
 <lyra_graphtool.vertex.Vertex object at 0x10bc1c700>]

isolated_vertices()

Using isolated_vertices(), users can determine if any of the vertices in the graph are isolated from other vertices in the graph configuration.

isolated_verts_list = cfg.graph.isolated_vertices()
pp.pprint(isolated_verts_list)

[<lyra_graphtool.vertex.Vertex object at 0x11f7ee800>]

load_from_json()

Load .json graph files into the Configuration object

cfg.graph.load_from_json(file_name='./ready_setups/graph_sample.json')

make_graph_connected()

Using the output from depth_first_search(), users can bring together the connected components into a single component. Without this, we would have multiple origins, which would significantly increase the complexity.

paths()

Another import method for the challenge is paths(), When provided with two vertices, this method will return ever possible path that can connect the two points.

# get two verts and then get paths between them
verts = pargs.graph.vertices

# pick first and last vertex in the list
v1 = verts[0]
v2 = verts[-1]

print(v1.info(),v2.info())
print('\n')
paths12 = pargs.graph.paths(v1,v2)

print('\n')
for p in paths12:
    path = []
    for v in p:
        path.append((v.x,v.y))
        
    display(path)
    # print_graph() method when provided with a list of vertices, highlights them in orange
    pargs.graph.print_graph(p)

print_graph()

The print_graph() method will be one of the most important used during the challenge, because it will allow you to visualize your the solution that your algorithm has created.

pargs.graph.print_graph()

Graph.save()

Save the graph to a pickle file for future use

pargs.graph.save(file_name= './ready_setups/test_graph_save')

Graph.save_to_json()

Save the new graph to a .json file for later use

new_pargs.graph.save_to_json(f'ready_setups/graph_{new_pargs.args_trial.trial_name}.json')

set_edges()

unclear what this does?

cfg.graph.set_edges()

[<lyra_graphtool.edge.Edge at 0x11771a950>,
 <lyra_graphtool.edge.Edge at 0x11771a9b0>,
 <lyra_graphtool.edge.Edge at 0x11771aa10>,
 <lyra_graphtool.edge.Edge at 0x11771aa70>,
 <lyra_graphtool.edge.Edge at 0x11771ab30>,
 <lyra_graphtool.edge.Edge at 0x11771aad0>,
 <lyra_graphtool.edge.Edge at 0x11771abf0>,
 <lyra_graphtool.edge.Edge at 0x11771ab90>,
 <lyra_graphtool.edge.Edge at 0x11771acb0>,
 <lyra_graphtool.edge.Edge at 0x11771ad10>,
 <lyra_graphtool.edge.Edge at 0x11771ad70>,
 <lyra_graphtool.edge.Edge at 0x11771ac50>,
 <lyra_graphtool.edge.Edge at 0x11771add0>,
 <lyra_graphtool.edge.Edge at 0x11771ae30>,
 <lyra_graphtool.edge.Edge at 0x11771aef0>,
 <lyra_graphtool.edge.Edge at 0x11771ae90>,
 <lyra_graphtool.edge.Edge at 0x11771af50>,
 <lyra_graphtool.edge.Edge at 0x11771b010>,
 <lyra_graphtool.edge.Edge at 0x11771b070>,
 <lyra_graphtool.edge.Edge at 0x11771afb0>,
 <lyra_graphtool.edge.Edge at 0x11771b130>,
 <lyra_graphtool.edge.Edge at 0x11771b0d0>,
 <lyra_graphtool.edge.Edge at 0x11771b190>,
 <lyra_graphtool.edge.Edge at 0x11771b250>,
 <lyra_graphtool.edge.Edge at 0x11771b1f0>,
 <lyra_graphtool.edge.Edge at 0x11771b310>,
 <lyra_graphtool.edge.Edge at 0x11771b2b0>,
 <lyra_graphtool.edge.Edge at 0x11771b3d0>,
 <lyra_graphtool.edge.Edge at 0x11771b370>,
 <lyra_graphtool.edge.Edge at 0x11771b430>,
 <lyra_graphtool.edge.Edge at 0x11771b490>,
 <lyra_graphtool.edge.Edge at 0x11771b4f0>,
 <lyra_graphtool.edge.Edge at 0x11771b550>,
 <lyra_graphtool.edge.Edge at 0x11771b610>,
 <lyra_graphtool.edge.Edge at 0x11771b5b0>,
 <lyra_graphtool.edge.Edge at 0x11771b6d0>,
 <lyra_graphtool.edge.Edge at 0x11771b730>,
 <lyra_graphtool.edge.Edge at 0x11771b670>,
 <lyra_graphtool.edge.Edge at 0x11771b7f0>,
 <lyra_graphtool.edge.Edge at 0x11771b790>,
 <lyra_graphtool.edge.Edge at 0x117833a00>]

set_random_sites_origin()

unclear what this does?

cfg.graph.set_random_sites_origin(n_site1=3,n_site2=4,n_site3=5)

set_vertex_type()

We can use the set_vertex_type() method to manually set a particular Vertex object, by defining the Vertex_Type and (x,y) coordinates

set_verts = cfg.graph.set_vertex_type(v_type= Vertex_Type.SITE2, x=5, y=6)
print(set_verts.info())

[(5.0, 6.0), <Vertex_Type.SITE2: 3>]

set_vertex_coords()

Similar to set_vertex_type(), set_vertex_coords() will set a defined Vertex_Type to specificed (x,y) coordinates

input_vertex = lgtool.Vertex(x=1,y=2,v_type=Vertex_Type.BASIC)
print(f'Coordinates of Input Vertex:{input_vertex.info()}')
new_vertex = cfg.graph.set_vertex_coords(v=input_vertex, x=9,y=7)
print(f'Coordinates of New Vertex:{new_vertex.info()}')

Coordinates of Input Vertex:[(1, 2), <Vertex_Type.BASIC: 0>]
Coordinates of New Vertex:[(9, 7), <Vertex_Type.SITE3: 4>]

vertices_array()

We can use the vertices_array() method to extract a Numpy array of vertices in the graph

vert_array = cfg.graph.vertices_array()
print(vert_array)

[[3. 0.]
 [3. 2.]
 [3. 6.]
 [3. 4.]
 [3. 7.]
 [2. 3.]
 [2. 0.]
 [2. 1.]
 [2. 8.]
 [2. 5.]
 [4. 1.]
 [4. 6.]
 [1. 2.]
 [1. 5.]
 [1. 3.]
 [1. 7.]
 [1. 0.]
 [0. 8.]
 [0. 7.]
 [0. 6.]
 [7. 1.]
 [7. 4.]
 [7. 0.]
 [7. 3.]
 [6. 2.]
 [6. 0.]
 [5. 2.]
 [5. 6.]
 [5. 7.]
 [5. 0.]
 [0. 9.]
 [2. 1.]
 [2. 1.]]

vertices_info()

By calling .vertices_info() the user can either define a list of vertices to recieve info about. Here we will use the get_vertices_type() method to extract a list of SITE3 Vertex_Types and use the list to get vertices information.

defined_verts_list = cfg.graph.vertices_info(vert_list=cfg.graph.get_vertices_type(v_type=Vertex_Type.SITE3))
pp.pprint(defined_verts_list)

{(0.0, 9.0): (<Vertex_Type.SITE3: 4>, 1),
 (1.0, 2.0): (<Vertex_Type.SITE3: 4>, 1),
 (2.0, 1.0): (<Vertex_Type.SITE3: 4>, 2),
 (2.0, 5.0): (<Vertex_Type.SITE3: 4>, 1),
 (4.0, 6.0): (<Vertex_Type.SITE3: 4>, 1),
 (5.0, 6.0): (<Vertex_Type.SITE3: 4>, 1),
 (7.0, 3.0): (<Vertex_Type.SITE3: 4>, 1)}

We can also provide no vertices list and recieve all vertices in the graph

all_verts_list = cfg.graph.vertices_info()
pp.pprint(all_verts_list)

{(0.0, 6.0): (<Vertex_Type.BASIC: 0>, 1),
 (0.0, 7.0): (<Vertex_Type.ORIGIN: 1>, 1),
 (0.0, 8.0): (<Vertex_Type.BASIC: 0>, 1),
 (0.0, 9.0): (<Vertex_Type.SITE3: 4>, 1),
 (1.0, 0.0): (<Vertex_Type.BASIC: 0>, 1),
 (1.0, 2.0): (<Vertex_Type.SITE3: 4>, 1),
 (1.0, 3.0): (<Vertex_Type.SITE1: 2>, 1),
 (1.0, 5.0): (<Vertex_Type.BASIC: 0>, 1),
 (1.0, 7.0): (<Vertex_Type.BASIC: 0>, 1),
 (2.0, 0.0): (<Vertex_Type.BASIC: 0>, 1),
 (2.0, 1.0): (<Vertex_Type.SITE3: 4>, 3),
 (2.0, 3.0): (<Vertex_Type.BASIC: 0>, 1),
 (2.0, 5.0): (<Vertex_Type.SITE3: 4>, 1),
 (2.0, 8.0): (<Vertex_Type.BASIC: 0>, 1),
 (3.0, 0.0): (<Vertex_Type.SITE2: 3>, 1),
 (3.0, 2.0): (<Vertex_Type.SITE2: 3>, 1),
 (3.0, 4.0): (<Vertex_Type.SITE1: 2>, 1),
 (3.0, 6.0): (<Vertex_Type.BASIC: 0>, 1),
 (3.0, 7.0): (<Vertex_Type.BASIC: 0>, 1),
 (4.0, 1.0): (<Vertex_Type.BASIC: 0>, 1),
 (4.0, 6.0): (<Vertex_Type.SITE3: 4>, 1),
 (5.0, 0.0): (<Vertex_Type.BASIC: 0>, 1),
 (5.0, 2.0): (<Vertex_Type.BASIC: 0>, 1),
 (5.0, 6.0): (<Vertex_Type.SITE3: 4>, 1),
 (5.0, 7.0): (<Vertex_Type.BASIC: 0>, 1),
 (6.0, 0.0): (<Vertex_Type.BASIC: 0>, 1),
 (6.0, 2.0): (<Vertex_Type.BASIC: 0>, 1),
 (7.0, 0.0): (<Vertex_Type.SITE1: 2>, 1),
 (7.0, 1.0): (<Vertex_Type.BASIC: 0>, 1),
 (7.0, 3.0): (<Vertex_Type.SITE3: 4>, 1),
 (7.0, 4.0): (<Vertex_Type.BASIC: 0>, 1)}

---

Vertex_Type Object

Vertex_Type is used to store and define each location type on the graph. These variables will contain spatial location information, as well as reward amount and time to extract. SITEs 1,2 and 3 can contain varying reward amounts.

Vertex_Type.BASIC - BASIC is a location in space, neither a SITE nor the ORIGIN (regular point on the graph)

Vertex_Type.ORIGIN - starting point for workers

Vertex_Type.OTHER

Vertex_Type.OTHER2

Vertex_Type.SITE1 - point on graph with reward

Vertex_Type.SITE2 - point on graph with reward

Vertex_Type.SITE2 - point on graph with reward

---

Vertex Object

The Vertex object allows users to create vertices for that graph by defining characteristics such as coordinates (x,y), Vertex_Type, rewards available at given site, site expiration time, and time to aquire. Below we create a vertex object and assign attributes.

verts = lgtool.Vertex(x=4,y=5, v_type=Vertex_Type.SITE1, reward=200)
verts.info()

[(4, 5), <Vertex_Type.SITE1: 2>]

Vertex.info()

Using .info() we can view the Vertex object we just created, along with it’s defining characteristics

verts.info()

[(4, 5), <Vertex_Type.SITE1: 2>]

accessible_types()

We can also use .accessible_types() to determine which Vertex_Types are accessible

verts.accessible_types()

[<Vertex_Type.SITE1: 2>, <Vertex_Type.SITE2: 3>, <Vertex_Type.SITE3: 4>]

---

Worker_Type Object

Worker_Type holds the variable information the three types of workers: WORKER1, WORKER2, and WORKER3. Each worker is assigned an order, and this can be viewed by calling .worker_types on the configuration ocject created in the initial setup.

In the Configuration-Object section above you can see how to get the cost rate assigned to each worker for the configuration.

cfg.worker_types

[<Worker_Type.WORKER1: 0>, <Worker_Type.WORKER2: 1>, <Worker_Type.WORKER3: 2>]

---

Worker Object

The Worker object contains the information about worker type and associated cost rate.

# output still in progress
wrker_obj = lgtool.Worker(w_type=Worker_Type.WORKER2, rates=5)

---