Find number of unique routes to specific node using Depth First Search

Question

I have a directed graph with vertexes 123456. Using a depth first search, if I wanted to be able to find the number of unique routes from 1-4 (for example), how would I go about doing it? Here is my current DFS.

private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;
private List<Node> mVisited = new ArrayList<>();
int weight;
int numberOfPaths;

public DepthFirstSearch(Graph graph){
    mNodes = graph.getNodes();
    mEdges = new ArrayList<>(graph.getEdges());
    for(Node node : mNodes.values()){
        node.setVisited(false);
    }
}

public void depthFirstSearch(Node source){

    source.setVisited(true);
    List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
    for(Edge edge : neighbours){
        System.out.println(edge.getFrom().getName()+"-"+edge.getTo().getName());
        if(!edge.getTo().isVisited()){

            mVisited.add(edge.getTo());
            weight += edge.getWeight();
            depthFirstSearch(edge.getTo());

        }
    }

}

Answer 1

Since cycles aren't allowed, you have actually a DAG (directed acyclid graph).

These are some questions related to this topic:

• Number of paths between two nodes in a DAG
• Topological sort to find the number of paths to t

Basically, the idea is get a topological sort of the DAG, then iterate the nodes starting from the destination node backwards to the source node, calculating how many paths are from that node.

Since the array haven't cycles and the nodes are topological sorted, when you visit a node, all nodes that can be reached from that node appears latter in the sort and are already visited. So, the count of paths from an node to the target is the sum of the counts of the nodes that are adjacent to it.

Models:

class Graph
{
    private List<Node> nodes;
    private List<Edge> edges;

    public Graph() {
        nodes = new ArrayList<>();
        edges = new ArrayList<>();
    }

    public List<Node> getNodes() { return nodes; }    
    public List<Edge> getEdges() { return edges; }

    public void addNode(Node node) { nodes.add(node); }    
    public void addEdge(Edge edge) {
        edges.add(edge);        
        edge.getFrom().addEdge(edge);
        edge.getTo().addEdge(edge);
    }
}

class Node
{
    private List<Edge> outgoings, incomings;

    public Node() {
        outgoings = new ArrayList<>();
        incomings = new ArrayList<>();
    }

    public List<Edge> getOutgoings() { return outgoings; }    
    public List<Edge> getIncomings() { return incomings; }

    public void addEdge(Edge edge) {
        if (edge.getFrom() == this) outgoings.add(edge);
        if (edge.getTo() == this) incomings.add(edge);
    }
}

class Edge
{
    private Node from, to;

    public Edge(Node from, Node to) {
        this.from = from;
        this.to = to;
    }

    public Node getFrom() { return from; }    
    public Node getTo() { return to; }
}

Algorithm:

static int countPaths(Graph graph, Node source, Node target)
{
    List<Node> nodes = topologicalSort(graph);
    int[] counts = new int[nodes.size()];

    int srcIndex = nodes.indexOf(source);
    int tgtIndex = nodes.indexOf(target);

    counts[tgtIndex] = 1;

    for (int i = tgtIndex; i >= srcIndex; i--) {
        for (Edge edge : nodes.get(i).getOutgoings())
            counts[i] += counts[nodes.indexOf(edge.getTo())];
    }

    return counts[srcIndex];
}

static List<Node> topologicalSort(Graph g)
{
    List<Node> result = new ArrayList<>();
    Set<Node> visited = new HashSet<>();
    Set<Node> expanded = new HashSet<>();

    for (Node node: g.getNodes())
        explore(node, g, result, visited, expanded);

    return result;
}

static void explore(Node node, Graph g, List<Node> ordering, Set<Node> visited, Set<Node> expanded) {
    if (visited.contains(node)) {            
        if (expanded.contains(node)) return;
        throw new IllegalArgumentException("Graph contains a cycle.");
    }

    visited.add(node);

    for (Edge edge: node.getIncomings())
        explore(edge.getFrom(), g, ordering, visited, expanded);

    ordering.add(node);
    expanded.add(node);
}

Usage:

Graph g = new Graph();

Node a = new Node();
Node b = new Node();
Node c = new Node();
Node d = new Node();
Node e = new Node();

Edge ab = new Edge(a, b);
Edge bc = new Edge(b, c);
Edge cd = new Edge(c, d);
Edge ad = new Edge(a, d);
Edge ae = new Edge(a, e);
Edge ed = new Edge(e, d);
Edge be = new Edge(b, e);
Edge ec = new Edge(e, c);

g.addNode(a);
g.addNode(b);
g.addNode(c);
g.addNode(d);
g.addNode(e);

g.addEdge(ab);
g.addEdge(bc);
g.addEdge(cd);
g.addEdge(ad);
g.addEdge(ae);
g.addEdge(ed);
g.addEdge(be);
g.addEdge(ec);

int count = countPaths(g, a, d); 

//count: 6

// Paths:
//1. A->B->C->D
//2. A->D
//3. A->E->D
//4. A->B->E->C->D
//5. A->B->E->D
//6. A->E->C->D

---

But, if you want to do it using a BFS, you can try doing a backtrack resetting the visited nodes:

static int countPaths(Graph graph, Node source, Node target)
{
    Set<Node> visiteds = new HashSet<>();
    return BFS(source, target, visiteds);
}

static int BFS(Node current, Node target, Set<Node> visiteds) {
    if (current == target) return 1;
    else
    {
        int count = 0;
        visiteds.add(current);

        for (Edge edge : current.getOutgoings())
            if (!visiteds.contains(edge.getTo()))
                count += BFS(edge.getTo(), target, visiteds);

        visiteds.remove(current);
        return count;
    }
}    

However, to increase the performance, you can implement some kind of memoization:

static int countPaths(Graph graph, Node source, Node target)
{
    Set<Node> visiteds = new HashSet<>();
    Map<Node, Integer> memoize = new HashMap<>();

    for (Node node : graph.getNodes())
        memoize.put(node, -1);

    memoize.put(target, 1);

    return BFS(source, visiteds, memoize);
}

static int BFS(Node current, Set<Node> visiteds, Map<Node, Integer> memoize) {
    if (memoize.get(current) != -1) return memoize.get(current);
    else
    {
        int count = 0;
        visiteds.add(current);

        for (Edge edge : current.getOutgoings())
            if (!visiteds.contains(edge.getTo()))
                count += BFS(edge.getTo(), visiteds, memoize);

        visiteds.remove(current);
        memoize.put(current, count);
        return count;
    }
}