Let us create an ADT (Graph_ADT) for the implementation of functions on a given graph. The key features of ADT for a given graph analysis are the following:

The vertices are denoted using non-zero integer values, and can additionally store vertex names or some kind of application-based predetermined values.

The following are some ADT functions that are widely used for implementing graph functions:

Each graph algorithm needs to traverse every vertex before it can culminate its execution. The functions firstEdge and nextVertex facilitate such kind of traversing across the graph. It is generally implemented using loops, wherein each vertex searches for all its linked vertices and then obtains their corresponding edge weights.

The following R code implements graph ADT. It takes a number of vertices n as input:

Graph_ADT <- setRefClass(Class = "adjacency_Matrix", 
  fields = list(n = "integer"), 
  methods = list( 
    ## Initialise a graph of n vertices 
    Initialize = function(n){}, 
 
    ## Return number of vertices and edges 
    num_vert = function(){}, 
    num_edges = function(){}, 
    ## Return weight of an edge for a pair of vertices v1 and v2 
    weightEdge = function(v1,v2){}, 
 
    ## Assign weight(wt) of an edge for a pair of vertices v1 and       
    v2 
    assignEdge = function(v1,v2,wt){}, 
 
    ## Delete weight of an edge for a pair of vertices v1 and v2 
    deleteEdge = function(v1,v2){}, 
 
    ## Return first connecting vertex for a given vertex v 
    firstVertex = function(v){}, 
 
    # Return next vertex for a given v and its neighbor w 
    nextVertex = function(v,w){}, 
 
    ## Check for presence of an edge for a pair of vertices v1 and      
    v2 
    isEdge = function(v1,v2){} 
))

The GraphADT function can be implemented using either adjacency matrix or adjacency list representations. In this chapter, a sample implementation of graph ADT is shown using both an adjacency list and adjacency matrix; however, the creation of a graph object has not been addressed. In lieu of the graph object, the assignEdge function can be used to build graphs based on edges.

In the adjacency matrix implementation, a list, mark, stores the output of the setMark function, and the getMark function can be used to extract the mark of a given vertex. The edge matrix mat is an n×n-dimensional array of integers, which store the weights of edges. The rows represent the from vertices, and the columns represent the to vertices. In case of no connection between two vertices, their edge weight is stored as zero:

adjacencyMatrix <-  
setRefClass( Class = "adjacencyMatrix", 
  fields = list(n = "integer"), 
  methods = list( 
    ## Initialise the graph of n vertices 
    Initialize <- function(n){ 
      numVertices <<- as.integer(n)  ## with n vertices 
      numEdges <<- 0L     ## with no connected edges 
      mark <<- list()       ## initialize mark list 
 
      ## initialize the mark of all vertices to 0 (unvisited) 
      for(i in 1:numVertices) 
      mark[[i]] <<- 0L 
 
      ## generate a new nxn matrix with initial weights as 0 
      mat <- matrix() 
      for(i in 1:numVertices) 
      for(j in 1:numVertices) 
      mat[i,j] <<- 0L 
    }, 
 
    ## get number of vertices 
    num_vert <- function() return(numVertices), 
 
    ## get number of edges 
    num_edges <- function() return(numEdges), 
 
    ## return the first adjacent neighbor of vertex index v 
    firstVertex <- function(v){ }, 
 
    ## return next adjacent vertices of index v after  
    ## getting index w using firstVertex 
    nextVertex <- function(v,w){ }, 
 
    ## Assign weight to each connected edge of indices v1 and v2   
    assignEdge <- function(v1,v2,wt){ }, 
 
    ## Delete a connected edge between indices v1 and v2 
    deleteEdge <- function(v1,v2){ }, 
 
    ## Check whether an edge exists between indices v1 and v2 
    isEdge <- function(v1,v2){ 
      return(mat[v1,v2] != 0) }, 
 
    ## Get weight of the connected edge between indices v1 and v2 
    weightEdge <- function(v1,v2){ 
      return(mat[v1,v2]) }, 
 
    ## Get the mark of a vertex of index v1 
    getMark <- function(v1){ 
      return(mark[[v1]]) }, 
 
    ## initialise the mark of a vertex of index v1 with 1 
    initMark <- function(v1,val){  
      mark[[v]] <<- val}
  ))

For a given vertex V, the firstVertex function scans through the row V of the matrix mat to locate the first edge and its corresponding to vertex. If the function fails to find the first vertex, it returns the value n+1. The nextVertex function is used to find the subsequent connected edge for the vertex V. If the edge is found, the nextVertex function will return the index value of the connected vertex, or else it will return the value n+1. The following R snippet can be used to get firstVertex and nextVertex:

## return the first adjacent neighbor of vertex index v 
firstVertex <- function(v){ 
  for(i in 1:numVertices) 
  if(mat[v,i] != 0) 
  return(i) 
  return(numVertices+1) 
}, 
 
## return next adjacent vertices of index v after  
## getting index w using firstVertex 
nextVertex <- function(v,w){ 
  for(i in (w+1):numVertices) 
  if(mat[v,i] != 0)  
  return(i) 
  return(numVertices+1) 
},

The assignEdge function is used to append the edges of a graph in the array, and deleteEdge is used to delete the edge from the array. The weightEdge function is used to return the edge value of the given from and to vertices. The following R code implements the adjacency matrix representation of graphs. It takes in a number of vertices n as an input. The R script for assignEdge and deleteEdge is shown as follows:

 ## Assign weight (wt) to each connected edge of indices v1 and v2 
 assignEdge <- function(v1,v2,wt){ 
   if(wt<0) stop(""Weight should be positive"") 
   ## increase the count of edges as the weights are assigned 
   if(mat[v1,v2] == 0) numEdges <<- numEdges + 1L 
             
   ## replace 0 with the wt 
   mat[v1,v2] <<- wt 
 }, 
                  
 ## Delete a connected edge between indices v1 and v2 
 deleteEdge <- function(v1,v2){ 
   if(mat[v1,v2] != 0) numEdges <<- numEdges - 1L 
   mat[v1,v2] <<- 0 
 }

In case of adjacency lists, the data structure is not as simple as in the case of an adjacency matrix. Here, a list vertex of length n is initialized, and each element in the list is assigned to its edges using the linked lists form of data structure. These lists store the index value of connected vertices along with their edge weights. It takes in a number of vertices n as input:

adjacencyList <-  
setRefClass( Class = "adjacencyList", 
  fields = list(n = "integer"), 
  methods = list( 
    ## Initialise the graph of n vertices 
    Initialize <- function(n){ 
      numVertices <<- n # with n vertices 
      numEdges <<- 0L # with no connected edges 
      mark <<- list() # initialise mark list 
 
      ## initialize the mark of all vertices to 0 (unvisited) 
      for(i in 1:numVertices) 
      mark[[i]] <<- 0L 
 
      ## generate a list of edges each for  
      ## each vertex in the list 
      vertex <- list() 
      for(i in 1:numVertices) 
      vertex[[i]] <<- llistofEdges() 
    }, 
 
    ## get number of vertices 
    num_vert <- function() return(numVertices), 
 
    ## get number of edges 
    num_edges <- function() return(numEdges), 
 
    ## return the first adjacent neighbout of vertex index v 
    firstVertex <- function(v){ }, 
     
    ## return next adjacent vertices of index v after  
    ## getting index w using firstVertex 
    nextVertex <- function(v,w){ }, 
     
    ## Assign weight to each connected edge of indices v1 and v2     
    assignEdge <- function(v1,v2,wt){ }, 
     
    ## Delete a connected edge between indices v1 and v2 
    deleteEdge <- function(v1,v2){ }, 
     
    ## Check whether an edge exists between indices v1 and v2 
    isEdge <- function(v1,v2){ 
      pos <- currentPos(vertex[[v1]], firstAdjVert(vertex[[v1]])) 
      while(pos < length(vertex[[v1]])){ 
        adjVert <- nextAdjVertex(vertex[[v1]],vertex[[v1]][pos]) 
        if(adjVert == v2){ 
          return(TRUE)} else {pos = pos+1 } 
        } 
      }, 
 
      ## Get weight of the connected edge between indices v1 and        
      v2 
      weightEdge <- function(v1,v2){ 
        if(isEdge(v1,v2)){ 
          adjEdge <- getValue(vertex[[v1]],v2) 
          return(adjEdge) 
        } else {return (0)} 
      }, 
 
      ## Get the mark of a vertex of index v1 
      getMark <- function(v1){ 
        return(mark[[v1]]) 
      }, 
 
      ## initialise the mark of a vertex of index v1 with 1 
      initMark <- function(v1,val){ 
        mark[[v]] <<- val 
      } ))

The functions firstVertex and nextVertex scan through the list to determine adjacent vertices using the R function as follows:

## return the first adjacent neighbour of vertex index v 
firstVertex <- function(v){ 
  if(length(vertex[[v]]) == 0) 
  ## indicates no adjacent neighbour 
  return(numVertices+1) 
  ## Move to the first adjacent vertex  
  adjVert <<- firstAdjVert(vertex[[v]])  
  ## get the current position of AdjVert 
  pos <<- currentPos(vertex[[v]],adjVert) 
  ## get value of connecting edge 
  adjEdge <<- getValue(vertex[[v]],adjVert) 
  return(adjVert) 
}, 
 
## return next adjacent vertices of index v after  
## getting index w using firstVertex 
nextVertex <- function(v,w){ 
  if(isEdge(v,w)){ 
    if(pos+1 > length(vertex[[v]])){ 
      ## move the next adjacent vertex of w 
      adjVert <<- nextAdjVertex(vertex[[v]],w) 
      ## get the current position of adjcent vertex 
      pos <<- currentPos(vertex[[v]],adjVert) 
      ## get value of connecting edge 
      adjEdge <<- getValue(vertex[[v]],adjVert) 
      return(adjVert) 
    } 
    ## no connecting edge 
  } else return(numVertices+1)  
},

The functions assignEdge and deleteEdge traverse across the linked lists of a given vertex. The following R code implements the adjacency list representation of graphs:

## Assign weight (wt) to each connected edge of indices v1 and v2 assignEdge <- function(v1,v2,wt){ 
  if(wt<0) stop("Weight should be positive") 
  ##check whether edge exists between v1 and v2 
  if(isEdge(v1,v2)){ 
    ## insert vertex v2 along with edge weight wt 
    insertVertex(vertex[[v1]],v2,wt) 
  }  
}, 
 
## Delete a connected edge between indices v1 and v2 
deleteEdge <- function(v1,v2){ 
  if(isEdge(v1,v2)){  
    removeEdge(v1,v2) 
    numEdges <<- numEdges - 1L 
  } 
},