BFS and DFS methods implemented to create new branches and be certain that those branches are not closer than T stations from the next branch.
private int calculateDistance(Station from, Station to) {
if (from.equals(to)) {
return 0; // La distancia a sí misma es 0
}
// Mapa para rastrear las distancias desde la estación 'from'
Map<Station, Integer> distances = new HashMap<>();
Queue<Station> queue = new Queue<>();
LinkedList<Station> visited = new LinkedList<>(); // Usar LinkedList para rastrear estaciones visitadas
queue.enqueue(from);
distances.put(from, 0);
visited.add(from);
while (!queue.isEmpty()) {
Station current = queue.dequeue();
int currentDistance = distances.get(current);
// Obtener estaciones vecinas
LinkedList<Station> neighbors = networkTrain.getNeighbors(current);
for (Station neighbor : neighbors) {
// Verifica si la estación ya ha sido visitada
if (!visited.contains(neighbor)) {
visited.add(neighbor);
distances.put(neighbor, currentDistance + 1);
queue.enqueue(neighbor);
// Si encontramos la estación objetivo, devolvemos la distancia
if (neighbor.equals(to)) {
return distances.get(neighbor);
}
}
}
}
// Si no se encuentra el destino, retornar -1 o alguna señal de error
return -1;
}
private void runDFS(Station startStation, int T) {
// Inicializamos la primera sucursal
branches.add(startStation);
Map<Station, Integer> distances = new HashMap<>();
distances.put(startStation, 0); // La distancia de la estación inicial es 0
// Colorear la primera sucursal en verde
if (graphStreamGraph.getNode(startStation.getName()) != null) {
graphStreamGraph.getNode(startStation.getName()).setAttribute("ui.style", "fill-color: green;");
graphStreamGraph.getNode(startStation.getName()).setAttribute("ui.label", startStation.getName() + " 0");
}
// Usamos una pila para implementar DFS manualmente
Stack<Station> stack = new Stack<>();
Set<Station> visited = new HashSet<>();
stack.push(startStation);
visited.add(startStation);
// Realizamos el recorrido DFS
while (!stack.isEmpty()) {
Station currentStation = stack.pop();
int currentDistance = distances.get(currentStation);
// Obtener estaciones vecinas
LinkedList<Station> neighbors = networkTrain.getNeighbors(currentStation);
for (Station neighbor : neighbors) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
distances.put(neighbor, currentDistance + 1);
stack.push(neighbor);
// Mostrar el nombre de la estación y su distancia desde la estación inicial en el grafo
if (graphStreamGraph.getNode(neighbor.getName()) != null) {
graphStreamGraph.getNode(neighbor.getName()).setAttribute("ui.label", neighbor.getName() + " " + distances.get(neighbor));
}
// Calcular la distancia desde la sucursal a las estaciones
int distanceToBranch = calculateDistance(neighbor, startStation);
// Verificar si la distancia es divisible por T
if (distances.get(neighbor) % T == 0) {
boolean canPlaceBranch = true; // Variable para verificar la colocación
Station conflictingBranch = null; // Para guardar la sucursal que causa conflicto
// Iterar sobre las sucursales ya creadas
for (Station branch : branches) {
// Comprobar si la sucursal ya creada está a menos de T estaciones
int distanceToExistingBranch = calculateDistance(neighbor, branch);
if (distanceToExistingBranch < T) {
canPlaceBranch = false; // Encontramos una sucursal dentro de T estaciones
conflictingBranch = branch; // Guardamos la sucursal conflictiva
break;
}
}
// Colocar la sucursal si cumple con las condiciones
if (canPlaceBranch) {
branches.add(neighbor);
// Cambiar el color de la nueva sucursal a verde
if (graphStreamGraph.getNode(neighbor.getName()) != null) {
graphStreamGraph.getNode(neighbor.getName()).setAttribute("ui.style", "fill-color: green;");
}
// Imprimir la sucursal creada
System.out.println("Sucursal creada en: " + neighbor.getName() + ", distancia: " + distances.get(neighbor));
} else {
// Si ya hay una sucursal cercana, registrar el intento de colocar la sucursal
System.out.println("No se colocó la sucursal en " + neighbor.getName() + " a distancia " + distances.get(neighbor)
+ " porque está a menos de T de la sucursal " + conflictingBranch.getName() + ".");
}
}
}
}
}
// Mostrar todas las distancias y los nombres de las estaciones
System.out.println("Distancias desde la estación inicial:");
for (Map.Entry<Station, Integer> entry : distances.entrySet()) {
Station station = entry.getKey();
Integer distance = entry.getValue();
System.out.println("Estación: " + station.getName() + ", Distancia: " + distance);
}
// Mostrar las sucursales creadas
System.out.println("Sucursales creadas (DFS): " + branches.toString());
}
private void runBFS(Station startStation, int T) {
// Inicializar la distancia de la estación inicial
Queue queue = new Queue<>();
branches.add(startStation); // Sucursal inicial
Set visitedStations = new HashSet<>();
Map<Station, Integer> distances = new HashMap<>();
distances.put(startStation, 0);
// Colorear la estación inicial en verde
if (graphStreamGraph.getNode(startStation.getName()) != null) {
graphStreamGraph.getNode(startStation.getName()).setAttribute("ui.style", "fill-color: green;");
}
queue.enqueue(startStation);
visitedStations.add(startStation);
while (!queue.isEmpty()) {
Station current = queue.dequeue();
LinkedList<Station> neighbors = networkTrain.getNeighbors(current); // Usar el método getNeighbors
for (Station neighbor : neighbors) {
if (!visitedStations.contains(neighbor)) {
visitedStations.add(neighbor);
queue.enqueue(neighbor);
distances.put(neighbor, distances.get(current) + 1);
// Aquí decides cuándo agregar una nueva sucursal
if (distances.get(neighbor) % T == 0) {
branches.add(neighbor);
// Colorear la nueva sucursal en verde
if (graphStreamGraph.getNode(neighbor.getName()) != null) {
graphStreamGraph.getNode(neighbor.getName()).setAttribute("ui.style", "fill-color: green;");
}
}
}
}
}
// Mostrar las estaciones y sus distancias
for (Map.Entry<Station, Integer> entry : distances.entrySet()) {
Station station = entry.getKey();
Integer distance = entry.getValue();
// Mostrar el nombre de la estación y su distancia en el grafo
if (graphStreamGraph.getNode(station.getName()) != null) {
graphStreamGraph.getNode(station.getName()).setAttribute("ui.label", station.getName() + " " + distance);
}
BFS and DFS methods implemented to create new branches and be certain that those branches are not closer than T stations from the next branch.
private int calculateDistance(Station from, Station to) { if (from.equals(to)) { return 0; // La distancia a sí misma es 0 }
}
private void runDFS(Station startStation, int T) { // Inicializamos la primera sucursal branches.add(startStation); Map<Station, Integer> distances = new HashMap<>(); distances.put(startStation, 0); // La distancia de la estación inicial es 0
}
private void runBFS(Station startStation, int T) { // Inicializar la distancia de la estación inicial Queue queue = new Queue<>();
branches.add(startStation); // Sucursal inicial
Set visitedStations = new HashSet<>();
Map<Station, Integer> distances = new HashMap<>();
distances.put(startStation, 0);
// System.out.println("Estación: " + station.getName() + ", Distancia: " + distance); }
}