algorithm - How to implement the search for all paths inside a directed graph in JavaScript? -

-

i find distinct paths without cycles in following graph:

directed unweighted graph

from graph, composed adjacency list, starting node 0 , going right (in picture above):

var rightadjacent = [[1,7],[2],[3,9],[4],[5],[6,10],[8],[2],[5],[11],[12]];

as noob in graphs, started canonical algorithm bfs, seems me cheapest way need:

...     var paths = []   queue.push(0); // starting node parents[0] = null;  while (queue.length > 0) {     u = queue.splice(0, 1)[0];     (i = 0, l= rightadjacent.length; < l; i++) { // explore edge(u, v).         v = rightadjacent[u][i];         if (rightadjacent[v]) {             if(rightadjacent[v].status === 'unexplored') {                 rightadjacent[v].status = 'exploring'; // node u has been discovered                 queue.push(v);                 parents[v] = u;             }         } else {             paths.push(collectpath(parents));         }     }     rightadjacent[u].status = 'explored';  }

... in first attempt able collect list of connected components, after , until now, garbage.

i have composed left-adjacency list, not knowing if useful speed search or back-trace discovered path. clue this?

for graph in picture, i'm expecting following result (please correct me if i'am wrong):

[0,1,2,3,4,5,6], [0,1,2,9,5,6], [0,1,2,9,5,10,11,12], [0,7,8,2,3,4,5,6], [0,7,8,2,9,5,10,11,12]

where each single path has nodes ordered starting node, through first encountered, until last.

starting adjacency list, , without using recursion, wouldn't simplest way collect paths, (the ordered parent nodes of parent paths) in example, starting node 0 , ending @ nodes 6 , 12?

what wrong in piece of code?

your rightadjacent missing neighbours of node 6, should empty array. easy solution implement bfs deep copy visited , current path when add node path. when have no neightbours, can output/save current path

		var rightadjacent = [[1,7],[2],[3,9],[4],[5],[6,10],[],[8],[2],[5],[11],[12]];        var queue = [{visited:{0:true},path:[0]}] // start node 0        function bfs(){         while(queue.length){             obj = queue.pop() // last added path             node = obj.path[obj.path.length-1] // last visited node path             visited = obj.visited             if(node >= rightadjacent.length || rightadjacent[node].length == 0){ // reached leaf node                 console.log(obj.path)             }else{               for(var i=0;i<rightadjacent[node].length;i++){ // need add neighbours not visited                   if(!visited[rightadjacent[node][i]]){                       visited[rightadjacent[node][i]] = true                       arr = obj.path.slice(0);                      arr.push(rightadjacent[node][i]); queue.push({visited:json.parse(json.stringify(visited)),path:arr}) // deep copy of both                   }               }             }         }	      }        bfs()


Comments

Post a Comment

Popular posts from this blog

Spring Boot + JPA + Hibernate: Unable to locate persister -

-
i trying work entity inside request method of spring boot application. entity in project , pom.xml has dependencies it. why error message?: org.hibernate.unknownentitytypeexception: unable locate persister: com.ric.bill.model.bs.par package com.ric.web; import java.util.concurrent.atomic.atomiclong; import javax.persistence.entitymanager; import javax.persistence.persistencecontext; import net.sf.ehcache.cachemanager; import net.sf.ehcache.management.cache; import net.sf.ehcache.management.cachestatistics; import org.hibernate.stat.statistics; import org.springframework.beans.factory.annotation.autowired; import org.springframework.boot.autoconfigure.domain.entityscan; import org.springframework.cache.annotation.enablecaching; import org.springframework.transaction.annotation.enabletransactionmanagement; import org.springframework.transaction.annotation.propagation; import org.springframework.transaction.annotation.transactional; import org.springframework.web.bind.annotati...
Read more

go - Golang: panic: runtime error: invalid memory address or nil pointer dereference using bufio.Scanner -

-
i implementing go program uses bufio.scanner , bufio.writer have packaged code follows package main import ( "fmt" "player/command" "strings" ) func main() { //enter code here. read input stdin. print output stdout commands.scanner.scan() { //scan new line , send comand variable check command exist or not input := strings.split(strings.trim(commands.scanner.text(), " "), " ") command := input[0] if command == "" { fmt.printf("$ %s:", commands.pwd) continue } if !commands.commands[command] { commands.throwerror("cannot recognize input.") } else { commands.execute(command, input[1:], nil) } fmt.printf("$ %s:", commands.pwd) } } i using init.go file in main package follows package main import ( "flag" "player/sourc...
Read more

c - double free or corruption (fasttop) -

-
this code reads null terminated string file (file containing null terminated strings & should provide index wanted string). error: *** error in `./main': double free or corruption (fasttop): 0x090a4a80 *** aborted code: char *tmp_realloc=null; char *sstring=null; int i=1; /*set file pointer point string*/ fseek(fh,index,seek_set); sstring=(char*)malloc(sizeof(char)); if(sstring == null) return null; tmp_realloc=sstring; while( (*(sstring+i-1)=(char)fgetc((file*)fh)) != 0x0 ) { /*reallocate more memory*/ tmp_realloc=(char*)realloc((char*)sstring,++i); /*if not same address copy old new & set old point new*/ if(tmp_realloc != sstring){ strcpy((char*)tmp_realloc,(char*)sstring); free(sstring); sstring=tmp_realloc; } } could tell me pointer causing issue (& reason) ? remove part /*if not same address copy old new & set old point new*/ if(tmp_realloc != sstring){ strc...
Read more