################################################### ### 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)