de.upb.swtpra05.group03.shuttle
Class SCCCalculator

java.lang.Object
  de.upb.swtpra05.group03.shuttle.SCCCalculator

All Implemented Interfaces:

Module, SCCCalculatorInterface, ShuttleModule

public class SCCCalculator

extends java.lang.Object

implements ShuttleModule, SCCCalculatorInterface

Calculates the strong connected components of a given topology.

Version:

$Revision: 1.3 $

Field Summary

(package private) java.util.HashMap	AdjacentVertices Stores the adjacent Stations for each Station
(package private) java.util.LinkedList	B List of the investigated Vertices -- needed for calculation --
(package private) int	biggestscc Number of the biggest SCC
(package private) int	biggestsccvertices The number of Vertices in the biggest SCC
(package private) int	dfbi dfb Index -- needed for calculation --
(package private) int[]	DFBI The DFB Index of the Vertice -- needed for calculation --
private static java.util.logging.Logger	log Logger
(package private) int[]	Q is the Vertice root of a SCC?
(package private) boolean	ready Are all SCCs connected?
(package private) int	scc Number of the current SCC -- needed for calculation --
(package private) java.util.LinkedList	SCC Vertices that are temporarly not in a SCC -- needed for calculation --
(package private) java.util.HashMap	SCCs HashMap with all calculated SCCs
(package private) boolean[]	stack Is the Vertice stacked?
(package private) java.util.HashMap	StationIDtoSCC Maps the StationID to the SCC Number
(package private) de.upb.swtpra.kernel.TopologyData	topology The Topology
(package private) java.util.HashMap	Vertices The Stations
(package private) java.util.HashMap	VerticesNum The Number a Vertice got -- needed for calculation --

Constructor Summary

SCCCalculator()
Constructor.. nothing needed here

Method Summary

private void	calculateSCC() Calculates all Strong Connected Components
private void	DFSSCC(de.upb.swtpra.kernel.TopologyDataObject tdobj) The SCC Algorithm
private void	generateStationIDtoSCCMap() Generates the StationIDtoSCC HashMap
private java.util.LinkedList	getAdjacentStations(de.upb.swtpra.kernel.TopologyDataObject tdobject) Returns all adjacent Stations to the given Station
java.util.HashMap	getSCCs() Returns the SCC HashMap
void	init(ModuleContainerInterface manager) Initializes this module.
boolean	isGoodConnection(int StartStationID, int EndStationID) Returns true if a Connection is within one SCC or the EndStation is within the biggest SCC
void	newMessageReceived(de.upb.swtpra.kernel.message.Message msg) React on the received message of the shuttle or not.
private void	trackdown(de.upb.swtpra.kernel.TopologyDataObject tdobject, java.util.LinkedList adjacent) Tracks down a given Track and adds all found Stations to the adjacent List.

Methods inherited from class java.lang.Object

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

Field Detail

log

private static final java.util.logging.Logger log

Logger

topology

de.upb.swtpra.kernel.TopologyData topology

The Topology

Vertices

java.util.HashMap Vertices

The Stations

AdjacentVertices

java.util.HashMap AdjacentVertices

Stores the adjacent Stations for each Station

VerticesNum

java.util.HashMap VerticesNum

The Number a Vertice got -- needed for calculation --

DFBI

int[] DFBI

The DFB Index of the Vertice -- needed for calculation --

Q

int[] Q

is the Vertice root of a SCC? -- needed for calculation --

stack

boolean[] stack

Is the Vertice stacked? -- needed for calculataion --

B

java.util.LinkedList B

List of the investigated Vertices -- needed for calculation --

SCC

java.util.LinkedList SCC

Vertices that are temporarly not in a SCC -- needed for calculation --

dfbi

int dfbi

dfb Index -- needed for calculation --

SCCs

java.util.HashMap SCCs

HashMap with all calculated SCCs

scc

int scc

Number of the current SCC -- needed for calculation --

StationIDtoSCC

java.util.HashMap StationIDtoSCC

Maps the StationID to the SCC Number

biggestscc

int biggestscc

Number of the biggest SCC

biggestsccvertices

int biggestsccvertices

The number of Vertices in the biggest SCC

ready

boolean ready

Are all SCCs connected?

Constructor Detail

SCCCalculator

public SCCCalculator()

Constructor.. nothing needed here

Method Detail

init

public void init(ModuleContainerInterface manager)

Description copied from interface: Module

Initializes this module. References to other modules should be set here to avoid circle dependencies.

Specified by:

init in interface Module

Parameters:

manager - The module manager which contain all modules

getSCCs

public java.util.HashMap getSCCs()

Returns the SCC HashMap

Returns:

HashMap

isGoodConnection

public boolean isGoodConnection(int StartStationID,
                                int EndStationID)

Returns true if a Connection is within one SCC or the EndStation is within the biggest SCC

Specified by:

isGoodConnection in interface SCCCalculatorInterface

Parameters:

StartStationID -

EndStationID -

Returns:

boolean

generateStationIDtoSCCMap

private void generateStationIDtoSCCMap()

Generates the StationIDtoSCC HashMap

DFSSCC

private void DFSSCC(de.upb.swtpra.kernel.TopologyDataObject tdobj)

The SCC Algorithm

Parameters:

tdobj -

calculateSCC

private void calculateSCC()

Calculates all Strong Connected Components

trackdown

private void trackdown(de.upb.swtpra.kernel.TopologyDataObject tdobject,
                       java.util.LinkedList adjacent)

Tracks down a given Track and adds all found Stations to the adjacent List.

Parameters:

tdobject -

adjacent -

getAdjacentStations

private java.util.LinkedList getAdjacentStations(de.upb.swtpra.kernel.TopologyDataObject tdobject)

Returns all adjacent Stations to the given Station

Parameters:

tdobject -

Returns:

LinkedList

newMessageReceived

public void newMessageReceived(de.upb.swtpra.kernel.message.Message msg)

Description copied from interface: ShuttleModule

React on the received message of the shuttle or not.

Specified by:

newMessageReceived in interface ShuttleModule

Parameters:

msg - The received message of the shuttle