## ----Setup, include = FALSE--------------------------------------------------- library(RBGL) library(Rgraphviz) library(XML) ## ----bfDemo------------------------------------------------------------------- con <- file(system.file("XML/bfsex.gxl", package="RBGL")) bf <- fromGXL(con) close(con) ## ----figbf, echo = FALSE, eval = FALSE---------------------------------------- # plot(bf, main="a) Breath-First Search Example") ## ----dfDemo------------------------------------------------------------------- con <- file(system.file("XML/dfsex.gxl", package="RBGL")) df <- fromGXL(con) close(con) ## ----figdf, echo = FALSE, eval = FALSE---------------------------------------- # plot(df, main="b) Depth-First Search Example") ## ----dijkstraDemo------------------------------------------------------------- con <- file(system.file("XML/dijkex.gxl", package="RBGL")) dijk <- fromGXL(con) close(con) ## ----figdijk, echo = FALSE, eval = FALSE-------------------------------------- # plot(dijk, main="c) Dijkstra's Example") ## ----connDemo----------------------------------------------------------------- con <- file(system.file("XML/conn.gxl", package="RBGL")) coex <- fromGXL(con) close(con) ## ----figcoex, echo = FALSE, eval = FALSE-------------------------------------- # plot(coex, main="d) Coex Example") ## ----conn2Demo---------------------------------------------------------------- con <- file(system.file("XML/conn2.gxl", package="RBGL")) coex2 <- fromGXL(con) close(con) ## ----figcoex2, echo = FALSE, eval = FALSE------------------------------------- # plot(coex2, main="e) Coex2 Example") ## ----conn2iDemo--------------------------------------------------------------- con <- file(system.file("XML/conn2iso.gxl", package="RBGL")) coex2i <- fromGXL(con) close(con) ## ----figcoex2i, echo = FALSE, eval = FALSE------------------------------------ # plot(coex2i, main="f) Coex2 Isomorphism Example") ## ----kmstDemo----------------------------------------------------------------- con <- file(system.file("XML/kmstEx.gxl", package="RBGL")) km <- fromGXL(con) close(con) ## ----figkmst, echo = FALSE, eval = FALSE-------------------------------------- # plot(km, main="g) Kruskal MST Example") ## ----bicoDemo----------------------------------------------------------------- con <- file(system.file("XML/biconn.gxl", package="RBGL")) bicoex <- fromGXL(con) close(con) ## ----figbico, echo = FALSE, eval = FALSE-------------------------------------- # plot(bicoex, main="h) Biconnected Component Example") ## ----ospfDemo----------------------------------------------------------------- con <- file(system.file("XML/ospf.gxl", package="RBGL")) ospf <- fromGXL(con) close(con) ## ----figospf, echo = FALSE, eval = FALSE-------------------------------------- # plot(ospf, main="i) Ospf Example") ## ----zzDemo------------------------------------------------------------------- con <- file(system.file("dot/joh.gxl", package="RBGL")) joh <- fromGXL(con) close(con) ## ----figjoh, echo = FALSE, eval = FALSE--------------------------------------- # plot(joh, main="j) joh Example") ## ----hcsDemo------------------------------------------------------------------ con <- file(system.file("XML/hcs.gxl", package="RBGL")) hcs <- fromGXL(con) close(con) ## ----fighcs, echo = FALSE, eval = FALSE--------------------------------------- # plot(hcs, main="k) HCS Example") ## ----kclexDemo---------------------------------------------------------------- con <- file(system.file("XML/snacliqueex.gxl", package="RBGL")) kclex <- fromGXL(con) close(con) ## ----figkclex, echo = FALSE, eval = FALSE------------------------------------- # plot(kclex, main="l) kCliques Example") ## ----kcoexDemo---------------------------------------------------------------- con <- file(system.file("XML/snacoreex.gxl", package="RBGL")) kcoex <- fromGXL(con) close(con) ## ----figkcoex, echo = FALSE, eval = FALSE------------------------------------- # plot(kcoex, main="m) kCores Example") ## ----layout, echo = FALSE----------------------------------------------------- layout_matrix_1 <- matrix(1:4, ncol = 2) ## ----fig.cap = "The example graphs (I).", fig.height = 8, echo = FALSE-------- layout(layout_matrix_1) plot(bf, main="a) Breath-First Search Example") plot(dijk, main="c) Dijkstra's Example") plot(df, main="b) Depth-First Search Example") plot(coex, main="d) Coex Example") ## ----fig.cap = "The example graphs (II).", fig.height = 8, echo = FALSE------- layout(layout_matrix_1) plot(coex2, main="e) Coex2 Example") plot(km, main="g) Kruskal MST Example") plot(coex2i, main="f) Coex2 Isomorphism Example") plot(bicoex, main="h) Biconnected Component Example") ## ----fig.cap = "The example graphs (III).", fig.height = 8, echo = FALSE------ layout(layout_matrix_1) plot(hcs, main="k) HCS Example") plot(kcoex, main="m) kCores Example") plot(kclex, main="l) kCliques Example") ## ----fdpic, fig.cap = "File dependency digraph example from Boost library", fig.height = 7, results = "hide", echo = FALSE---- data(FileDep) FileDep plot(FileDep) ## ----showFileDep-------------------------------------------------------------- data(FileDep) FileDep ## ----echo = FALSE------------------------------------------------------------- layout_matrix_2 <- matrix(1:2, ncol = 2) ## ----figdfsex, fig.cap = "a) The graph for depth-first-search example b) The graph for depth-first-search example, showing search orders.", echo = FALSE, results = "hide"---- layout(layout_matrix_2) print(dfs.res <- dfs(df, "y")) plot(df, main="a) DFS Example") dfsNattrs <- makeNodeAttrs(df) dfsNattrs$label[dfs.res$discovered] <- 1:numNodes(df) plot(df, nodeAttrs=dfsNattrs, main="b) DFS Example with search order") ## ----DFSdemo------------------------------------------------------------------ print(dfs.res <- dfs(df, "y")) ## ----figdfs1, echo = FALSE, eval = FALSE-------------------------------------- # plot(df, main="a) DFS Example") ## ----figdfs2, echo = FALSE, eval = FALSE-------------------------------------- # dfsNattrs <- makeNodeAttrs(df) # dfsNattrs$label[dfs.res$discovered] <- 1:numNodes(df) # plot(df, nodeAttrs=dfsNattrs, main="b) DFS Example with search order") ## ----figbfsex, fig.cap = "a) The graph for breadth-first-search example b) The graph for breadth-first-search example, showing search orders.", echo = FALSE, results = "hide"---- layout(layout_matrix_2) print(bfs.res <- bfs(bf,"s")) plot(bf, main="a) BFS Example") bfsNattrs <- makeNodeAttrs(bf) bfsNattrs$label[bfs.res] <- 1:numNodes(bf) plot(bf, nodeAttrs=bfsNattrs, main="b) BFS Example with search order") ## ----BFSdemo------------------------------------------------------------------ print(bfs.res <- bfs(bf,"s")) ## ----figbfs1, echo = FALSE, eval = FALSE-------------------------------------- # plot(bf, main="a) BFS Example") ## ----figbfs2, echo = FALSE, eval = FALSE-------------------------------------- # bfsNattrs <- makeNodeAttrs(bf) # bfsNattrs$label[bfs.res] <- 1:numNodes(bf) # plot(bf, nodeAttrs=bfsNattrs, main="b) BFS Example with search order") ## ----dijkdemo1---------------------------------------------------------------- nodes(dijk) edgeWeights(dijk) dijkstra.sp(dijk) ## ----dijkdemo2---------------------------------------------------------------- nodes(ospf)[6] dijkstra.sp(ospf,nodes(ospf)[6]) sp.between(ospf, "RT6", "RT1") ## ----figospfs, fig.width = 6, fig.cap = "Network example from BGL.", echo = FALSE---- plot(ospf) ## ----bellmanfordDemo---------------------------------------------------------- dd <- coex2 nodes(dd) bellman.ford.sp(dd) bellman.ford.sp(dd,nodes(dd)[2]) ## ----DAGDemo------------------------------------------------------------------ dd <- coex2 dag.sp(dd) dag.sp(dd,nodes(dd)[2]) ## ----johnsonDemo-------------------------------------------------------------- zz <- joh edgeWeights(zz) johnson.all.pairs.sp(zz) ## ----floydwarshallDemo-------------------------------------------------------- floyd.warshall.all.pairs.sp(coex) ## ----figjohn, fig.cap = "Example: Johnson-all-pairs-shortest-paths example", fig.small = TRUE, echo = FALSE---- plot(zz) ## ----KMSTdemo----------------------------------------------------------------- mstree.kruskal(km) ## ----primDemo----------------------------------------------------------------- mstree.prim(coex2) ## ----figkm, fig.cap = "Kruskal MST examples.", echo = FALSE, results = "hide"---- 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)) layout(layout_matrix_2) plot(km, main="g) Kruskal MST Example") plot(km1, main="Modified Kruskal MST example") ## ----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)) ## ----figkm1, echo = FALSE, eval = FALSE--------------------------------------- # plot(km1, main="Modified Kruskal MST example") ## ----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) ## ----biConnCompdemo----------------------------------------------------------- biConnComp(bicoex) articulationPoints(bicoex) ## ----figbicoex, fig.width = 6, fig.cap = "Biconnected components example from Boost library.", echo = FALSE---- plot(bicoex) ## ----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) x <- init.incremental.components(jcoex) incremental.components(jcoex) same.component(jcoex, "A", "A1") ## ----figjcoex, fig.width = 6, fig.cap = "Example on incremental components: a graph connecting coexand hcs.", echo = FALSE---- plot(jcoex) ## ----MaxFlowdemo-------------------------------------------------------------- edgeWeights(dijk) edmonds.karp.max.flow(dijk, "B", "D") push.relabel.max.flow(dijk, "C", "B") ## ----SparseMatrixOrderingdemo------------------------------------------------- dijk1 <- ugraph(dijk) cuthill.mckee.ordering(dijk1) minDegreeOrdering(dijk1) sloan.ordering(dijk1) ## ----edgeConndemo------------------------------------------------------------- edgeConnectivity(coex) ## ----tsortDemo1--------------------------------------------------------------- tsort(FileDep) ## ----tsortDemo2, warning = FALSE---------------------------------------------- FD2 <- FileDep # now introduce a cycle FD2 <- addEdge(from="bar_o", to="dax_h", FD2) tsort(FD2) ## ----Isomorphismdemo---------------------------------------------------------- isomorphism(dijk, coex2) isomorphism(coex2i, coex2) ## ----fig.small = TRUE, fig.cap = "Example conn2i", echo = FALSE--------------- plot(coex2i) ## ----VertexColoringdemo------------------------------------------------------- sequential.vertex.coloring(coex) ## ----wavefrontdemo------------------------------------------------------------ ss <- 1 ith.wavefront(dijk, ss) maxWavefront(dijk) aver.wavefront(dijk) rms.wavefront(dijk) ## ----Centralitydemo, echo = TRUE---------------------------------------------- brandes.betweenness.centrality(coex) betweenness.centrality.clustering(coex, 0.1, TRUE) ## ----mincutdemo--------------------------------------------------------------- minCut(coex) ## ----highlyConnSGdemo--------------------------------------------------------- highlyConnSG(coex) highlyConnSG(hcs) ## ----MaxCliquedemo------------------------------------------------------------ maxClique(coex) maxClique(hcs) ## ----IsTriangulateddemo------------------------------------------------------- is.triangulated(coex) is.triangulated(hcs) ## ----Separatesdemo------------------------------------------------------------ separates("B", "A", "E", km) separates("B", "A", "C", km) ## ----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") ## ----figkcores, fig.small = TRUE, fig.cap = "K-cores Example.", echo = FALSE---- plot(kcoex) ## ----kCliquesdemo------------------------------------------------------------- kCliques(kclex) ## ----figkcliques, fig.small = TRUE, fig.cap = "K-cliques Example", echo = FALSE---- plot(kclex)