thr3ads.net - R help - [R] Kosaraju's SCC Algorithm Running [Nov 2016]

If this information is useful, please help other people find it:
Share via:

Megan

2016-Nov-07 04:12 UTC

[R] Kosaraju's SCC Algorithm Running

To whom it may concerns,

We encountered stack overflow issues when we implemented DFS(depth first search)
algorithm on a directed graph having 800,000+ vertices and millions of edges. 
The purpose of running DFS is to use Kosaraju Algorithm to calculate the size of
SCC(strongly connected componment) in the graph. This is an assignment from
Coursea.org <http://coursea.org/>. We know the maximum size of SCC in the
graph is 434,821, which means the maximum recursion depth during code running is
434,821. We know it is a large calculation behind the scene, therefore, we?ve
done the below pre-setup hopefully to solve the stack overflow issue. However,
we have not got the luck yet. We?ve tried running on both R and RStudio.

We would really appreciate if someone in your team can help to investigate. We
can?t wait to see if our code is working in R.

System Information:
Model Name:	MacBook Pro
  Model Identifier:	MacBookPro11,1
  Processor Name:	Intel Core i5
  Processor Speed:	2.4 GHz
  Number of Processors:	1
  Total Number of Cores:	2
  L2 Cache (per Core):	256 KB
  L3 Cache:	3 MB
  Memory:	8 GB

System settings we have tried:
1. ulimit- s 65000 (to increase stack size before starting up R)
2. R --max-ppsize =500000 (start R with max ppsize)
3. options(expression=500000)


The data we used can be found on 
https://d18ky98rnyall9.cloudfront.net/_410e934e6553ac56409b2cb7096a44aa_SCC.txt?Expires=1478649600&Signature=YC0OjTn4hmzWpzAMw3WkQjXgxkAc0qhZrCd07JAPtud3dGQqywpQgkAASf-bWX6qgGafVvObciJ3ww-7wbNqY0YhWxwcg-IxmCnz1xJu1SORdDobiVKmhhfSaqgTyullX1hFmcxAA4y6Ud33hY1dhIP~UTAlW~IV8Y-zSliAts8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A
<https://d18ky98rnyall9.cloudfront.net/_410e934e6553ac56409b2cb7096a44aa_SCC.txt?Expires=1478649600&Signature=YC0OjTn4hmzWpzAMw3WkQjXgxkAc0qhZrCd07JAPtud3dGQqywpQgkAASf-bWX6qgGafVvObciJ3ww-7wbNqY0YhWxwcg-IxmCnz1xJu1SORdDobiVKmhhfSaqgTyullX1hFmcxAA4y6Ud33hY1dhIP~UTAlW~IV8Y-zSliAts8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A>

Data discription provided as follow:
https://www.coursera.org/learn/algorithm-design-analysis/exam/rOtFq/programming-assignment-4
<https://www.coursera.org/learn/algorithm-design-analysis/exam/rOtFq/programming-assignment-4>

Below is our code:

options(expressions=500000)
#Prepare input test file  
g=read.table("Downloads/scc.txt")
x<<-as.matrix(g)
remove(g)
vector.is.empty<<-function(x) {return(length(x)==0)}
'%!in%' <- function(x,y)!('%in%'(x,y))
#g<-c(2,1,3,1,3,4,4,2,5,4,5,6,6,7,7,8,8,9,2,3)
#x<<-matrix(g,nrow=10,ncol=2, byrow=TRUE)
#g<-c(1,4,2,8,3,6,4,7,5,2,6,9,7,1,8,5,8,6,9,3,9,7,10,2)
#x<<-matrix(g,nrow=12,ncol=2, byrow=TRUE)
#g<-c(1,2,2,3,2,4,3,4,3,5,4,1,4,13,5,6,6,7,7,8,8,9,9,6,10,9,10,11,11,8,11,12,12,13,12,14,13,10,14,15)
#x<<-matrix(g,20,2,byrow=TRUE)

u1<-unique(x[,1])
u2<-unique(x[,2])
u<-c(u1,u2)
n<<-length(unique(u))
remove(u1,u2,u)

G <<- vector("list", length=n)
G_REV <<- vector("list", length=n)
P = numeric(n)
FT = numeric(n)

for (i in 1:nrow(x)) {
  a = x[i,1]
  b = x[i,2]
  #for G
  if (is.null(G[[a]])) {
    G[[a]] = c(b)
  } else {
    G[[a]] = c(G[[a]], b)
  }
  if (is.null(G[[b]])) {
    G[[b]] = numeric()
  }
  #for G_VEV
  if (is.null(G_REV[[b]])) {
    G_REV[[b]] = c(a)
  } else {
    G_REV[[b]] = c(G_REV[[b]], a)
  }
  if (is.null(G_REV[[a]])) {
    G_REV[[a]] = numeric()
  }
}

G_TEMP <<- G_REV

#G_REV<<-x[,c(2,1)]

#P<<-matrix(c(1:n,rep(0,2*n)),nrow=n,ncol=3) #tracking whether vertex is
explored or not

#colnames(P)<-c("node","f","parent_vertex")
explore<<-numeric()
assign("time",0,envir=globalenv())
#Algorithm -DFS

DFS_LOOP<<-function(G){
  counter = n 
  for(i in n : 1){
    if (i < counter) {
      counter = counter - 1000;
      print(i);
    }
    if (i %in% explore){next}
    else {
      DFS(i)
    }
  }
}

DFS<<-function(i){
  #if(time>=n){return(p)}
  #else{
  #print(c("i=",i))
  explore<<-c(explore,i)
  #print(c("explore",explore))
  
  #P[i,2] <<- 1 # gray
  v=G_TEMP[[i]]
  
  #print(c("v=",v))
  if (vector.is.empty(v) ==TRUE){
    len=1
    v=i
  }
  
  if(vector.is.empty(v)==FALSE){
    len=length(v)
  }
  
  for(j in 1: len){
    if(v[j] %!in% explore){
      DFS(v[j])
      #P[v[j],3] <<-i
      P[v[j]] <<- i
      # print(c("child",j,"parent",i))
    }
  }
  
  time<<-time + 1
  FT[i] <<- time
  #P[i,2] <<- time
  #P[i,2] <<- 2 #black
  # } <<-else
}
print('Starting DFS_loop on G_REV')
DFS_LOOP(G_REV)
###################################################
#temp0<-matrix(1:n,n,1)
# temp1<-P[,c(1,2)]
# colnames(temp1)<-c("before","after")
# temp1<-as.data.frame(temp1)
# colnames(x)<-c("vertex","edge")
# X<-as.data.frame(x)
# X_NEW<-merge(x=X,y=temp1,by.x="vertex",by.y="before")
# remove(X)
# names(X_NEW)[names(X_NEW)=="after"]<-"vertex_new"
#
X_NEW2<-merge(x=X_NEW,y=temp1,by.x="edge",by.y="before")
# remove(X_NEW,temp1)
# names(X_NEW2)[names(X_NEW2)=="after"]<-"edge_new"
# G2<-as.matrix(X_NEW2)
# remove(X_NEW2)
# G2<-G2[,c(3,4)]
# u1<-unique(G2[,1])
# u2<-unique(G2[,2])
# u<-c(u1,u2)
# n<<-length(unique(u))
# remove(u1,u2,u)

FT_SORTED = numeric(n)
for (i in length(FT):1) {
  finish_time = FT[i]
  FT_SORTED[finish_time] = i
}

P = numeric(n)
FT = numeric(n)

#P<<-matrix(c(1:n,rep(0,2*n)),nrow=n,ncol=3) #tracking whether vertex is
explored or not
#colnames(P)<-c("vertex","f","parent_vertex")
explore<<-numeric()
assign("time",0,envir=globalenv())

print('Starting DFS_loop on G')
#DFS_LOOP(G2)#2nd DFS
explore<<-numeric()

G_TEMP <<- G

for (i in length(FT_SORTED):1) { 
  k = FT_SORTED[i]
  if (k %!in% explore) {
    DFS(k)
  }
}

mscc_temp = which(P==0)
scc_temp=FT[mscc_temp]
#scc_temp<-P[P[,3]==0,2]
scc_temp=sort(scc_temp,decreasing=TRUE)
m=length(scc_temp)
scc=numeric()
for (i in 1:(m-1)){
  scc[i]=scc_temp[i]-scc_temp[i+1]
}
scc[m]<-scc_temp[m]
scc_top_5<-tail(sort(scc),5)


Thanks,
Jing
	[[alternative HTML version deleted]]

Jeff Newmiller

2016-Nov-07 07:28 UTC

head link

[R] Kosaraju's SCC Algorithm Running

Please read the Posting Guide mentioned at the bottom of this and every post,
which warns you that homework is off topic on this mailing list. Use the support
provided by your institution of learning (Coursera in this case).
-- 
Sent from my phone. Please excuse my brevity.

On November 6, 2016 8:12:38 PM PST, Megan <megan.fight at gmail.com>
wrote:>To whom it may concerns,
>
>We encountered stack overflow issues when we implemented DFS(depth
>first search) algorithm on a directed graph having 800,000+ vertices
>and millions of edges.  The purpose of running DFS is to use Kosaraju
>Algorithm to calculate the size of SCC(strongly connected componment)
>in the graph. This is an assignment from Coursea.org
><http://coursea.org/>. We know the maximum size of SCC in the graph is
>434,821, which means the maximum recursion depth during code running is
>434,821. We know it is a large calculation behind the scene, therefore,
>we?ve done the below pre-setup hopefully to solve the stack overflow
>issue. However, we have not got the luck yet. We?ve tried running on
>both R and RStudio.
>
>We would really appreciate if someone in your team can help to
>investigate. We can?t wait to see if our code is working in R. 
>
>System Information:
>Model Name:	MacBook Pro
>  Model Identifier:	MacBookPro11,1
>  Processor Name:	Intel Core i5
>  Processor Speed:	2.4 GHz
>  Number of Processors:	1
>  Total Number of Cores:	2
>  L2 Cache (per Core):	256 KB
>  L3 Cache:	3 MB
>  Memory:	8 GB
>
>System settings we have tried:
>1. ulimit- s 65000 (to increase stack size before starting up R)
>2. R --max-ppsize =500000 (start R with max ppsize)
>3. options(expression=500000)
>
>
>The data we used can be found on 
>https://d18ky98rnyall9.cloudfront.net/_410e934e6553ac56409b2cb7096a44aa_SCC.txt?Expires=1478649600&Signature=YC0OjTn4hmzWpzAMw3WkQjXgxkAc0qhZrCd07JAPtud3dGQqywpQgkAASf-bWX6qgGafVvObciJ3ww-7wbNqY0YhWxwcg-IxmCnz1xJu1SORdDobiVKmhhfSaqgTyullX1hFmcxAA4y6Ud33hY1dhIP~UTAlW~IV8Y-zSliAts8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A
><https://d18ky98rnyall9.cloudfront.net/_410e934e6553ac56409b2cb7096a44aa_SCC.txt?Expires=1478649600&Signature=YC0OjTn4hmzWpzAMw3WkQjXgxkAc0qhZrCd07JAPtud3dGQqywpQgkAASf-bWX6qgGafVvObciJ3ww-7wbNqY0YhWxwcg-IxmCnz1xJu1SORdDobiVKmhhfSaqgTyullX1hFmcxAA4y6Ud33hY1dhIP~UTAlW~IV8Y-zSliAts8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A>
>
>Data discription provided as follow:
>https://www.coursera.org/learn/algorithm-design-analysis/exam/rOtFq/programming-assignment-4
><https://www.coursera.org/learn/algorithm-design-analysis/exam/rOtFq/programming-assignment-4>
>
>
>Below is our code:
>
>options(expressions=500000)
>#Prepare input test file  
>g=read.table("Downloads/scc.txt")
>x<<-as.matrix(g)
>remove(g)
>vector.is.empty<<-function(x) {return(length(x)==0)}
>'%!in%' <- function(x,y)!('%in%'(x,y))
>#g<-c(2,1,3,1,3,4,4,2,5,4,5,6,6,7,7,8,8,9,2,3)
>#x<<-matrix(g,nrow=10,ncol=2, byrow=TRUE)
>#g<-c(1,4,2,8,3,6,4,7,5,2,6,9,7,1,8,5,8,6,9,3,9,7,10,2)
>#x<<-matrix(g,nrow=12,ncol=2, byrow=TRUE)
>#g<-c(1,2,2,3,2,4,3,4,3,5,4,1,4,13,5,6,6,7,7,8,8,9,9,6,10,9,10,11,11,8,11,12,12,13,12,14,13,10,14,15)
>#x<<-matrix(g,20,2,byrow=TRUE)
>
>u1<-unique(x[,1])
>u2<-unique(x[,2])
>u<-c(u1,u2)
>n<<-length(unique(u))
>remove(u1,u2,u)
>
>G <<- vector("list", length=n)
>G_REV <<- vector("list", length=n)
>P = numeric(n)
>FT = numeric(n)
>
>for (i in 1:nrow(x)) {
>  a = x[i,1]
>  b = x[i,2]
>  #for G
>  if (is.null(G[[a]])) {
>    G[[a]] = c(b)
>  } else {
>    G[[a]] = c(G[[a]], b)
>  }
>  if (is.null(G[[b]])) {
>    G[[b]] = numeric()
>  }
>  #for G_VEV
>  if (is.null(G_REV[[b]])) {
>    G_REV[[b]] = c(a)
>  } else {
>    G_REV[[b]] = c(G_REV[[b]], a)
>  }
>  if (is.null(G_REV[[a]])) {
>    G_REV[[a]] = numeric()
>  }
>}
>
>G_TEMP <<- G_REV
>
>#G_REV<<-x[,c(2,1)]
>
>#P<<-matrix(c(1:n,rep(0,2*n)),nrow=n,ncol=3) #tracking whether vertex
>is explored or not
>
>#colnames(P)<-c("node","f","parent_vertex")
>explore<<-numeric()
>assign("time",0,envir=globalenv())
>#Algorithm -DFS
>
>DFS_LOOP<<-function(G){
>  counter = n 
>  for(i in n : 1){
>    if (i < counter) {
>      counter = counter - 1000;
>      print(i);
>    }
>    if (i %in% explore){next}
>    else {
>      DFS(i)
>    }
>  }
>}
>
>DFS<<-function(i){
>  #if(time>=n){return(p)}
>  #else{
>  #print(c("i=",i))
>  explore<<-c(explore,i)
>  #print(c("explore",explore))
>  
>  #P[i,2] <<- 1 # gray
>  v=G_TEMP[[i]]
>  
>  #print(c("v=",v))
>  if (vector.is.empty(v) ==TRUE){
>    len=1
>    v=i
>  }
>  
>  if(vector.is.empty(v)==FALSE){
>    len=length(v)
>  }
>  
>  for(j in 1: len){
>    if(v[j] %!in% explore){
>      DFS(v[j])
>      #P[v[j],3] <<-i
>      P[v[j]] <<- i
>      # print(c("child",j,"parent",i))
>    }
>  }
>  
>  time<<-time + 1
>  FT[i] <<- time
>  #P[i,2] <<- time
>  #P[i,2] <<- 2 #black
>  # } <<-else
>}
>print('Starting DFS_loop on G_REV')
>DFS_LOOP(G_REV)
>###################################################
>#temp0<-matrix(1:n,n,1)
># temp1<-P[,c(1,2)]
># colnames(temp1)<-c("before","after")
># temp1<-as.data.frame(temp1)
># colnames(x)<-c("vertex","edge")
># X<-as.data.frame(x)
>#
X_NEW<-merge(x=X,y=temp1,by.x="vertex",by.y="before")
># remove(X)
># names(X_NEW)[names(X_NEW)=="after"]<-"vertex_new"
>#
X_NEW2<-merge(x=X_NEW,y=temp1,by.x="edge",by.y="before")
># remove(X_NEW,temp1)
># names(X_NEW2)[names(X_NEW2)=="after"]<-"edge_new"
># G2<-as.matrix(X_NEW2)
># remove(X_NEW2)
># G2<-G2[,c(3,4)]
># u1<-unique(G2[,1])
># u2<-unique(G2[,2])
># u<-c(u1,u2)
># n<<-length(unique(u))
># remove(u1,u2,u)
>
>FT_SORTED = numeric(n)
>for (i in length(FT):1) {
>  finish_time = FT[i]
>  FT_SORTED[finish_time] = i
>}
>
>P = numeric(n)
>FT = numeric(n)
>
>#P<<-matrix(c(1:n,rep(0,2*n)),nrow=n,ncol=3) #tracking whether vertex
>is explored or not
>#colnames(P)<-c("vertex","f","parent_vertex")
>explore<<-numeric()
>assign("time",0,envir=globalenv())
>
>print('Starting DFS_loop on G')
>#DFS_LOOP(G2)#2nd DFS
>explore<<-numeric()
>
>G_TEMP <<- G
>
>for (i in length(FT_SORTED):1) { 
>  k = FT_SORTED[i]
>  if (k %!in% explore) {
>    DFS(k)
>  }
>}
>
>mscc_temp = which(P==0)
>scc_temp=FT[mscc_temp]
>#scc_temp<-P[P[,3]==0,2]
>scc_temp=sort(scc_temp,decreasing=TRUE)
>m=length(scc_temp)
>scc=numeric()
>for (i in 1:(m-1)){
>  scc[i]=scc_temp[i]-scc_temp[i+1]
>}
>scc[m]<-scc_temp[m]
>scc_top_5<-tail(sort(scc),5)
>
>
>Thanks,
>Jing
>	[[alternative HTML version deleted]]
>
>______________________________________________
>R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
>https://stat.ethz.ch/mailman/listinfo/r-help
>PLEASE do read the posting guide
>http://www.R-project.org/posting-guide.html
>and provide commented, minimal, self-contained, reproducible code.

Jie C

2016-Nov-07 15:49 UTC

head link

[R] Kosaraju's SCC Algorithm Running

Hi Jeff,

Thanks for your reply! We are definitely not seeking for help with the
assignment per se. Maybe we should have given you a simpler code to just
illustrate the problem. We found this to be an interesting case for
illustrating the recursion limit of R. For other languages such as Python,
Java, and C++, it seems that they are less likely to hit the problem as R
does. Even if they do, it is relatively easy to increase the recursion
depth to the desired numbers. I want to clarify that our purpose is trying
to understand the limitation of R language in handling big computational
problems that relies on deep recursion. If you could point us to technical
documents regarding this, that would be highly appreciated. Also, we could
definitely re-post a simple code snippet that follows the Posting Guide to
illustrate that R hits the recursion limitation. Looking forward to your
advise!

Thanks,

Jie





On Mon, Nov 7, 2016 at 2:28 AM, Jeff Newmiller <jdnewmil at
dcn.davis.ca.us>
wrote:
> Please read the Posting Guide mentioned at the bottom of this and every
> post, which warns you that homework is off topic on this mailing list. Use
> the support provided by your institution of learning (Coursera in this
> case).
> --
> Sent from my phone. Please excuse my brevity.
>
> On November 6, 2016 8:12:38 PM PST, Megan <megan.fight at gmail.com>
wrote:
> >To whom it may concerns,
> >
> >We encountered stack overflow issues when we implemented DFS(depth
> >first search) algorithm on a directed graph having 800,000+ vertices
> >and millions of edges.  The purpose of running DFS is to use Kosaraju
> >Algorithm to calculate the size of SCC(strongly connected componment)
> >in the graph. This is an assignment from Coursea.org
> ><http://coursea.org/>. We know the maximum size of SCC in the
graph is
> >434,821, which means the maximum recursion depth during code running is
> >434,821. We know it is a large calculation behind the scene, therefore,
> >we?ve done the below pre-setup hopefully to solve the stack overflow
> >issue. However, we have not got the luck yet. We?ve tried running on
> >both R and RStudio.
> >
> >We would really appreciate if someone in your team can help to
> >investigate. We can?t wait to see if our code is working in R.
> >
> >System Information:
> >Model Name:    MacBook Pro
> >  Model Identifier:    MacBookPro11,1
> >  Processor Name:      Intel Core i5
> >  Processor Speed:     2.4 GHz
> >  Number of Processors:        1
> >  Total Number of Cores:       2
> >  L2 Cache (per Core): 256 KB
> >  L3 Cache:    3 MB
> >  Memory:      8 GB
> >
> >System settings we have tried:
> >1. ulimit- s 65000 (to increase stack size before starting up R)
> >2. R --max-ppsize =500000 (start R with max ppsize)
> >3. options(expression=500000)
> >
> >
> >The data we used can be found on
> >https://d18ky98rnyall9.cloudfront.net/_410e934e6553ac56409b2cb7096a44
> aa_SCC.txt?Expires=1478649600&Signature=YC0OjTn4hmzWpzAMw3WkQjXgxkAc0q
> hZrCd07JAPtud3dGQqywpQgkAASf-bWX6qgGafVvObciJ3ww-7wbNqY0YhWxwcg-
> IxmCnz1xJu1SORdDobiVKmhhfSaqgTyullX1hFmcxAA4y6Ud33hY1dhIP~
> UTAlW~IV8Y-zSliAts8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A
>
><https://d18ky98rnyall9.cloudfront.net/_410e934e6553ac56409b2cb7096a44
> aa_SCC.txt?Expires=1478649600&Signature=YC0OjTn4hmzWpzAMw3WkQjXgxkAc0q
> hZrCd07JAPtud3dGQqywpQgkAASf-bWX6qgGafVvObciJ3ww-7wbNqY0YhWxwcg-
> IxmCnz1xJu1SORdDobiVKmhhfSaqgTyullX1hFmcxAA4y6Ud33hY1dhIP~
> UTAlW~IV8Y-zSliAts8_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A>
> >
> >Data discription provided as follow:
> >https://www.coursera.org/learn/algorithm-design-analysis/exam/rOtFq/
> programming-assignment-4
>
><https://www.coursera.org/learn/algorithm-design-analysis/exam/rOtFq/
> programming-assignment-4>
> >
> >
> >Below is our code:
> >
> >options(expressions=500000)
> >#Prepare input test file
> >g=read.table("Downloads/scc.txt")
> >x<<-as.matrix(g)
> >remove(g)
> >vector.is.empty<<-function(x) {return(length(x)==0)}
> >'%!in%' <- function(x,y)!('%in%'(x,y))
> >#g<-c(2,1,3,1,3,4,4,2,5,4,5,6,6,7,7,8,8,9,2,3)
> >#x<<-matrix(g,nrow=10,ncol=2, byrow=TRUE)
> >#g<-c(1,4,2,8,3,6,4,7,5,2,6,9,7,1,8,5,8,6,9,3,9,7,10,2)
> >#x<<-matrix(g,nrow=12,ncol=2, byrow=TRUE)
> >#g<-c(1,2,2,3,2,4,3,4,3,5,4,1,4,13,5,6,6,7,7,8,8,9,9,6,10,
> 9,10,11,11,8,11,12,12,13,12,14,13,10,14,15)
> >#x<<-matrix(g,20,2,byrow=TRUE)
> >
> >u1<-unique(x[,1])
> >u2<-unique(x[,2])
> >u<-c(u1,u2)
> >n<<-length(unique(u))
> >remove(u1,u2,u)
> >
> >G <<- vector("list", length=n)
> >G_REV <<- vector("list", length=n)
> >P = numeric(n)
> >FT = numeric(n)
> >
> >for (i in 1:nrow(x)) {
> >  a = x[i,1]
> >  b = x[i,2]
> >  #for G
> >  if (is.null(G[[a]])) {
> >    G[[a]] = c(b)
> >  } else {
> >    G[[a]] = c(G[[a]], b)
> >  }
> >  if (is.null(G[[b]])) {
> >    G[[b]] = numeric()
> >  }
> >  #for G_VEV
> >  if (is.null(G_REV[[b]])) {
> >    G_REV[[b]] = c(a)
> >  } else {
> >    G_REV[[b]] = c(G_REV[[b]], a)
> >  }
> >  if (is.null(G_REV[[a]])) {
> >    G_REV[[a]] = numeric()
> >  }
> >}
> >
> >G_TEMP <<- G_REV
> >
> >#G_REV<<-x[,c(2,1)]
> >
> >#P<<-matrix(c(1:n,rep(0,2*n)),nrow=n,ncol=3) #tracking whether
vertex
> >is explored or not
> >
>
>#colnames(P)<-c("node","f","parent_vertex")
> >explore<<-numeric()
> >assign("time",0,envir=globalenv())
> >#Algorithm -DFS
> >
> >DFS_LOOP<<-function(G){
> >  counter = n
> >  for(i in n : 1){
> >    if (i < counter) {
> >      counter = counter - 1000;
> >      print(i);
> >    }
> >    if (i %in% explore){next}
> >    else {
> >      DFS(i)
> >    }
> >  }
> >}
> >
> >DFS<<-function(i){
> >  #if(time>=n){return(p)}
> >  #else{
> >  #print(c("i=",i))
> >  explore<<-c(explore,i)
> >  #print(c("explore",explore))
> >
> >  #P[i,2] <<- 1 # gray
> >  v=G_TEMP[[i]]
> >
> >  #print(c("v=",v))
> >  if (vector.is.empty(v) ==TRUE){
> >    len=1
> >    v=i
> >  }
> >
> >  if(vector.is.empty(v)==FALSE){
> >    len=length(v)
> >  }
> >
> >  for(j in 1: len){
> >    if(v[j] %!in% explore){
> >      DFS(v[j])
> >      #P[v[j],3] <<-i
> >      P[v[j]] <<- i
> >      # print(c("child",j,"parent",i))
> >    }
> >  }
> >
> >  time<<-time + 1
> >  FT[i] <<- time
> >  #P[i,2] <<- time
> >  #P[i,2] <<- 2 #black
> >  # } <<-else
> >}
> >print('Starting DFS_loop on G_REV')
> >DFS_LOOP(G_REV)
> >###################################################
> >#temp0<-matrix(1:n,n,1)
> ># temp1<-P[,c(1,2)]
> ># colnames(temp1)<-c("before","after")
> ># temp1<-as.data.frame(temp1)
> ># colnames(x)<-c("vertex","edge")
> ># X<-as.data.frame(x)
> >#
X_NEW<-merge(x=X,y=temp1,by.x="vertex",by.y="before")
> ># remove(X)
> >#
names(X_NEW)[names(X_NEW)=="after"]<-"vertex_new"
> >#
X_NEW2<-merge(x=X_NEW,y=temp1,by.x="edge",by.y="before")
> ># remove(X_NEW,temp1)
> >#
names(X_NEW2)[names(X_NEW2)=="after"]<-"edge_new"
> ># G2<-as.matrix(X_NEW2)
> ># remove(X_NEW2)
> ># G2<-G2[,c(3,4)]
> ># u1<-unique(G2[,1])
> ># u2<-unique(G2[,2])
> ># u<-c(u1,u2)
> ># n<<-length(unique(u))
> ># remove(u1,u2,u)
> >
> >FT_SORTED = numeric(n)
> >for (i in length(FT):1) {
> >  finish_time = FT[i]
> >  FT_SORTED[finish_time] = i
> >}
> >
> >P = numeric(n)
> >FT = numeric(n)
> >
> >#P<<-matrix(c(1:n,rep(0,2*n)),nrow=n,ncol=3) #tracking whether
vertex
> >is explored or not
>
>#colnames(P)<-c("vertex","f","parent_vertex")
> >explore<<-numeric()
> >assign("time",0,envir=globalenv())
> >
> >print('Starting DFS_loop on G')
> >#DFS_LOOP(G2)#2nd DFS
> >explore<<-numeric()
> >
> >G_TEMP <<- G
> >
> >for (i in length(FT_SORTED):1) {
> >  k = FT_SORTED[i]
> >  if (k %!in% explore) {
> >    DFS(k)
> >  }
> >}
> >
> >mscc_temp = which(P==0)
> >scc_temp=FT[mscc_temp]
> >#scc_temp<-P[P[,3]==0,2]
> >scc_temp=sort(scc_temp,decreasing=TRUE)
> >m=length(scc_temp)
> >scc=numeric()
> >for (i in 1:(m-1)){
> >  scc[i]=scc_temp[i]-scc_temp[i+1]
> >}
> >scc[m]<-scc_temp[m]
> >scc_top_5<-tail(sort(scc),5)
> >
> >
> >Thanks,
> >Jing
> >       [[alternative HTML version deleted]]
> >
> >______________________________________________
> >R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> >https://stat.ethz.ch/mailman/listinfo/r-help
> >PLEASE do read the posting guide
> >http://www.R-project.org/posting-guide.html
> >and provide commented, minimal, self-contained, reproducible code.
>
>

-- 
Best regards,

Jie

	[[alternative HTML version deleted]]

R help - Nov 2016 - Kosaraju's SCC Algorithm Running

[R] Kosaraju's SCC Algorithm Running

[R] Kosaraju's SCC Algorithm Running

[R] Kosaraju's SCC Algorithm Running