Xbt

• Index

Contents

• Functions
• Fields

Modules

• xbt.util
• xbt.path
• xbt.graph
• xbt

Module xbt.graph

Generating and finding paths in graphs.

Info:

• Copyright: 2015, Matthias Hölzl
• License: MIT, see the file LICENSE.md.
• Author: Matthias Hölzl

Functions

node_dist (n1, n2)	Compute the distance between two nodes.
diameter (nodes)	Compute the diameter of a graph.
min_node_distance (node, nodes)	Compute the minimum distance between a node and a set of nodes.
maxmin_distance (nodes)	Compute the maximum of the minimal node distances.
generate_all_edges (nodes)	Generate all possible edges between members of nodes.
make_short_edge_generator (slack)	Build a generator that builds all short edges between nodes.
generate_graph (nodes, size, edge_gen)	Generate a graph.
copy (g)	Copy a graph.
copy_badly (g, p_del, p_gen, err, connect)	Copy a graph, introducing errors in the edge rewards.
outnodes (g, n)	All nodes reachable via an outgoing edge.
generate_table (size, init_value)	Generate a square two-dimensional table.
delete_transition (g, from, to)	Delete a transition from a graph.
floyd (g)	Compute the tables for computing all paths in a graph.
absolute_difference (rewards1, rewards2)	Compute the difference in rewards between two rewards tables of the same size.
different_choices (next1, next2)	Compute the number of different choices for two next tables.
path (g, n1, n2)	Compute the cheapest path between nodes in a graph.
pathstring (g, n1, n2)	Return the shortest path between nodes in a graph as string.
update_edge_reward (g, sample)	Update the reward of an edge based on a sample value.

Fields

print_trace_info	Print information about the execution of some graph functions.
initial_edge_occurrences	When updating a graph we may sometimes want to bias the results towards the initial value, so that the first few samples don't have an undue effect on the graph if the environment is very noisy.
failure_cost	The cost of a failed action.

Functions

node_dist (n1, n2)

Compute the distance between two nodes.

Parameters:

• n1 The first node.
• n2 The second node.

Returns:

The distance between n1 and n2.

diameter (nodes)

Compute the diameter of a graph. The diameter of (the nodes of) a graph $g$ is the maximum distance between any two nodes of $g$. This function accepts a set of nodes, /not/ a graph.

Parameters:

• nodes The nodes of a graph.

Returns:

The diameter of the graph.

min_node_distance (node, nodes)

Compute the minimum distance between a node and a set of nodes. If node appears in the set of nodes it is ignored, i.e., the result is always positive. If nodes is empty or all members of nodes are equal to n, the value math.huge is returned.

Parameters:

• node A node.
• nodes A set of nodes.

Returns:

The minimum distance between node and any element of nodes

maxmin_distance (nodes)

Compute the maximum of the minimal node distances. Ccompute the maximum of the minimal distances between any two members of a set of nodes. Inserting all edges of length no bigger than this value ensures that every node in the graph is connected to at least one other node (although the graph may still consist of many disconnected components).

Parameters:

• nodes The nodes of a graph.

Returns:

The maximum of the minimum of the distances between nodes.

generate_all_edges (nodes)

Generate all possible edges between members of nodes. When passed as edge generator to generate_graph this will build the complete graph for the generated nodes.

Parameters:

• nodes The nodes of a graph.

Returns:

All possible edges for the nodes.

make_short_edge_generator (slack)

Build a generator that builds all short edges between nodes. This function returns a function that is suitable as edge generator for generate_graph. This generator builds all edges that are shorter than slack times the maxmin_distance between nodes. Setting slack to a value below 1 will ensure that the graph contains isolated nodes (and in general consists of many disconnected components).

Parameters:

• slack A factor by which the generated edges may be longer than the maxmin distance.

Returns:

All short edges for nodes.

generate_graph (nodes, size, edge_gen)

Generate a graph. Generate a graph with the given number of nodes.

Parameters:

• nodes An array of nodes or the number of nodes in the graph. If a node array is passed as argument, each node must have x and y attributes that describe its physical location. Each node is assigned an integer attribute id that corresponds to its position in the array of nodes, a type attribute that has the value "node", and an array of the same size as the nodes table that contains nil for indices of nodes for which there is no edge, and the transition for indices for which a transition exists. The entries in this array have to be filled in by the edge_gen.
• size The size of the are in which the nodes are located. May either be a number, in which case both x and y dimension are set to this number, or a pair {x=x, y=y} that specifies the dimensions for x and y separately. Defaults to 500. Ignored when an arrayo of nodes is passed in.
• edge_gen A function that generates the edges for the graph given the table of nodes. The generator has to add each edge to the correct index of the edges array of its start node.

copy (g)

Copy a graph. This function copies a graph, taking care of the cycles appearing in the graph structure. It copys only the default attributes of a graph and ignores any attributes stored by the user.

Parameters:

• g

copy_badly (g, p_del, p_gen, err, connect)

Copy a graph, introducing errors in the edge rewards.

Parameters:

• g The graph to copy.
• p_del The probability with which existing edges are deleted. Defaults to 0.1.
• p_gen The probability with which new edges will be introduced. Defaults to 0.05.
• err A function that computes the error for the new edge reward, based on the old reward, or the standard deviation of a normal distribution with which the existing rewards are modified. Defaults to 1/20 the diameter of g.
• connect If truthy ensure that the graph remains connected. This is currently an expensive operation.

outnodes (g, n)

All nodes reachable via an outgoing edge. Compute all nodes of g that are directly reachable from n via an outgoing edge.

Parameters:

• g A graph.
• n Either a node or a node id.

generate_table (size, init_value)

Generate a square two-dimensional table. Genrate a table with size*size entries, each of which has the value init_value.

Parameters:

• size The size of one table dimension.
• init_value The initial value of all entries.

Returns:

A freshly allocated table.

delete_transition (g, from, to)

Delete a transition from a graph.

Parameters:

• g
• from
• to

floyd (g)

Compute the tables for computing all paths in a graph. Uses the Floyd-Warshall dynamic-programming algorithm to compute tables rewards and next. rewards's entries at position [i][j] contain the (weighted) reward of the cheapest path between nodes i and j (where i and j are the node ids or, equivalently, their position in the nodes array of the graph). The reward is taken from the transition's reward attribute. The entry of next at this position is the next node on the shortest path between the two nodes. These tables are then added to g as the rewards and next attributes; if these attributes already exist they are not taken into account and overwritten. The algorithm has time complexity O(#g.nodes^3) and quadratic space complexity.

Parameters:

• g The graph whose tables are computed.

Returns:

1. The rewards table.
2. The next table.

absolute_difference (rewards1, rewards2)

Compute the difference in rewards between two rewards tables of the same size.

Parameters:

• rewards1
• rewards2

different_choices (next1, next2)

Compute the number of different choices for two next tables.

Parameters:

• next1
• next2

path (g, n1, n2)

Compute the cheapest path between nodes in a graph. Compute the cheapest path between two nodes in a graph. The first invocation of this function uses floyd to compute the rewards and next tables for g and therefore has time complexity O(#g.nodes^3) and quadratic space complexity. Subsequent invocations have linear complexity in the size of the path.

Parameters:

• g The graph.
• n1 The start node.
• n2 The end node.

Returns:

An array containing the ids of the nodes on the cheapest path between 'n1' and 'n2'.

pathstring (g, n1, n2)

Return the shortest path between nodes in a graph as string. Compute the sortest path between two nodes in a graph using the function path and return the result as a string.

Parameters:

• g The graph.
• n1 The start node.
• n2 The end node.

Returns:

A string representation of the shortest path.

update_edge_reward (g, sample)

Update the reward of an edge based on a sample value.

Parameters:

• g
• sample

Fields

print_trace_info

Print information about the execution of some graph functions.

initial_edge_occurrences

When updating a graph we may sometimes want to bias the results towards the initial value, so that the first few samples don't have an undue effect on the graph if the environment is very noisy. Therefore we can adjust how often the update algorithm thinks that it has already seen the initial reward of the edge before the first update.

failure_cost

The cost of a failed action. The reward of a failed navigation action is the negated value of the cost.