Core Types
Graph
GraphUtils.AbstractCustomNGraph
— Typeabstract type AbstractCustomNGraph{G,N,ID} <: AbstractCustomGraph
An abstract Custom Graph type, with an underlying graph of type G
, nodes of type N
with ids of type ID
. All concrete subtypes CG<:AbstractCustomNGraph
must implement the following methods: get_graph(g::CG)
,get_vtx_ids(g::CG)
, get_vtx_map(g::CG)
, and get_nodes(g::CG)
. These methods are implemented by default if g::CG
has the following fields:
graph ::CG
nodes ::Vector{N}
vtx_map ::Dict{ID,Int}
vtx_ids ::Vector{ID}
Abstract subtypes of AbstractCustomNGraph{G,N,ID}
include:
AbstractCustomNEGraph{G,N,E,ID}
- a graph with custom edges of typeE
GraphUtils.get_graph
— Functionget_graph(g::AbstractCustomNGraph{G,N,ID})
return the underlying graph of type G
.
GraphUtils.get_vtx_ids
— Functionget_vtx_ids(g::AbstractCustomNGraph{G,N,ID})
return the vector Vector{ID}
of g
's unique vertex ids.
GraphUtils.get_vtx_map
— Functionget_vtx_map(g::AbstractCustomNGraph{G,N,ID})
return a data structure (e.g, a 'Dict{ID,Int}') mapping node id to node index.
GraphUtils.get_nodes
— Functionget_nodes(g::AbstractCustomNGraph{G,N,ID})
Return the vector Vector{N}
of g
's nodes.
GraphUtils.node_val
— Functionnode_val(node)
Return the value associated with a node. Part of the optional node interface for nodes in an AbstractCustomNGraph
.
GraphUtils.edge_val
— Functionedge_val(edge)
Returns the value associated with an edge. Part of the optional interface for edges in an AbstractCustomNEGraph
.
GraphUtils.edge_source
— Functionedge_source(edge)
Returns the ID of the source node of an edge. Part of the required interface for edges in an AbstractCustomNEGraph
.
GraphUtils.edge_target
— Functionedge_target(edge)
Returns the ID of the target node of an edge. Part of the required interface for edges in an AbstractCustomNEGraph
.
GraphUtils.replace_node!
— Functionreplace_node!(g::AbstractCustomNGraph{G,N,ID},node::N,id::ID) where {G,N,ID}
Replace the current node associated with id
with the new node node
.
GraphUtils.add_node!
— Functionadd_node!(g::AbstractCustomNGraph{G,N,ID},node::N,id::ID) where {G,N,ID}
Add node
to g
with associated id
.
GraphUtils.make_node
— Functionmake_node(g::AbstractCustomNGraph{G,N,ID},val,id)
Construct a node of type N
from val and id. This method must be implemented for whatever custom node type is used.
GraphUtils.make_edge
— Functionmake_edge(g::G,u,v,val) where {G}
Construct an edge u → v
of type _edge_type(g)
based on val. Default behavior is to throw an error.
GraphUtils.add_child!
— Functionfunction add_child!(graph,parent,node,id)
add node child
to graph
with id id
, then add edge parent
→ child
GraphUtils.add_parent!
— Functionfunction add_parent!(graph,child,parent,id)
add node parent
to graph
with id id
, then add edge parent
→ child
GraphUtils.rem_node!
— Functionrem_node!
removes a node (by id) from g. Note about LightGraphs.rem_vertex!: "internally the removal is performed swapping the vertices v
and nv(G)
, and removing the last vertex nv(G)
from the graph"
GraphUtils.is_terminal_node
— Functionisroot_node(G,v)
Inputs: G
- graph v
- query vertex
Outputs: returns true
if vertex v has no outneighbors
GraphUtils.get_all_root_nodes
— Functionget_all_root_nodes
GraphUtils.get_all_terminal_nodes
— Functionget_all_terminal_nodes
GraphUtils.get_dist_matrix
— Functionget_dist_matrix(G)
Get the distance matrix corresponding to the edge weights of a graph
GraphUtils.topological_sort
— Functiontopological_sort(G)
Returns a topological sort of the vertices of a graph, with the property that v1 < v2 iff there is not forward path through the graph from v2 to v1. G must be non-cyclic. Can handle disjoint graphs.
Tree
GraphUtils.AbstractCustomNTree
— Typeabstract type AbstractCustomNTree{N,ID} <: AbstractCustomNDiGraph{N,ID}
Abstract custom graph type with tree edge structure.
GraphUtils.AbstractTreeNode
— Typeabstract type AbstractTreeNode{E,ID}
E is element type, ID is id type
GraphUtils.validate_tree
— Functionvalidate_tree(n::AbstractTreeNode)
Ensure that the transform tree is in fact a tree–no cycles, and no duplicate ids
GraphUtils.validate_embedded_tree
— Functionvalidate_embedded_tree(graph,f=v->get_node(graph,v))
Verify that all graph edges are mirrored by the parent-child structure stored in the nodes.
Factory World
GraphUtils.construct_vtx_map
— Functionconstruct_vtx_map(vtxs,dims)
Returns a matrix M
such that MV[i,j] == v
, where v is the index of the vertex whose coordinates are (i,j)
Arguments:
- vtxs : a list of integer coordinates
- dims : the dimensions of the grid
GraphUtils.construct_edge_cache
— Functionconstruct_edge_cache(vtxs,vtx_map)
Returns a cache
such that cache[v] = {(0,1),(0,0),...}
, the set of all valid directions in which a robot may move from vertex v
.
Arguments:
- vtxs : a list of integer coordinates
- vtxmap : a matrix such that `vtxmap[i,j] = v
, where
vtxs[i,j] = v`.
GraphUtils.construct_expanded_zones
— Functionconstruct_expanded_zones(vtxs,vtx_map,pickup_zones,dropoff_zones;
shapes=[(1,1),(1,2),(2,1),(2,2)])
A utility for constructing drop-off/pick-up zones where large-footprint objects need to be delivered. Returns a dictionary mapping vertices to a dict of shape=>vtxs for expanded size delivery zones. For each starting vertex, the expanded zone is selected as the appropriately sized region that overlaps with the original vertex, does not overlap with any obstacles, and has minimal overlap with all other vertices in the zone list.
Arguments:
- vtxs : a list of integer coordinates
- vtxmap : a matrix such that `vtxmap[i,j] == v
, where
vtxs[v] == (i,j)` - zones : a list of integer vertex indices identifying the zones to be expanded
GraphUtils.validate_expanded_zones
— Functionvalidate_expanded_zones(vtx_map,expanded_zones)
Verify that all vertices of each expanded zone do not overlap with obstacle regions, and that each expanded zone contains the original vertex.
GraphUtils.SparseDistanceMatrix
— TypeSparseDistanceMatrix{G,M}
Stores a graph and sparse distance matrix. When the distance matrix is queried for the distance between start
and goal
, it first checks that this distance has been computed. If not, it will first compute the distances from all nodes to goal
before returning the queried distance.
GraphUtils.remap_idx
— Functionremap_idx(m::SparseDistanceMatrix,v,config)
Maps an index and configuration from the base grid to the transformed grid represented by m.graph. config
represents the position of the query pt relative to the coordinates that correspond to v
.
GraphUtils.recompute_cached_distances!
— Functionrecompute_cached_distances!
Recompute all cached distances (important if, e.g., the graph has been modified)
GraphUtils.config_index_to_tuple
— Functionconfig_index_to_tuple(shape::Tuple{Int,Int}, idx::Int)
Convert a config index to a tuple coordinate representation. Assumes the following layout for config indices given shape (m,n)
: 1 2 ... n ____________________________ 1 | 1 2 ... n 2 | n+1 n+2 ... 2n ... | m | (m-1)n+1 (m-1)n+2 ... m*n
GraphUtils.RemappedDistanceMatrix
— TypeRemappedDistanceMatrix
Stores a distance matrix that corresponds to a "shifted" grid graph with a new configuration space layered over a base graph. The shape m.s
of m::RemappedDistanceMatrix
defines the convolution kernel used to generate the modified.
GraphUtils.GridFactoryEnvironment
— TypeGridFactoryEnvironment
GraphUtils.construct_regular_factory_world
— Functionconstruct_regular_factory_world()
Returns a GridFactoryEnvironment
with regularly spaced obstacle regions surrounded by alternating pick-up and drop-off locations.
Keyword Arguments:
- nobstaclesx = 2 : number of obstacles in x direction
- nobstaclesy = 2 : number of obstacles in y direction
- obs_width = [2;2] : obstacle width in both directions
- obs_offset = [1;1] : width of buffer region around each obstacle
- env_pad = [1;1] : env pad
- env_scale = 0.5 : determines the width of each grid cell when the coordinates of the environment are transformed to continuous Cartesian space.
- transition_time = 2.0 : determines the nominal travel time for a robot to move from one grid cell to an adjacent one.
GraphUtils.construct_factory_env_from_vtx_grid
— Functionconstruct_factory_env_from_vtx_grid(vtx_grid;kwargs...)
Arguments:
- vtxgrid : a matrix such that `vtxgrid[i,j] > 0` represents free space, otherwise an obstacle.
Keyword Arguments:
- cell_width = 0.5 : determines the width of each grid cell when the coordinates of the environment are transformed to continuous Cartesian space.
- transition_time = 2.0 : determines the nominal travel time for a robot to move from one grid cell to an adjacent one.
- pickup_zones = Int[] : a list of vertices that represent pick-up points
- dropoff_zones = Int[] : a list of vertices that represent drop-off points
GraphUtils.construct_factory_env_from_indicator_grid
— Functionconstruct_factory_env_from_indicator_grid
Args: * grid: an indicator grid whose zero entries denote free space (non-zero denotes obstacle)