% NOTE

ONLY EDIT THE .Rnw FILE!!! The .tex file is % likely to be overwritten. % \VignetteDepends{Biobase,graph,RBGL} % \VignetteIndexEntry{Introductory Graph Lab} % \VignetteKeywords{tutorial} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[a4paper,11pt]{article} \usepackage{a4wide} \usepackage{times}

\newcommand{\Robject}[1]{\texttt{#1}} \newcommand{\Rpackage}[1]{\textit{#1}}

\begin{document} \title{Introductory Graph Lab} \author{Robert Gentleman, Wolfgang Huber, Vince Carey} \maketitle

<>= library(graph) library(Rgraphviz) @

\textbf{Note for MS Windows users:} The R package \Rpackage{Rgraphviz} is an interface to the graph layout program \textit{graphviz}. With this, you can directly visualize graphs from within R, for example using the \Robject{plot} method. Currently, \Rpackage{Rgraphviz} does not run under MS-Windows. However, \textit{graphviz} does. Here, we provide a simple function that uses files for a uni-directional communication from R to \textit{graphviz}.

<>= writeDot <- function(g, y="dot", f) { filegxl <- paste(f, ".gxl", sep="") filedot <- paste(f, ".dot", sep="") filegif <- paste(f, ".gif", sep="") saveXML(toGXL(g)$value(), file=filegxl) #$ system(paste("gxl2dot", filegxl, ">", filedot)) system(paste(y, "-Tgif", filedot, ">", filegif)) return(filegif) } @

%------------------------------------------------------------ \section{The \Rpackage{graph} package} %------------------------------------------------------------

First, we create a simple example graph:

<>= edges <- list(a=list(edges=2:3), b=list(edges=2:3), c=list(edges=c(2,4)), d=list(edges=1)) g <- new("graphNEL", nodes=letters[1:4], edgeL=edges, edgemode="directed") g @

and plot it:

<>= plot(g, main="My first graph") writeDot(g, f="myfirstgraph") @

We can find out about the nodes, edges, and node degrees of $\Robject{g}$:

<>= nodes(g) edges(g) degree(g) @

The functions \Robject{adj} and \Robject{acc} provide the names of the \textit{adjacent} and \textit{accessible} nodes:

<>= edges <- list(a=list(edges=2:3), b=list(edges=2:3), c=list(edges=c(2,4)), d=list(edges=1), e=list(edges=6,7), f=list(edges=7), g=list(edges=7)) g <- new("graphNEL", nodes=letters[1:7], edgeL=edges, edgemode="directed") plot(g, main="Example for adj, acc")

adj(g, c("b", "c")) acc(g, c("b", "c")) @

From the directed graph, we can construct the corresponding \textit{undirected graph}:

<>= ug <- ugraph(g) plot(ug, main="Undirected Graph") @

... and a \textit{subgraph}

<>= sg <- subGraph(c("a", "b", "c", "f"), ug) plot(sg, main="subGraph") @

... and the \textit{boundary} of the subgraph within the larger graph.

<>= bd <- boundary(sg, ug) bd @

We can also define \textit{edge weights} on our graphs:

<>= edges <- list(a=list(edges=2:3, weights=1:2), b=list(edges=2:3, weights=c(0.5, 1)), c=list(edges=c(2,4), weights=c(2:1)), d=list(edges=1, weights=3)) g <- new("graphNEL", nodes=letters[1:4], edgeL=edges, edgemode="directed") edgeWeights(g) @

\textit{Graph manipulation} functions allow to add and remove edges:

<>= g1 <- addNode("e", g) g2 <- removeNode("d", g)

## addEdge(from, to, graph, weights) g3 <- addEdge("e", "a", g1, pi/2)

## removeEdge(from, to, graph) g4 <- removeEdge("e", "a", g3)

identical(g4, g1)

## par(mfrow=c(2,1)) ## plot(ug) ## g5 <- combineNodes(c("b", "c"), ug, "w") ## plot(g5) @

\textit{Graph algebra}: complement, union, intersection

<>= par(mfrow=c(2,3)) V <- letters[1:4] set.seed(4713) g1 <- randomGraph(V, 1, .55) g2 <- randomGraph(V, 1, .55) plot(g1, main="g1") plot(g2, main="g2") plot(complement(g1), main="complement(g1)") plot(intersection(g1, g2), main="intersection(g1,g2)") plot(union(g1, g2), main="union(g1,g2)") par(mfrow=c(1,1)) @

%------------------------------------------------------------ \section{The \Rpackage{RBGL} package} %------------------------------------------------------------

The \Rpackage{tsort} function calculates the \textit{topological sort order} for a directed acyclic graph. The topological sort order is defined as follows: if edge $(u,v)$ appears in the graph, then $u$ comes before $v$ in the ordering.

<>= library(RBGL) data(FileDep) plot(FileDep, main="Topological sort order example graph")

ts <- tsort(FileDep) nodes(FileDep)[ts+1] @

The function \Rpackage{mstree.kruskal} provides Kruskal's minimum spanning tree:

<>= km <- fromGXL(file(system.file("GXL/kmstEx.gxl", package = "graph"))) ms <- mstree.kruskal(km)

<>= e <- buildEdgeList(km) n <- buildNodeList(km) for(i in 1:ncol(ms$edgeList)) e[[paste(ms$nodes[ms$edgeList[,i]], collapse="~")]]@attrs$color <- "red" z <- agopen(nodes=n, edges=e, edgeMode="directed", name="") plot(z, main="Topological sort order example graph") @

\textit{Breadth first} and \textit{depth first} search:

<>= dd <- fromGXL(file(system.file("XML/bfsex.gxl", package = "RBGL"))) plot(dd, main="Breadth first search example graph")

br <- bfs(dd, "r") nodes(dd)[br]

bs <- bfs(dd, "s") nodes(dd)[bs] @

<>= dd <- fromGXL(file(system.file("XML/dfsex.gxl", package = "RBGL"))) plot(dd, main="Depth first search example graph")

df <- dfs(dd, "u") nodes(dd)[df$discovered] nodes(dd)[df$finish] @

<>= g <- fromGXL(file(system.file("XML/dijkex.gxl", package = "RBGL"))) plot(g, main="Shortest path example graph")

sp.between(g, "E", "C") dijkstra.sp(g) @

<>= g1 <- removeEdge(A, C, g) g1 <- removeEdge(D, E, g1) g1 <- removeEdge(B, E, g1) g1 <- removeEdge(E, B, g1) connectedComp(g) connectedComp(g1)

par(mfrow=c(1,2)) plot(g, main="g") plot(g1, main="g1") @

<>= km <- fromGXL(file(system.file("XML/kmstEx.gxl",package="RBGL"))) km@nodes <- c(km@nodes,"F","G","H") km@edgeL$F <- list(edges=numeric(0)) km@edgeL$G <- list(edges=8) km@edgeL$H <- list(edges=7)

strongComp(km) connectedComp(ugraph(km)) plot(km, main="km: connected components example graph") @

<>= g <- fromGXL(file(system.file("XML/conn.gxl",package="RBGL"))) edgeConnectivity(g) plot(g, main="g: edgeConnectivity example graph") @

<>= attrs <- getDefaultAttrs() attrs$node$fillcolor <- red attrs$node$height <- 1 attrs$node$label <- myplot <- function(m) plot(FileDep, m, main=m, attrs=attrs)

par(mfrow=c(1,3)) myplot("dot") myplot("neato") myplot("twopi") @

\end{document}