edu.gwu.csd.algorithm
Class MapToRing

java.lang.Object
  |
  +--gov.nist.antd.merlin.algorithm.AlgorithmTemplate
        |
        +--edu.gwu.csd.algorithm.GWUTemplate
              |
              +--edu.gwu.csd.algorithm.MapToRing

All Implemented Interfaces:

Algorithm, DMLDump

public class MapToRing

extends GWUTemplate

This algorithm is used to find a vertex mapping f[] and edge_to_path mapping from a Mesh topology graph ipG representing Ip layer (Upper Layer) to a WDM Ring topology (Lower Layer). creation Nov 29, 2001

Author:

Hwajung Lee

, borchert NIST , rouil NIST

Field Summary

(package private) static java.lang.String	ALGONAME
(package private) static int	CENTER
(package private) static int	CutSize
(package private) int[][][]	cutStack Initial Value -1
(package private) int	cutStackPosition Initial Value 0
(package private) int[][]	deleted Deleted Edge while finding an edge cut : Initial Value -1
(package private) int[]	dfs
(package private) int[]	dfsPath Tmp Stack :Initial Value -1
(package private) int[][]	dummyG
(package private) int[][]	edgeCut Initial Value -1
(package private) java.util.Hashtable	fakeAsKey This hashtable contains the mapping of real node to a sequence of nodes.
(package private) static int	FALSE
(package private) int[][]	fLeftStack Tmp Vertex Mapping :Initial Value -1
(package private) int[][]	fRightStack Tmp Vertex Mapping : Initial Value -1
(package private) int[][]	fStack Vertex Mapping :Initial Value -1
(package private) int	fStackPosition
(package private) int	giDebug
(package private) int	giEdgeCnt
(package private) int	giNodeCnt
(package private) int	giPathIndex
(package private) int[][]	gLeft G_left component divided by an edge cut set : Initial Value 0
(package private) int[][]	gppiPrtArr
(package private) int[][]	gRight G_right component divided by an edge cut set : Initial Value 0
(package private) int[][]	h Edge to Path Mapping : Initial Value 0
(package private) static int	INFINITE
(package private) int[][]	ipG Original Input Graph : Initial Value 0
(package private) static int	LEFT
(package private) int	matrixSize Size of the matrix.
(package private) static int	MAX
(package private) int	maxNodeIdx
(package private) static int	NIL
private java.lang.StringBuffer	outStr Contains the result of the algorithm.
(package private) int[][]	ppiEdgeArr
(package private) int[][]	ppiNodeArr
(package private) java.util.Hashtable	realAsKey This hashtable contains the mapping of real node to a sequence of nodes.
(package private) static int	RIGHT
(package private) int[][]	tmpIpG Working space for ipG : Initial Value 0
(package private) static int	TRUE

Fields inherited from class edu.gwu.csd.algorithm.GWUTemplate

listOfConnections, parameter

Fields inherited from class gov.nist.antd.merlin.algorithm.AlgorithmTemplate

Fields inherited from interface gov.nist.antd.optical.algorithm.Algorithm

ROUTING, RWA, UNKNOWN, WAVELENGTH

Constructor Summary

MapToRing()
Creates an instance of the algorithm with the default name.

Method Summary

private void	checkRing(Glass net, RingList ring) Checks if the network provides the ring topology that is needed.
void	deleteEdge(int[][] graph) Delete an edge from graph[][] and the updated graph[][] will be saved in tmpIpG[][].
void	dfSearch(int[][] graph, int chk)
int	doesNeedDummy(int[][] graph)
void	edgeToRing(int[][] tmpGraph, int flag, int fStackPosition)
java.util.Vector	execute(Glass net, java.util.Vector theListOfConnections, java.util.Vector theParameter) This method executes the algorithm.
private void	fillConnection(OpticalConnection conn, int[] nodeList) This method creates the datastructure behind the optical Connection.
int	findEdgeCutOf2(int[][] tmpGraph, int numOfNode) Find an edge cut set of size 2 and the result is saved in EdgeCut[CutSize][CutSize].
int	findInducedG(int[][] graph, int vertex, int flag) Find the LEFT or RIGHT component of graph, connected from the vertex, edgeCut[0][0] and saved gLeft[][] for the flag LEFT or gRIGHT[][] for the flag RIGHT.
int	findNumOfEdge(int[][] graph) Check the number of edges of the graph.
int	findNumOfNode(int[][] graph)
private void	generateOpticalRoutes(OpticalConnection[] connections) Generates the array if routes according to the connection request.
java.lang.String	getResultString() Returns the result string.
byte	getType() This algorithm is a Routing and Wavelength Algorithm for Ring topologies.
int	is2EdgeConnected(int[][] orgGraph)
int	isDummy(int s, int t)
int	isIncluded(int[][] graph, int node)
int	isRing(int[][] tmpGraph) Check whether the graph is ring or not.
int	loadTopologyData(java.lang.String[] args) Read the input out of a file.
static void	main(java.lang.String[] args)
void	map2toRing(int[][] graph, int flag, int numOfNode, int fStackPosition) void map2toRing(int graph[matrixSize][matrixSize], int flag, int fStackPosition)
void	merge2Rings(int[] vertexLeft, int[] vertexRight, int[][] edgeCut, int flag, int fStackPosition)
int	reachable(int[][] graph, int numOfNode)
int	reachableFromTo(int[][] graph, int numOfNode, int from, int to)
void	ringToRing(int[][] tmpGraph, int flag, int fStackPosition)
void	ringToRingOLD(int[][] graph, int flag)
int	run(java.lang.String[] args) Starts the final execution of the algorithm.
int[][]	theAlgorithm(int[][] topo, int[][] connections) This method is the startmethod of the algorithm out of SSF.

Methods inherited from class edu.gwu.csd.algorithm.GWUTemplate

config, customConfig, preComputeAlgorithm, toDML

Methods inherited from class gov.nist.antd.merlin.algorithm.AlgorithmTemplate

execute, getName, isDebug, setDebug, setName

Methods inherited from class java.lang.Object

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

Field Detail

INFINITE

static final int INFINITE

See Also:

Constant Field Values

MAX

static final int MAX

See Also:

Constant Field Values

NIL

static final int NIL

See Also:

Constant Field Values

TRUE

static final int TRUE

See Also:

Constant Field Values

FALSE

static final int FALSE

See Also:

Constant Field Values

LEFT

static final int LEFT

See Also:

Constant Field Values

CENTER

static final int CENTER

See Also:

Constant Field Values

RIGHT

static final int RIGHT

See Also:

Constant Field Values

CutSize

static final int CutSize

See Also:

Constant Field Values

matrixSize

int matrixSize

Size of the matrix.

ipG

int[][] ipG

Original Input Graph : Initial Value 0

tmpIpG

int[][] tmpIpG

Working space for ipG : Initial Value 0

gLeft

int[][] gLeft

G_left component divided by an edge cut set : Initial Value 0

gRight

int[][] gRight

G_right component divided by an edge cut set : Initial Value 0

fStack

int[][] fStack

Vertex Mapping :Initial Value -1

fLeftStack

int[][] fLeftStack

Tmp Vertex Mapping :Initial Value -1

fRightStack

int[][] fRightStack

Tmp Vertex Mapping : Initial Value -1

fStackPosition

int fStackPosition

h

int[][] h

Edge to Path Mapping : Initial Value 0

edgeCut

int[][] edgeCut

Initial Value -1

cutStack

int[][][] cutStack

Initial Value -1

cutStackPosition

int cutStackPosition

Initial Value 0

deleted

int[][] deleted

Deleted Edge while finding an edge cut : Initial Value -1

dummyG

int[][] dummyG

dfsPath

int[] dfsPath

Tmp Stack :Initial Value -1

dfs

int[] dfs

maxNodeIdx

int maxNodeIdx

giNodeCnt

int giNodeCnt

giEdgeCnt

int giEdgeCnt

giDebug

int giDebug

giPathIndex

int giPathIndex

gppiPrtArr

int[][] gppiPrtArr

ppiNodeArr

int[][] ppiNodeArr

ppiEdgeArr

int[][] ppiEdgeArr

fakeAsKey

java.util.Hashtable fakeAsKey

This hashtable contains the mapping of real node to a sequence of nodes. The Key is the sequential number and the value is the real node id.

realAsKey

java.util.Hashtable realAsKey

This hashtable contains the mapping of real node to a sequence of nodes. the Key is the real node id and the value is the sequential number.

outStr

private java.lang.StringBuffer outStr

Contains the result of the algorithm.

ALGONAME

static final java.lang.String ALGONAME

See Also:

Constant Field Values

Constructor Detail

MapToRing

public MapToRing()

Creates an instance of the algorithm with the default name.

Since:

1.1

Method Detail

run

public int run(java.lang.String[] args)

Starts the final execution of the algorithm.

Parameters:

args - The argumental array. The first argument is the filename.

Returns:

o if the algorithm stopped successfull, otherwise -1.

loadTopologyData

public int loadTopologyData(java.lang.String[] args)

Read the input out of a file. This method is used if this algorithm is called as stand alone program.

Parameters:

args - the argument string array of the main method

Returns:

0 if everuthing is ok; otherwise -1

map2toRing

public void map2toRing(int[][] graph,
                       int flag,
                       int numOfNode,
                       int fStackPosition)

void map2toRing(int graph[matrixSize][matrixSize], int flag, int fStackPosition)

Parameters:

graph - The topology graph.

flag -

numOfNode -

fStackPosition -

isRing

public int isRing(int[][] tmpGraph)

Check whether the graph is ring or not.

Parameters:

tmpGraph - the graph that has to be checked

Returns:

TRUE == 1 or FALSE == -1

findNumOfEdge

public int findNumOfEdge(int[][] graph)

Check the number of edges of the graph.

Parameters:

graph - The topology graph.

Returns:

The number of edges.

deleteEdge

public void deleteEdge(int[][] graph)

Delete an edge from graph[][] and the updated graph[][] will be saved in tmpIpG[][].

Parameters:

graph - The topology graph.

findEdgeCutOf2

public int findEdgeCutOf2(int[][] tmpGraph,
                          int numOfNode)

Find an edge cut set of size 2 and the result is saved in EdgeCut[CutSize][CutSize].

Parameters:

numOfNode - ???

Returns:

???

findInducedG

public int findInducedG(int[][] graph,
                        int vertex,
                        int flag)

Find the LEFT or RIGHT component of graph, connected from the vertex, edgeCut[0][0] and saved gLeft[][] for the flag LEFT or gRIGHT[][] for the flag RIGHT.

Parameters:

graph - The topology Graph

vertex - ???

flag - LEFT/RIGHT

Returns:

???

merge2Rings

public void merge2Rings(int[] vertexLeft,
                        int[] vertexRight,
                        int[][] edgeCut,
                        int flag,
                        int fStackPosition)

edgeToRing

public void edgeToRing(int[][] tmpGraph,
                       int flag,
                       int fStackPosition)

ringToRing

public void ringToRing(int[][] tmpGraph,
                       int flag,
                       int fStackPosition)

ringToRingOLD

public void ringToRingOLD(int[][] graph,
                          int flag)

reachableFromTo

public int reachableFromTo(int[][] graph,
                           int numOfNode,
                           int from,
                           int to)

reachable

public int reachable(int[][] graph,
                     int numOfNode)

isDummy

public int isDummy(int s,
                   int t)

isIncluded

public int isIncluded(int[][] graph,
                      int node)

doesNeedDummy

public int doesNeedDummy(int[][] graph)

is2EdgeConnected

public int is2EdgeConnected(int[][] orgGraph)

dfSearch

public void dfSearch(int[][] graph,
                     int chk)

findNumOfNode

public int findNumOfNode(int[][] graph)

main

public static void main(java.lang.String[] args)

theAlgorithm

public int[][] theAlgorithm(int[][] topo,
                            int[][] connections)

This method is the startmethod of the algorithm out of SSF.

Specified by:

theAlgorithm in class GWUTemplate

Parameters:

topo - An array containing the topology matrix [fromNodeID, toNodeID, linkID].

connections - An array containing the connections [sourceNodeID, destNodeID].

Returns:

An array on int[0][0].

generateOpticalRoutes

private void generateOpticalRoutes(OpticalConnection[] connections)

Generates the array if routes according to the connection request. The routes will be generated out of the result stored in the outStr.

Parameters:

connections - the array containing the connection request from node to node.

Returns:

An array containing a list of nodes of the connection array.

checkRing

private void checkRing(Glass net,
                       RingList ring)

Checks if the network provides the ring topology that is needed. If the ring is not complete the topology creates it.

Parameters:

net - The network.

fillConnection

private void fillConnection(OpticalConnection conn,
                            int[] nodeList)

This method creates the datastructure behind the optical Connection. If a link is missing, this method even so creates the link in the topology. If a link does not have enough ressources it adds the ressource to the link. The created optical path provide lambda switching.

Parameters:

conn - The connection that has to be completed.

nodeList - The list of nodes that create the Path.

getResultString

public java.lang.String getResultString()

Returns the result string.

Returns:

The result stored in outStr as String.

getType

public byte getType()

This algorithm is a Routing and Wavelength Algorithm for Ring topologies.

Specified by:

getType in interface Algorithm

Overrides:

getType in class AlgorithmTemplate

Returns:

the value Algorithm.UNKNOWN.

Since:

1.1

execute

public java.util.Vector execute(Glass net,
                                java.util.Vector theListOfConnections,
                                java.util.Vector theParameter)
                         throws AlgorithmException

This method executes the algorithm.

Specified by:

execute in interface Algorithm

Overrides:

execute in class GWUTemplate

Parameters:

net - the topologies network.

theListOfConnections - The vector containing the connections.

theParameter - not used here.

Returns:

The vector containing the result.

Throws:

AlgorithmException - An AlgorithmException occured.