<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * A Backend class that implements BackendInterface, using the new
 * GraphADT&lt;String, Double&gt; interface to manage graph data.
 */
public class Backend implements BackendInterface {

    private GraphADT&lt;String, Double&gt; graph;

    /**
     * Constructor that takes a GraphADT where nodes are Strings and
     * edge weights are Doubles (which must be &gt; 0.0).
     *
     * @param graph the graph this backend will manage
     */
    public Backend(GraphADT&lt;String, Double&gt; graph) {
        this.graph = graph;
    }

    /**
     * Clears all edges and nodes from the graph.
     */
    private void clearGraph() {
        List&lt;String&gt; nodes = new ArrayList&lt;&gt;(graph.getAllNodes());

        // First remove all edges between nodes
        for (String from : nodes) {
            for (String to : nodes) {
                if (!from.equals(to)) {
                    try {
                        graph.removeEdge(from, to);
                    } catch (NoSuchElementException e) {
                        // Ignore if no such edge exists
                    }
                }
            }
        }

        // Then remove all nodes
        for (String node : nodes) {
            graph.removeNode(node);
        }
    }

    /**
     * Loads graph data from a DOT file. Clears the existing graph, then loads nodes and edges.
     *
     * @param filename the path to a DOT file to read graph data from
     * @throws IOException if there was any problem reading from this file
     */
    @Override
    public void loadGraphData(String filename) throws IOException {
        clearGraph();
    
        // Correct and strict regex for parsing edges
        Pattern edgePattern = Pattern.compile("\\s*\"([^\"]+)\"\\s*-&gt;\\s*\"([^\"]+)\"\\s*\\[\\s*seconds\\s*=\\s*([0-9]+(?:\\.[0-9]+)?)\\s*\\];");
    
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            String line;
            while ((line = br.readLine()) != null) {
                Matcher m = edgePattern.matcher(line);
                if (m.matches()) {
                    String source = m.group(1);
                    String destination = m.group(2);
                    String weightStr = m.group(3);
    
                    try {
                        Double weight = Double.valueOf(weightStr);
                        if (weight &lt;= 0.0) {
                            continue; // Skip non-positive weights
                        }
                        graph.insertNode(source);
                        graph.insertNode(destination);
                        graph.insertEdge(source, destination, weight);
                    } catch (NumberFormatException e) {
                        // Skip invalid weight
                    }
                }
            }
        }
    }
    

    /**
     * Returns a list of all locations (node data) available in the graph.
     *
     * @return list of all location names
     */
    @Override
    public List&lt;String&gt; getListOfAllLocations() {
        return graph.getAllNodes();
    }

    /**
     * Returns the sequence of locations along the shortest path from
     * startLocation to endLocation, or an empty list if no such path exists.
     *
     * @param startLocation the start location of the path
     * @param endLocation   the end location of the path
     * @return a list of nodes along the shortest path; empty if no path
     */
    @Override
    public List&lt;String&gt; findLocationsOnShortestPath(String startLocation, String endLocation) {
        if (!graph.containsNode(startLocation) || !graph.containsNode(endLocation)) {
            return Collections.emptyList();
        }
        try {
            return graph.shortestPathData(startLocation, endLocation);
        } catch (NoSuchElementException e) {
            return Collections.emptyList();
        }
    }

    /**
     * Returns the walking times (in seconds) between each pair of consecutive
     * locations on the shortest path from startLocation to endLocation.
     *
     * @param startLocation the start location of the path
     * @param endLocation   the end location of the path
     * @return a list of edge weights (times) along the path; empty if no path
     */
    @Override
    public List&lt;Double&gt; findTimesOnShortestPath(String startLocation, String endLocation) {
        List&lt;Double&gt; times = new ArrayList&lt;&gt;();

        if (!graph.containsNode(startLocation) || !graph.containsNode(endLocation)) {
            return times;
        }

        List&lt;String&gt; path = findLocationsOnShortestPath(startLocation, endLocation);

        if (path.size() &lt; 2) {
            return times;
        }

        for (int i = 0; i &lt; path.size() - 1; i++) {
            String from = path.get(i);
            String to = path.get(i + 1);

            try {
                Double weight = graph.getEdge(from, to);
                times.add(weight);
            } catch (NoSuchElementException e) {
                // Edge missing; skip
            }
        }
        return times;
    }

    /**
     * Returns the most distant location (the one that takes the longest time
     * to reach via the shortest path) from the provided startLocation.
     *
     * @param startLocation the location to start from
     * @return the most distant reachable location
     * @throws NoSuchElementException if startLocation does not exist,
     *                                or if there are no other locations reachable
     */
    @Override
    public String getFurthestDestinationFrom(String startLocation) throws NoSuchElementException {
        if (!graph.containsNode(startLocation)) {
            throw new NoSuchElementException("Start location not in graph: " + startLocation);
        }

        String furthestLocation = null;
        double maxDistance = Double.NEGATIVE_INFINITY;

        for (String location : graph.getAllNodes()) {
            if (location.equals(startLocation)) {
                continue;
            }
            try {
                double distance = graph.shortestPathCost(startLocation, location);
                if (distance &gt; maxDistance) {
                    maxDistance = distance;
                    furthestLocation = location;
                }
            } catch (NoSuchElementException e) {
                // No path exists; skip
            }
        }

        if (furthestLocation == null) {
            throw new NoSuchElementException("No other reachable locations from " + startLocation);
        }

        return furthestLocation;
    }
}
</pre></body></html>