package org.lucci.madhoc.network.util;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
import org.lucci.madhoc.network.Station;
import org.lucci.madhoc.network.Network;
import org.lucci.madhoc.network.net.NetworkInterface;
import org.lucci.madhoc.network.net.NetworkingTechnology;
import org.lucci.madhoc.network.net.NetworkingUnit;
import org.lucci.math.Utilities;
import org.lucci.util.assertion.Assertions;
public class Graph
{
static public List<Collection<Station>> getHops(NetworkingUnit networkingUnit, int maxHop)
{
if (maxHop < 0)
throw new IllegalArgumentException();
List<Collection<Station>> hops = new Vector<Collection<Station>>();
Collection<Station> hop0 = new HashSet<Station>();
hop0.add(networkingUnit.getStation());
hops.add(hop0);
while (hops.size() - 1 < maxHop)
{
Collection<Station> newHop = new HashSet<Station>();
{
Collection<Station> previousHop = hops.get(hops.size() - 1);
for (Station s : previousHop)
{
newHop.addAll(s.getNetworkingUnit().getNeighborhood());
}
}
Iterator hopIterator = hops.iterator();
while (hopIterator.hasNext())
{
newHop.removeAll((Collection) hopIterator.next());
}
hops.add(newHop);
}
return hops;
}
public static int getMaximumDegree(Network net)
{
if (net.getStations().isEmpty())
throw new IllegalArgumentException();
int max = 0;
for (Station station : net.getStations())
{
int degree = station.getNetworkingUnit().getNeighborhood().size();
if (degree > max)
{
max = degree;
}
}
return max;
}
public static int getMinimumDegree(Network net)
{
Assertions.ensure(!net.getStations().isEmpty(), "no station in the network, the min degree cannot be processed");
int min = Integer.MAX_VALUE;
for (Station station : net.getStations())
{
int degree = station.getNetworkingUnit().getNeighborhood().size();
if (degree < min)
{
min = degree;
}
}
return min;
}
public static double getAverageDegree(Network net)
{
Collection c = new Vector();
Iterator stationsIterator = net.getStations().iterator();
while (stationsIterator.hasNext())
{
Station station = (Station) stationsIterator.next();
double degree = station.getNetworkingUnit().getNeighborhood().size();
c.add(new Double(degree));
}
return Utilities.getAverage(c);
}
public static Collection getRedundantConnections(Network net)
{
Collection c = new HashSet();
Iterator stationsIterator = net.getStations().iterator();
while (stationsIterator.hasNext())
{
Station station = (Station) stationsIterator.next();
Iterator neighborIterator = station.getNetworkingUnit().getNeighborhood().iterator();
while (neighborIterator.hasNext())
{
Station neighbor = (Station) neighborIterator.next();
Collection connectionsToNeighbors = station.getNetworkingUnit().getConnectionsTo(neighbor);
int connectionCount = connectionsToNeighbors.size();
if (connectionCount > 1)
{
c.add(connectionsToNeighbors);
}
}
}
return c;
}
public static Collection<Collection<Station>> getPartitions(Network net)
{
Collection<Collection<Station>> partitions = new Vector<Collection<Station>>();
Collection<Station> stationsNotYetAffected = new HashSet<Station>(net.getStations());
while (!stationsNotYetAffected.isEmpty())
{
Station station = stationsNotYetAffected.iterator().next();
Collection<Station> partition = getPartition(station);
stationsNotYetAffected.removeAll(partition);
partitions.add(partition);
}
return partitions;
}
public static Collection<Station> getGreatestConnectedComponent(Network net)
{
double max = 0;
Collection<Station> greatestComponent = null;
for (Collection<Station> partition : getPartitions(net))
{
if (greatestComponent == null)
{
greatestComponent = partition;
}
else
{
int ps = partition.size();
if (ps > max)
{
greatestComponent = partition;
max = ps;
}
}
}
return greatestComponent;
}
private static Collection<Station> getPartition(Station station)
{
List<Station> partition = new Vector<Station>();
partition.add(station);
for (int i = 0; i < partition.size(); ++i)
{
for (Station neighbor : partition.get(i).getNetworkingUnit().getNeighborhood())
{
if (!partition.contains(neighbor))
{
partition.add(neighbor);
}
}
}
return partition;
}
public static Collection findNetworkTypes(Network network)
{
Collection networkTypes = new HashSet();
Iterator stationIterator = network.getStations().iterator();
while (stationIterator.hasNext())
{
Station station = (Station) stationIterator.next();
Iterator networkInterfaceIterator = station.getNetworkingUnit().getNetworkInterfaces().iterator();
while (networkInterfaceIterator.hasNext())
{
NetworkInterface networkInterface = (NetworkInterface) networkInterfaceIterator.next();
networkTypes.add(networkInterface.getNetworkingTechnology());
}
}
return networkTypes;
}
public static Collection findBridgesTowardsNetworkType(Network network, NetworkingTechnology networkType)
{
Collection bridges = new Vector();
Iterator stationIterator = network.getStations().iterator();
while (stationIterator.hasNext())
{
Station station = (Station) stationIterator.next();
if (station.getNetworkingUnit().getNetworkInterfaces().size() > 1 && station.getNetworkingUnit().getNetworkInterface(networkType) != null)
{
bridges.add(station);
}
}
return bridges;
}
public static Collection findBridgesBetween(Network network, NetworkingTechnology t1, NetworkingTechnology t2)
{
Collection bridges = new Vector();
Iterator stationIterator = network.getStations().iterator();
while (stationIterator.hasNext())
{
Station station = (Station) stationIterator.next();
if (station.getNetworkingUnit().getNetworkInterface(t1) != null && station.getNetworkingUnit().getNetworkInterface(t2) != null)
{
bridges.add(station);
}
}
return bridges;
}
public static Collection findUnreachableNetworkTypes(Network network)
{
Collection isolatedNetworkTypes = new Vector();
Collection networkTypesInvolved = findNetworkTypes(network);
if (networkTypesInvolved.size() > 1)
{
Iterator networkTypeIterator = networkTypesInvolved.iterator();
while (networkTypeIterator.hasNext())
{
NetworkingTechnology networkType = (NetworkingTechnology) networkTypeIterator.next();
Collection bridges = findBridgesTowardsNetworkType(network, networkType);
if (bridges.isEmpty())
{
isolatedNetworkTypes.add(networkType);
}
}
}
return isolatedNetworkTypes;
}
}