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

i have directed graph vertexes 123456. using depth first search, if wanted able find number of unique routes 1-4 (for example), how go doing it? here 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());          }     }  } 

since cycles aren't allowed, have dag (directed acyclid graph).

these questions related topic:

• number of paths between 2 nodes in dag
• topological sort find number of paths t

basically, idea topological sort of dag, iterate nodes starting destination node backwards source node, calculating how many paths node.

since array haven't cycles , nodes topological sorted, when visit node, nodes can reached node appears latter in sort , visited. so, count of paths node target sum of counts of nodes adjacent 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;      (int = tgtindex; >= srcindex; i--) {         (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<>();      (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 cycle.");     }      visited.add(node);      (edge edge: node.getincomings())         explore(edge.getfrom(), g, ordering, visited, expanded);      ordering.add(node);     expanded.add(node); } 

usage:

graph g = new graph();  node = 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 = 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 want using bfs, can try doing backtrack resetting 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);          (edge edge : current.getoutgoings())             if (!visiteds.contains(edge.getto()))                 count += bfs(edge.getto(), target, visiteds);          visiteds.remove(current);         return count;     } }     

however, increase performance, can implement kind of memoization:

static int countpaths(graph graph, node source, node target) {     set<node> visiteds = new hashset<>();     map<node, integer> memoize = new hashmap<>();      (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);          (edge edge : current.getoutgoings())             if (!visiteds.contains(edge.getto()))                 count += bfs(edge.getto(), visiteds, memoize);          visiteds.remove(current);         memoize.put(current, count);         return count;     } }