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
andn2
. - 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. Ifnodes
is empty or all members ofnodes
are equal ton
, the value math.huge is returned.Parameters:
- node A node.
- nodes A set of nodes.
Returns:
-
The minimum distance between
node
and any element ofnodes
- 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
andy
attributes that describe its physical location. Each node is assigned an integer attributeid
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 containsnil
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 theedge_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.
- 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
- 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 fromn
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 valueinit_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 nodesi
andj
(wherei
andj
are the node ids or, equivalently, their position in thenodes
array of the graph). The reward is taken from the transition'sreward
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 tog
as therewards
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:
-
The
rewards
table. - 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 forg
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.