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:
mark
array, which can assist algorithms in traversing along the graphThe 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:
num_vert
: This function returns the number of vertices for a given graph.num_edge
: This function returns the number of edges for a given graph.weightEdge
: This function returns the weight of an edge connecting two adjacent vertices. Its input is a pair of two connected vertices and its output is a numeric value indicating its weight.assignEdge
: This function is used to assign weight to a given edge of a graph. The input is a pair of vertices. It can take in only a non-zero positive value, as a zero value means no connection (thereby no assignment required) and a negative value can skew the computational results.deleteEdge
: This function is used to delete the weight of a given edge. The input is a pair of vertices, which has a connected edge.firstVertex
: This function returns the index of the first edge vertex based on a sorted list of vertices, which are connected to a given vertex. The input is a vertex for a given graph.nextVertex
: This function returns the subsequent index of vertices for a given pair of connected vertices such that the returned vertex will have an edge connecting to the first vertex. Assume that V1 is connected with V2 and V3 such that the index values of V2 are less than V3. Then, the firstVertex
function will return the edge vertex of V1 as V2 (as the index value of V2 is less than V3), and the nextVertex
function will return V3, as it is a subsequent connected vertex index of V1 for a given V2.isEdge
: This function returns a Boolean number, where 1 represents the presence of an edge, and 0 represents the absence of an edge.getMark
: This function returns the mark of a given vertex from an array mark
.initMark
: This function marks the unmarked vertex in an array mark
.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
}
},