Graph Basics

University Project #Data Science#Mathematics

Graph Basics #

Some very simple graph functions just to re-familarize myself with basic graphs.

.rmd knitted with execution results available for download here

1
if (!require("igraph")) {
2
    install.packages("igraph")
3
    library(igraph)
4
}

1
## Loading required package: igraph

1
##
2
## Attaching package: 'igraph'

1
## The following objects are masked from 'package:stats':
2
##
3
##     decompose, spectrum

1
## The following object is masked from 'package:base':
2
##
3
##     union

Q2#

(i,j), i != j in E if: 1. i + j in S 2. | i - j | in S

Generate graph using input vertex set

1
# list search function, could use sapply or smth
2
# returns true if val is in list, else returns false
3
is_in = function(val, list){
4
  for(i in 1:length(list)){
5
    if(val == list[i]){
6
      return(TRUE)
7
    }
8
  }
9
  return(FALSE)
10
}
11

12
q2 = function(v){
13
  index = 1
14
  e = c()
15
  # loop through each vertex
16
  for(i in 1:length(v)){
17
    # check all the other vertex
18
    for(j in 1:length(v)){
19
      # if not the same vertex, and conditions 1 or 2 are True
20
      if(v[i] != v[j] & ( is_in((v[i]+v[j]),v) | is_in(abs(v[i]-v[j]),v))){
21
        # add to edge list
22
        e[index] = as.character(v[i])
23
        e[index+1] = as.character(v[j])
24
        index = index + 2
25
      }
26
    }
27
  }
28
  # generate graph
29
  g = make_graph(e,directed = FALSE)
30
  plot(g)
31
}

1
q2(c(2,3,4,7,11,13))

Q3#

Given a set of vertices, A, and another set S

There exists an arc between vertices i,j in V if j-i in S and i != j

1
q3 = function(A,S){
2
  index = 1
3
  e = c()
4
  # loop through each vertex
5
  for(i in 1:length(A)){
6
    # check all the other vertex
7
    for(j in 1:length(A)){
8
      # if not the same vertex, and A[j]-A[i] in S
9
      if(A[i] != A[j] & is_in(A[j]-A[i],S)){
10
        # add to edge list
11
        e[index] = as.character(A[i])
12
        e[index+1] = as.character(A[j])
13
        index = index + 2
14
      }
15
    }
16
  }
17
  # generate graph
18
  g = make_graph(e,directed = TRUE)
19
  plot(g)
20
}

1
q3(c(0,1,2,3,4), c(-2,1,2,4))

Q4#

Given vertex set ‘v’,

Arc (i,j) exists if i!=j and j is a multiple of i

(so, j % i == 0)

1
q4 = function(v){
2
  index = 1
3
  e = c()
4
  # loop through each vertex
5
  for(i in 1:length(v)){
6
    # check all the other vertex
7
    for(j in 1:length(v)){
8
      # if not the same vertex, and conditions 1 or 2 are True
9
      if(v[i] != v[j] & v[j]%%v[i] == 0){
10
        # add to edge list
11
        e[index] = as.character(v[i])
12
        e[index+1] = as.character(v[j])
13
        index = index + 2
14
      }
15
    }
16
  }
17
  # generate graph
18
  g = make_graph(e,directed = TRUE)
19
  plot(g)
20
}

1
q4(c(-3,3,6,12))

← Back to Projects

Graph Basics#

Q2#

Q3#

Q4#

Graph Basics #