Graph Traversal with Command Pattern

Compute distances, shortest paths, and route counts across a weighted directed graph.

Problem

Given a directed graph where nodes are towns and weighted edges are rail routes:

• Calculate the distance along a specific route.
• Count routes between two stations with constraints (max stops, max distance).
• Find the shortest path between two stations (with and without cycles).

Approach

1. Graph representation. Adjacency list using a HashMap<Node, List<WeightedEdge>>. More memory-efficient than a matrix for sparse graphs, and the typical rail network is sparse.

2. Command pattern for calculations. Each query type is encapsulated as a command — FollowPathCommand, StopsMadeCommand, ShortestPathDijkstra, DistanceTraversedCommand, etc. New calculations can be added without modifying the graph structure.

3. Dijkstra for shortest path (no cycles). Standard priority-queue-based shortest path. Parent pointers are set during relaxation, then the path is reconstructed by walking backwards from the target.

4. DFS with backtracking for constrained traversals. Route counting under distance or stop constraints uses DFS with accumulated state. The search prunes branches that exceed the constraint, and backtracking ensures all valid paths are explored.

5. Facade via RailwayService. A single service class delegates to the appropriate command, keeping the API surface clean.

Implementation

Graph — adjacency list with factory method for string-based construction:

public class Graph implements IGraph {

    private Map<Node, List<WeightedEdge>> adj = new LinkedHashMap<>();
    private Map<String, Node> nodes = new LinkedHashMap<>();

    public static IGraph buildGraph(String mapString) {
        Graph g = new Graph();
        for (String edge : mapString.trim().split(", ")) {
            Node src = g.nodes.computeIfAbsent(String.valueOf(edge.charAt(0)), Node::new);
            Node tgt = g.nodes.computeIfAbsent(String.valueOf(edge.charAt(1)), Node::new);
            g.addWeightedEdge(src, tgt, Double.parseDouble(String.valueOf(edge.charAt(2))));
        }
        return g;
    }

    public void addWeightedEdge(Node v, Node w, double weight) {
        adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new WeightedEdge(w, weight));
        nodes.putIfAbsent(v.getName(), v);
        nodes.putIfAbsent(w.getName(), w);
    }

    public List<WeightedEdge> getNodeAdjacentEdges(Node node) {
        return new ArrayList<>(adj.getOrDefault(node, Collections.emptyList()));
    }

    public Node getNode(String name) { return nodes.get(name); }
}

Node and WeightedEdge:

public class Node implements Comparable<Node> {
    public String name;
    public double shortestDistanceFromParent = Double.POSITIVE_INFINITY;
    public Node parent;

    public Node(String name) { this.name = name; }

    @Override
    public int compareTo(Node other) {
        return Double.compare(shortestDistanceFromParent, other.shortestDistanceFromParent);
    }
}

public class WeightedEdge {
    public Node target;
    public double weight;

    public WeightedEdge(Node target, double weight) {
        this.target = target;
        this.weight = weight;
    }
}

RailwayService — facade that delegates to command objects:

public class RailwayService implements IRailwayService {

    private IGraph graph;

    public void buildMap(String railwayMap) {
        graph = Graph.buildGraph(railwayMap);
    }

    public int getDistance(String route) {
        Node[] nodes = new Node[route.length()];
        for (int i = 0; i < route.length(); i++)
            nodes[i] = graph.getNode(String.valueOf(route.charAt(i)));

        ITraverseCommand follow = new FollowPathCommand();
        follow.execute(graph, nodes);
        List<List<WeightedEdge>> edges = follow.results();
        return !edges.isEmpty() ? Utils.computeDistance(edges.get(0)) : 0;
    }

    public int getShortestDistance(String source, String target, Utils.AllowCycles allowCycles) {
        if (allowCycles == Utils.AllowCycles.NO) {
            IModifyCommand dijkstra = new ShortestPathDijkstra(Utils.Sorters.ShortestDistanceComparator);
            dijkstra.compute(graph, new Node[]{graph.getNode(source)});
            ITraverseCommand cmd = new ShortestPathCommand();
            cmd.execute(graph, new Node[]{graph.getNode(target)});
            return Utils.computeDistance(cmd.results().get(0));
        } else {
            GetAllPathsCommand allPaths = new GetAllPathsCommand(true);
            allPaths.execute(graph, new Node[]{graph.getNode(source), graph.getNode(target)});
            return Utils.computeDistances(allPaths.results());
        }
    }

    public int getRoutesInDistance(String source, String target, int distance) {
        ITraverseCommand cmd = new DistanceTraversedCommand(distance);
        cmd.execute(graph, new Node[]{graph.getNode(source), graph.getNode(target)});
        return cmd.results().size();
    }
}

DistanceTraversedCommand — DFS with distance constraint and backtracking:

public class DistanceTraversedCommand implements ITraverseCommand {

    private final double maxDistance;
    private List<List<WeightedEdge>> paths;

    public DistanceTraversedCommand(double distance) {
        this.maxDistance = distance;
    }

    @Override
    public void execute(IGraph graph, Node[] nodes) {
        paths = new ArrayList<>();
        Deque<WeightedEdge> path = new ArrayDeque<>();
        dfs(graph, new WeightedEdge(nodes[0], 0.0), new WeightedEdge(nodes[1], 0.0),
            path, paths, 0.0);
    }

    private void dfs(IGraph graph, WeightedEdge current, WeightedEdge target,
                     Deque<WeightedEdge> path, List<List<WeightedEdge>> result,
                     double accumulated) {
        double dist = accumulated + current.weight;
        path.addLast(current);

        if (path.size() > 1 && current.target.equals(target.target) && dist < maxDistance)
            result.add(new ArrayList<>(path));

        if (dist < maxDistance && graph.getGraphAdjacencyMap().containsKey(current.target)) {
            for (WeightedEdge next : graph.getGraphAdjacencyMap().get(current.target)) {
                if (!path.contains(next))
                    dfs(graph, next, target, path, result, dist);
            }
        }

        path.removeLast(); // backtrack
    }

    @Override
    public List<List<WeightedEdge>> results() { return paths; }
}

Complexity

• Dijkstra (shortest path, no cycles): O((V + E) log V) with a priority queue.
• DFS with constraints: O(V + E) per traversal, but can explore exponentially many paths in dense graphs with cycles.
• Space: O(V + E) for the adjacency list, O(V) for Dijkstra's visited set.

Takeaway

The command pattern decouples graph structure from graph algorithms, so you can add new query types without touching the core data model. Useful anytime you have a stable data structure but changing requirements for how you traverse or analyze it.

---

Back to Microservices & APIs