gov.sandia.cognition.graph

Class GraphWalker<NodeNameType>

java.lang.Object

gov.sandia.cognition.graph.GraphWalker<NodeNameType>

Type Parameters:

NodeNameType - The datatype for the graph's nodes

public class GraphWalker<NodeNameType>
extends java.lang.Object

This class provides the core functionality for any random, deterministic, or probabilistic graph walking code as long as only one edge can be traversed from any given node (that is a depth-first or breadth-first can't be implemented by this as it doesn't permit a queue of nodes to visit, but only a single element "next node to visit").

Author:

jdwendt

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	GraphWalker.NextNodeSelector<NodeNameType> This interface defines the method needed by the GraphWalker class to implement all features of graph walking _except_ the algorithm used to select the next node to visit
static class	GraphWalker.RandomWalker<NodeNameType> This class implements the most simple walker which randomly selects from the available edges.

Constructor Summary

Constructors

Constructor and Description
GraphWalker(DirectedNodeEdgeGraph<NodeNameType> graph, GraphWalker.NextNodeSelector<NodeNameType> selector) Initializes a new graph walker with as-yet empty metrics
GraphWalker(DirectedNodeEdgeGraph<NodeNameType> graph, GraphWalker.NextNodeSelector<NodeNameType> selector, GraphMetrics<NodeNameType> metrics) Initializes a new graph walker with the input values

Method Summary

Modifier and Type	Method and Description
NodeNameType	getEndNode(int numSteps) Returns the last node reached on a walk of numSteps steps starting from current node
NodeNameType	getEndNode(NodeNameType startNode, int numSteps) Returns the last node reached on a walk of numSteps steps starting from startNode
java.util.Map<NodeNameType,java.lang.Integer>	getEndNodes(NodeNameType startNode, int numSteps, int numTries) After running numTries walk of numSteps starting from startNode, this returns a map where the keys are all nodes reached at the end and the values are the number of times those nodes were reached.
java.util.List<NodeNameType>	getPath(int numSteps) Returns the path traversed across numSteps steps of the walk from the current start node.
java.util.List<NodeNameType>	getPath(NodeNameType startNode, int numSteps) Returns the path traversed across numSteps steps of the walk from startNode
static int	probablisticSelect(DoubleArrayList weights, java.util.Random r) Helper method that returns the index of the probabilistically selected input weight.
void	setStartNode(int nodeId) Sets the starting node (by id) for the next step (or series of steps)
void	setStartNode(NodeNameType node) Sets the start node (by name) for the next step (or series of steps)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphWalker

public GraphWalker(DirectedNodeEdgeGraph<NodeNameType> graph,
                   GraphWalker.NextNodeSelector<NodeNameType> selector)

Initializes a new graph walker with as-yet empty metrics

Parameters:

graph - The graph to walk

selector - The algorithm to use to select the next node in a walk

GraphWalker

public GraphWalker(DirectedNodeEdgeGraph<NodeNameType> graph,
                   GraphWalker.NextNodeSelector<NodeNameType> selector,
                   GraphMetrics<NodeNameType> metrics)

Initializes a new graph walker with the input values

Parameters:

graph - The graph to walk

selector - The algorithm to use to select the next node in a walk

metrics - The metrics to use

Method Detail

setStartNode

public void setStartNode(int nodeId)

Sets the starting node (by id) for the next step (or series of steps)

Parameters:

nodeId - The node to start at

setStartNode

public void setStartNode(NodeNameType node)

Sets the start node (by name) for the next step (or series of steps)

Parameters:

node - The node to start at

getPath

public java.util.List<NodeNameType> getPath(int numSteps)

Returns the path traversed across numSteps steps of the walk from the current start node.

Parameters:

numSteps - The number of steps to take

Returns:

A list of numSteps node names (not necessarily distinct)

getPath

public java.util.List<NodeNameType> getPath(NodeNameType startNode,
                                            int numSteps)

Returns the path traversed across numSteps steps of the walk from startNode

Parameters:

startNode - The node to start from

numSteps - The number of steps to take

Returns:

A list of numSteps node names (not necessarily distinct)

getEndNode

public NodeNameType getEndNode(int numSteps)

Returns the last node reached on a walk of numSteps steps starting from current node

Parameters:

numSteps - The number of steps to take

Returns:

The node reached at the end of the walk

getEndNode

public NodeNameType getEndNode(NodeNameType startNode,
                               int numSteps)

Returns the last node reached on a walk of numSteps steps starting from startNode

Parameters:

startNode - The node to start from

numSteps - The number of steps to take

Returns:

the node reached at the end of the walk

getEndNodes

public java.util.Map<NodeNameType,java.lang.Integer> getEndNodes(NodeNameType startNode,
                                                                 int numSteps,
                                                                 int numTries)

After running numTries walk of numSteps starting from startNode, this returns a map where the keys are all nodes reached at the end and the values are the number of times those nodes were reached. The sum of all keys is numTries.

Parameters:

startNode - The node to start from on every path

numSteps - The number of steps to take on any path

numTries - The number of paths to run

Returns:

The end nodes (keys) with the number of times each was reached at the end (values)

probablisticSelect

public static int probablisticSelect(DoubleArrayList weights,
                                     java.util.Random r)

Helper method that returns the index of the probabilistically selected input weight. Note that the input weights need not be probabilities (sum to 1) as this will normalize the selection properly (without changing the input values)

Parameters:

weights - The relative weights of each choice

r - The instance of Random to use

Returns:

The index of the probabilistically chosen input weight