net.aerith.misao.util
Class Graph

java.lang.Object
  |
  +--net.aerith.misao.util.Graph

public class Graph

extends java.lang.Object

The Graph represents a graph which consists of some nodes and branches connecting the nodes.

Field Summary

protected boolean[][]	branch The branch[i][j] is true if node i and j is directly connected.
private int	max_steps The maximum steps to search, used in method checkReachableIndexes.
protected int	number_of_nodes The number of nodes.
private boolean[]	reached_flag The reached_flag[i] is true if node i is reached already, used in method checkReachableIndexes.

Constructor Summary

Graph(int nodes)
Constructs a Graph of the specified number of nodes.

Method Summary

private void	checkReachableIndexes(int index, int current_step) Checkes the reachable nodes.
void	connect(int i, int j) Connects the node i and j.
void	disconnect(int i, int j) Disconnects the node i and j.
int	getNodeCount() Gets the number of nodes.
int[]	getReachableIndexes(int index) Gets the list of indexes of nodes reachable from the specified node.
int[]	getReachableIndexesInStep(int index, int steps) Gets the list of indexes of nodes reachable from the specified node within the specified steps.
boolean	isConnected(int i, int j) Returns true if the node i and j are connected.
boolean	isReachable(int i, int j) Returns true if the node j is reachable from the node i.
boolean	isReachableInStep(int i, int j, int steps) Returns true if the node j is reachable from the node i within the specified steps.

Methods inherited from class java.lang.Object

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

Field Detail

number_of_nodes

protected int number_of_nodes

The number of nodes.

branch

protected boolean[][] branch

The branch[i][j] is true if node i and j is directly connected.

max_steps

private int max_steps

The maximum steps to search, used in method checkReachableIndexes.

reached_flag

private boolean[] reached_flag

The reached_flag[i] is true if node i is reached already, used in method checkReachableIndexes.

Constructor Detail

Graph

public Graph(int nodes)

Constructs a Graph of the specified number of nodes. No nodes are connected with the other nodes at first.

Parameters:

nodes - the number of nodes.

Method Detail

getNodeCount

public int getNodeCount()

Gets the number of nodes.

Returns:

the number of nodes.

connect

public void connect(int i,
                    int j)

Connects the node i and j.

Parameters:

i - the index of node to be connected.

j - the index of node to be connected.

disconnect

public void disconnect(int i,
                       int j)

Disconnects the node i and j.

Parameters:

i - the index of node to be disconnected.

j - the index of node to be disconnected.

isConnected

public boolean isConnected(int i,
                           int j)

Returns true if the node i and j are connected.

Parameters:

i - the index of node to check.

j - the index of node to check.

Returns:

true if the node i and j are connected.

isReachable

public boolean isReachable(int i,
                           int j)

Returns true if the node j is reachable from the node i.

Parameters:

i - the index of node to check.

j - the index of node to check.

Returns:

true if the node j is reachable from the node i.

isReachableInStep

public boolean isReachableInStep(int i,
                                 int j,
                                 int steps)

Returns true if the node j is reachable from the node i within the specified steps.

Parameters:

i - the index of node to check.

j - the index of node to check.

steps - the maximum steps to reach to node j from i.

Returns:

true if the node j is reachable from the node i within the specified steps.

getReachableIndexes

public int[] getReachableIndexes(int index)

Gets the list of indexes of nodes reachable from the specified node. The indexes to be returned are sorted.

Parameters:

index - the index of start node.

Returns:

the list of indexes of nodes reachable from the specified node.

getReachableIndexesInStep

public int[] getReachableIndexesInStep(int index,
                                       int steps)

Gets the list of indexes of nodes reachable from the specified node within the specified steps. The indexes to be returned are sorted.

Parameters:

index - the index of start node.

steps - the maximum steps to reach. In the case of -1, it means there is no limit of steps to reach.

Returns:

the list of indexes of nodes reachable from the specified node within the specified steps.

checkReachableIndexes

private void checkReachableIndexes(int index,
                                   int current_step)

Checkes the reachable nodes. It is recurrsively invoked in method getReachableIndexesInStep. The max_steps and reached_flag must be set properly before invoking this method.

Parameters:

index - the index of start node.

current_step - the current step.