###################################################
### chunk number 1: 
###################################################
library("RBGL")
library(Rgraphviz)
library("XML")


###################################################
### chunk number 2: bfDemo
###################################################
con <- file(system.file("XML/bfsex.gxl", package="RBGL"))
bf <- fromGXL(con)
close(con)


###################################################
### chunk number 3: figbf
###################################################
  plot(bf, main="a) Breath-First Search Example")


###################################################
### chunk number 4: dfDemo
###################################################
con <- file(system.file("XML/dfsex.gxl", package="RBGL"))
df <- fromGXL(con)
close(con)


###################################################
### chunk number 5: figdf
###################################################
  plot(df, main="b) Depth-First Search Example")


###################################################
### chunk number 6: dijkstraDemo
###################################################
con <- file(system.file("XML/dijkex.gxl", package="RBGL"))
dijk <- fromGXL(con)
close(con)


###################################################
### chunk number 7: figdijk
###################################################
 plot(dijk, main="c) Dijkstra's Example")


###################################################
### chunk number 8: connDemo
###################################################
con <- file(system.file("XML/conn.gxl", package="RBGL"))
coex <- fromGXL(con)
close(con)


###################################################
### chunk number 9: figcoex
###################################################
 plot(coex, main="d) Coex Example")


###################################################
### chunk number 10: conn2Demo
###################################################
con <- file(system.file("XML/conn2.gxl", package="RBGL"))
coex2 <- fromGXL(con)
close(con)


###################################################
### chunk number 11: figcoex2
###################################################
  plot(coex2, main="e) Coex2 Example")


###################################################
### chunk number 12: conn2iDemo
###################################################
con <- file(system.file("XML/conn2iso.gxl", package="RBGL"))
coex2i <- fromGXL(con)
close(con)


###################################################
### chunk number 13: figcoex2i
###################################################
  plot(coex2i, main="f) Coex2 Isomorphism Example")


###################################################
### chunk number 14: kmstDemo
###################################################
con <- file(system.file("XML/kmstEx.gxl", package="RBGL"))
km <- fromGXL(con)
close(con)


###################################################
### chunk number 15: figkmst
###################################################
  plot(km, main="g) Kruskal MST Example")


###################################################
### chunk number 16: bicoDemo
###################################################
con <- file(system.file("XML/biconn.gxl", package="RBGL"))
bicoex <- fromGXL(con)
close(con)


###################################################
### chunk number 17: figbico
###################################################
  plot(bicoex, main="h) Biconnected Component Example")


###################################################
### chunk number 18: ospfDemo
###################################################
con <- file(system.file("XML/ospf.gxl", package="RBGL"))
ospf <- fromGXL(con)
close(con)


###################################################
### chunk number 19: figospf
###################################################
  plot(ospf, main="i) Ospf Example")


###################################################
### chunk number 20: zzDemo
###################################################
con <- file(system.file("dot/joh.gxl", package="RBGL"))
joh <- fromGXL(con)
close(con)


###################################################
### chunk number 21: figjoh
###################################################
  plot(joh, main="j) joh Example")


###################################################
### chunk number 22: hcsDemo
###################################################
con <- file(system.file("XML/hcs.gxl", package="RBGL"))
hcs <- fromGXL(con)
close(con)


###################################################
### chunk number 23: fighcs
###################################################
  plot(hcs, main="k) HCS Example")


###################################################
### chunk number 24: kclexDemo
###################################################
con <- file(system.file("XML/snacliqueex.gxl", package="RBGL"))
kclex <- fromGXL(con)
close(con)


###################################################
### chunk number 25: figkclex
###################################################
  plot(kclex, main="l) kCliques Example")


###################################################
### chunk number 26: kcoexDemo
###################################################
con <- file(system.file("XML/snacoreex.gxl", package="RBGL"))
kcoex <- fromGXL(con)
close(con)


###################################################
### chunk number 27: figkcoex
###################################################
  plot(kcoex, main="m) kCores Example")


###################################################
### chunk number 28: showFileDep
###################################################
data(FileDep)
FileDep


###################################################
### chunk number 29: figfd
###################################################
z <- plot(FileDep)


###################################################
### chunk number 30: DFSdemo
###################################################
print(dfs.res <- dfs(df, "y"))


###################################################
### chunk number 31: figdfs1
###################################################
plot(df, main="a) DFS Example")


###################################################
### chunk number 32: figdfs2
###################################################
dfsNattrs <- makeNodeAttrs(df)
dfsNattrs$label[dfs.res$discovered] <- 1:numNodes(df)
plot(df, nodeAttrs=dfsNattrs, main="b) DFS Example with search order")


###################################################
### chunk number 33: BFSdemo
###################################################
print(bfs.res <- bfs(bf,"s"))


###################################################
### chunk number 34: figbfs1
###################################################
plot(bf, main="a) BFS Example")


###################################################
### chunk number 35: figbfs2
###################################################
bfsNattrs <- makeNodeAttrs(bf)
bfsNattrs$label[bfs.res] <- 1:numNodes(bf)
plot(bf, nodeAttrs=bfsNattrs, main="b) BFS Example with search order")


###################################################
### chunk number 36: dijkdemo1
###################################################
nodes(dijk)
edgeWeights(dijk)
dijkstra.sp(dijk)


###################################################
### chunk number 37: dijkdemo2
###################################################
nodes(ospf)[6]
dijkstra.sp(ospf,nodes(ospf)[6])
sp.between(ospf, "RT6", "RT1")


###################################################
### chunk number 38: figospf
###################################################
z <- plot(ospf)


###################################################
### chunk number 39: bellmanfordDemo
###################################################
dd <- coex2
nodes(dd)
bellman.ford.sp(dd)
bellman.ford.sp(dd,nodes(dd)[2])


###################################################
### chunk number 40: DAGDemo
###################################################
dd <- coex2
dag.sp(dd)
dag.sp(dd,nodes(dd)[2])


###################################################
### chunk number 41: johnsonDemo
###################################################
zz <- joh
edgeWeights(zz)
johnson.all.pairs.sp(zz)


###################################################
### chunk number 42: figjoh
###################################################
z <- plot(zz)


###################################################
### chunk number 43: floydwarshallDemo
###################################################
floyd.warshall.all.pairs.sp(coex)


###################################################
### chunk number 44: KMSTdemo
###################################################
mstree.kruskal(km)


###################################################
### chunk number 45: primDemo
###################################################
mstree.prim(coex2)


###################################################
### chunk number 46: conndemo
###################################################
km1 <- km
km1 <- graph::addNode(c("F","G","H"), km1)
km1 <- addEdge("G", "H", km1, 1)
km1 <- addEdge("H", "G", km1, 1)
connectedComp(ugraph(km1))


###################################################
### chunk number 47: figkm1
###################################################
plot(km1, main="Modified Kruskal MST example")


###################################################
### chunk number 48: sconndemo
###################################################
km2 <- km
km2 <- graph::addNode(c("F","G","H"), km2)
km2 <- addEdge("G", "H", km2, 1)
km2 <- addEdge("H", "G", km2, 1)
strongComp(km2)


###################################################
### chunk number 49: biConnCompdemo
###################################################
biConnComp(bicoex)
articulationPoints(bicoex)


###################################################
### chunk number 50: figbicoex
###################################################
z <- plot(bicoex)


###################################################
### chunk number 51: incrCompdemo
###################################################
jcoex <- join(coex, hcs)
x <- init.incremental.components(jcoex)
incremental.components(jcoex)
same.component(jcoex, "A", "F")
same.component(jcoex, "A", "A1")
jcoex <- addEdge("A", "A1", jcoex)
incremental.components(jcoex)
same.component(jcoex, "A", "A1")


###################################################
### chunk number 52: figjcoex
###################################################
z <- plot(jcoex)


###################################################
### chunk number 53: MaxFlowdemo
###################################################
edgeWeights(dijk)
edmunds.karp.max.flow(dijk, "B", "D")
push.relabel.max.flow(dijk, "C", "B")


###################################################
### chunk number 54: SparseMatrixOrderingdemo
###################################################
dijk1 <- ugraph(dijk)
cuthill.mckee.ordering(dijk1)
minDegreeOrdering(dijk1)
sloan.ordering(dijk1)


###################################################
### chunk number 55: edgeConndemo
###################################################
edgeConnectivity(coex)


###################################################
### chunk number 56: tsortDemo1
###################################################
tsort(FileDep)


###################################################
### chunk number 57: tsortDemo2
###################################################
FD2 <- FileDep
# now introduce a cycle
FD2 <- addEdge(from="bar_o", to="dax_h", FD2)
tsort(FD2)


###################################################
### chunk number 58: Layoutdemo
###################################################
# library(Rgraphviz)
plot(coex, "neato")


###################################################
### chunk number 59: figneato
###################################################
z <- plot(coex, "neato")


###################################################
### chunk number 60: Layoutdemo2
###################################################
randomGraphLayout(coex)
circleLayout(coex)
kamadaKawaiSpringLayout(coex)
fruchtermanReingoldForceDirectedLayout(coex, 10, 10)


###################################################
### chunk number 61: Layoutdemo3
###################################################
crudeGraphPlot <- function(g, alg=circleLayout, ...) {
#
# the alg parameter is a function that computes the
# layout of g, returning it as a list of length 1
# with two rows: top row is x coordinates, bottom is
# y coordinates, and node names are used as colnames
# the ... are passed to segments()
#
  layout <- alg(g)
  plot( layout[1,], layout[2,], pch=nodes(g), axes=FALSE,
    xlab="", ylab="", main=substitute(g), cex=1.4 )
  ee <- edges(g)
  src <- names(ee)
  ds <- function(nn1, nn2, lob) segments(lob[1,nn1], lob[2,nn1],
        lob[1,nn2], lob[2,nn2], ...)
  for (s in src) sapply(ee[[s]], function(x) ds(s, x, layout))
  invisible(NULL)
}

crudeGraphPlot(coex)
crudeGraphPlot(coex, alg=kamadaKawaiSpringLayout, col="green")


###################################################
### chunk number 62: figlayout1
###################################################
crudeGraphPlot(coex)


###################################################
### chunk number 63: figlayout2
###################################################
crudeGraphPlot(coex, alg=kamadaKawaiSpringLayout, col="green")


###################################################
### chunk number 64: Isomorphismdemo
###################################################
isomorphism(dijk, coex2)
isomorphism(coex2i, coex2)


###################################################
### chunk number 65: figcoex2i
###################################################
z <- plot(coex2i)


###################################################
### chunk number 66: VertexColoringdemo
###################################################
sequential.vertex.coloring(coex)


###################################################
### chunk number 67: transClosuredemo
###################################################
dijk.tc = transitive.closure(dijk)


###################################################
### chunk number 68: figdijkTC
###################################################
  plot(dijk.tc, main="b) Transitive closure")


###################################################
### chunk number 69: wavefrontdemo
###################################################
ss <- 1
ith.wavefront(dijk, ss)
maxWavefront(dijk)
aver.wavefront(dijk)
rms.wavefront(dijk)


###################################################
### chunk number 70: Centralitydemo
###################################################
brandes.betweenness.centrality(coex)
betweenness.centrality.clustering(coex, 0.1, TRUE)


###################################################
### chunk number 71: mincutdemo
###################################################
minCut(coex)


###################################################
### chunk number 72: highlyConnSGdemo
###################################################
highlyConnSG(coex)
highlyConnSG(hcs)


###################################################
### chunk number 73: MaxCliquedemo
###################################################
maxClique(coex)
maxClique(hcs)


###################################################
### chunk number 74: IsTriangulateddemo
###################################################
is.triangulated(coex)
is.triangulated(hcs)


###################################################
### chunk number 75: Separatesdemo
###################################################
separates("B", "A", "E", km)
separates("B", "A", "C", km)


###################################################
### chunk number 76: kCoresdemo1
###################################################
kCores(kcoex)
kcoex2 <- coex2
kCores(kcoex2)
kCores(kcoex2, "in")
kCores(kcoex2, "out")
g1 <- addEdge("C", "B", kcoex2)
kCores(g1, "in")
g2 <- addEdge("C", "A", kcoex2)
kCores(g2, "out")


###################################################
### chunk number 77: figkcores
###################################################
z <- plot(kcoex)


###################################################
### chunk number 78: kCliquesdemo
###################################################
kCliques(kclex)


###################################################
### chunk number 79: figkcliques
###################################################
z <- plot(kclex)