MATES 3.0-rc2

org.mates.sim.network
Class Topology

java.lang.Object
  extended byorg.mates.sim.network.Topology
All Implemented Interfaces:
Processor

public class Topology
extends java.lang.Object
implements Processor

Class for storing the network topology.

Author:
Evan Sultanik

Nested Class Summary
 class Topology.AllPairsShortestPathData
          Class containing both the distances and route table for the shortest path between all pairs of hosts.
 class Topology.SingleSourceShortestPathData
          Class containing both the distances and routes for the shortest path between one host and all other hosts.
protected  class Topology.TopologyBundle
          Specialized threading bundle for parallelized updating of the topology.
 
Constructor Summary
Topology()
          Default constructor for a network of no hosts.
Topology(Topology t)
          Copy constructor; makes sure everything is cloned properly.
Topology(java.util.Vector hosts, LinkModel link_model)
          Creates a new topology from a given set of hosts, determining their connectivity from the provided link model.
 
Method Summary
 Topology.AllPairsShortestPathData allPairsShortestPath()
          Returns the all pairs shortest path matrix for this topology, calculated using Floyd and Warshall's algorithm.
 int calculateDiameter()
          Calculates the diameter of this topology.
static int calculateDiameter(double[][] graph)
          Calculates the diameter of a graph.
 double calculateEccentricity(Host host)
          Returns the eccentricity of a host.
static int calculateRadius(double[][] graph, int vertex)
          Calculates the radius of the provided graph (represented by an adjacency matrix) from a specific vertex's perspective.
 int calculateRadius(Host host)
          Calculates the radius of a specific host in this topology.
 double[] calculateStationaryDistribution()
          Calculates the stationary distribution for this topology using the PageRank iterative improvement approximation algorithm.
static double[] calculateStationaryDistribution(double[][] adjacency)
          Calculates the stationary distribution of a graph (represented as an adjacency matrix) using the PageRank iterative improvement approximation algorithm.
static double[] calculateStationaryDistribution(double[][] adjacency, int iterations, double damping_factor)
          Calculates the stationary distribution of a graph (represented as an adjacency matrix) using the PageRank iterative improvement approximation algorithm.
 double[][] getAdjacency()
          Returns a weighted adjacency matrix representation of the topology.
 java.util.Vector getCommunicableHosts(Host host)
          Returns a vector of all of the hosts that the provided host can communicate with.
 int[] getDegreeDistribution()
          Returns the current degree distribution of the topology.
 Host getHostByIndex(int index)
          Accessor function for a host in the topology, based on its index.
 int getHostIndex(Host host)
          Returns the index of the provided host.
 java.lang.String[] getHostNames()
          Returns an array of the names of the hosts in this topology.
 double getLinkQuality(Host host1, Host host2)
          Returns the link quality between two hosts in the topology.
 java.util.Vector getNeighbors(Host host)
          This is equivalent to getNeighborsHostCanTalkTo(Host).
 java.util.Vector getNeighborsHostCanHear(Host host)
          Returns a vector of all of a host's neighbors that are capable of sending messages to the provided host.
 java.util.Vector getNeighborsHostCanTalkTo(Host host)
          Returns a vector of all of a host's neighbors that are capable of receiving messages from the provided host.
 int getNumHosts()
          Returns the number of hosts in the topology.
static int[] getRoute(int[][] predecessorMatrix, int i, int j)
          Returns an array of integers representing the shortest path (i.e.
 int numCommunicableHosts(Host host)
          Returns the number of hosts that the provided host is connected to.
static int[][] predecessorMatrixToRouteTable(int[][] predecessorMatrix)
          Converts a predecessor matrix into a route table.
 void process(Bundle bundle)
          Callback function for processing a Topology.TopologyBundle.
 Topology.SingleSourceShortestPathData singleSourceShortestPath(Host host)
          Calculates the shortest path from host to every other host in the network, using Dijkstra's algorithm implemented with a FibonacciHeap.
 void update(Host host1, Host host2, double link)
          Manually updates the link quality between two hosts.
 void update(java.util.Vector hosts, LinkModel link_model)
          Updates this topology with a new set of hosts.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Topology

public Topology()
Default constructor for a network of no hosts.


Topology

public Topology(java.util.Vector hosts,
                LinkModel link_model)
Creates a new topology from a given set of hosts, determining their connectivity from the provided link model.

See Also:
update(Vector, LinkModel)

Topology

public Topology(Topology t)
Copy constructor; makes sure everything is cloned properly.

Method Detail

process

public void process(Bundle bundle)
Callback function for processing a Topology.TopologyBundle. This function is called by threads created by an internal instance of a BatchProcessor.

Specified by:
process in interface Processor

update

public void update(java.util.Vector hosts,
                   LinkModel link_model)
Updates this topology with a new set of hosts. Connectivity is determined from the given link model.


getHostNames

public java.lang.String[] getHostNames()
Returns an array of the names of the hosts in this topology.

See Also:
Host.getName()

getDegreeDistribution

public int[] getDegreeDistribution()
Returns the current degree distribution of the topology. This array will always be of size getNumHosts()+1. If there are no hosts in the topology, null is returned. The ith element of the returned array will be set to the number of hosts that have degree i. The degree of a host is the number of outgoing edges from it. For example, if getDegreeDistribution()[0] == 5, then there are 5 hosts in the topology with no outgoing edges.


getRoute

public static int[] getRoute(int[][] predecessorMatrix,
                             int i,
                             int j)
Returns an array of integers representing the shortest path (i.e. route) from i to j. The first element of the array will always be i (i.e. the length of the returned array will always be greater than or equal to 1). If no route exists between i and j, the length of the route will be exactly 1. If a route does exist, the last element of the returned array will be equal to j.


predecessorMatrixToRouteTable

public static int[][] predecessorMatrixToRouteTable(int[][] predecessorMatrix)
Converts a predecessor matrix into a route table.


singleSourceShortestPath

public Topology.SingleSourceShortestPathData singleSourceShortestPath(Host host)
Calculates the shortest path from host to every other host in the network, using Dijkstra's algorithm implemented with a FibonacciHeap.


allPairsShortestPath

public Topology.AllPairsShortestPathData allPairsShortestPath()
Returns the all pairs shortest path matrix for this topology, calculated using Floyd and Warshall's algorithm.


calculateEccentricity

public double calculateEccentricity(Host host)
Returns the eccentricity of a host. This is the length of the longest geodesic (i.e. shortest path) from host to any other host in the network.


calculateRadius

public static int calculateRadius(double[][] graph,
                                  int vertex)
Calculates the radius of the provided graph (represented by an adjacency matrix) from a specific vertex's perspective. Note that this is different than the eccentricity of a vertex; this function basically calculates the maximum depth of a depth-first traversal of the graph starting from vertex.

Parameters:
graph - an adjacency matrix representation of a graph
vertex - the index of the vertex (with respect to its representation in the adjacency matrix)
Returns:
the eccentricity of the vertex. 0 is returned on error.

calculateDiameter

public static int calculateDiameter(double[][] graph)
Calculates the diameter of a graph. In other words, this function returns the length of the longest shortest path in the graph.


calculateDiameter

public int calculateDiameter()
Calculates the diameter of this topology.


calculateRadius

public int calculateRadius(Host host)
Calculates the radius of a specific host in this topology.

See Also:
calculateRadius(double[][], int)

update

public void update(Host host1,
                   Host host2,
                   double link)
Manually updates the link quality between two hosts. If the hosts are not already present in the topology, they are added.


getNeighborsHostCanHear

public java.util.Vector getNeighborsHostCanHear(Host host)
Returns a vector of all of a host's neighbors that are capable of sending messages to the provided host. Note that this vector will never include the host itself, even if the topology has loops. This is because it is assumed that a host can always talk to itself. Also, note that this function is not symmetric; the fact that host x can "hear" host y does not imply that y can hear x.

See Also:
getNeighborsHostCanTalkTo(Host)

getNeighborsHostCanTalkTo

public java.util.Vector getNeighborsHostCanTalkTo(Host host)
Returns a vector of all of a host's neighbors that are capable of receiving messages from the provided host. Note that this vector will never include the host itself, even if the topology has loops. Also, note that this function is not symmetric; the fact that host x can "talk to" host y does not imply that y can talk to x.

See Also:
getNeighborsHostCanHear(Host)

getNeighbors

public java.util.Vector getNeighbors(Host host)
This is equivalent to getNeighborsHostCanTalkTo(Host).


numCommunicableHosts

public int numCommunicableHosts(Host host)
Returns the number of hosts that the provided host is connected to. In other words, the number of hosts which are on a directed path originating from the provided host. Note that this count never includes the provided host, and will therefore always be greater than or equal to 0.


getCommunicableHosts

public java.util.Vector getCommunicableHosts(Host host)
Returns a vector of all of the hosts that the provided host can communicate with. Note that the resulting Vector will never include the host itself, since it is assumed evident that a host can always talk to itself.


getHostByIndex

public Host getHostByIndex(int index)
Accessor function for a host in the topology, based on its index. Returns null on error.


getHostIndex

public int getHostIndex(Host host)
Returns the index of the provided host.

Returns:
the indes of the provided host; -1 on error.

getAdjacency

public double[][] getAdjacency()
Returns a weighted adjacency matrix representation of the topology.


getNumHosts

public int getNumHosts()
Returns the number of hosts in the topology.


getLinkQuality

public double getLinkQuality(Host host1,
                             Host host2)
Returns the link quality between two hosts in the topology.

Throws:
java.lang.IllegalArgumentException - if either of the provided hosts is not in this topology.

calculateStationaryDistribution

public double[] calculateStationaryDistribution()
Calculates the stationary distribution for this topology using the PageRank iterative improvement approximation algorithm.


calculateStationaryDistribution

public static double[] calculateStationaryDistribution(double[][] adjacency)
Calculates the stationary distribution of a graph (represented as an adjacency matrix) using the PageRank iterative improvement approximation algorithm. This function simply calls calculateStationaryDistribution(double[][], int, double) with adjacency.length*100 iterations and a damping factor of 0.15.


calculateStationaryDistribution

public static double[] calculateStationaryDistribution(double[][] adjacency,
                                                       int iterations,
                                                       double damping_factor)
Calculates the stationary distribution of a graph (represented as an adjacency matrix) using the PageRank iterative improvement approximation algorithm.

Parameters:
adjacency - the adjacency matrix representation of the graph
iterations - the number of iterations to run the algorithm
damping_factor - damping factor required by the PageRank algorithm

MATES 3.0-rc2

Submit a bug or request a feature
http://mates.sourceforge.net/

Copyright 2004 Evan Sultanik