If debugging is the process of removing bugs, then programming must be the process of putting them in.

—Edsger W. Dijkstra (cannot find the citation, this may be fabricated)

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. The more common algorithm fixes a single node as the initial node and finds shortest paths from the initial node to all other nodes in the graph, producing a shortest-path tree.

The steps for implementing Dijkstra’s algorithm are as follows:

• find the initial distance vector \(D\) of each nodes (the distance from initial node to other nodes)
• find the minimum distance between the initial node and one other node, set the distance to vector \(D\)
• update the initial node index, from the new initial node find the minimum distance again.

Here is the MATLAB code for calculate the distance from a graph, the output vector is the shortest paths from initial node to other nodes.

function dijkstra(V,o)
%V is adjacency matrix, o is the initial node index
A=V;
[m,n]=size(A);
d=zeros(1,m);% vector to store the distance of initial node and other nodes
d(:)=inf;
Q=A(o,:);%find the distance between two nodes (the initial node and others)
d(o)=0;% set the distance of start point to initial node is zero
p=10;%loop flag
while(min(Q)~=inf&p~=0)% stop loop when all distance is Inf or loop flag is zero
    [a id]=min(Q);% find the minimum distance and the index of the node
    Q(id)=inf;%set the minimum index to Inf 
    A(o,id)=inf;%set the minimum distance to Ind
    o=id;%update the initial node
    if d(id)>a
        d(id)=a;
    end
    for j=1:m%change the distance of each node
        if (Q(j)>d(id)+A(id,j))
            Q(j)=d(id)+A(id,j);
        end
    end
    p=0;%loop flat == 0
    for i=1:m%check inf value, set the loop flag > 0 (looping)
        if d(i)==inf
            p=p+1;
        end
    end
end
d
end

The distance from initial node 1 to node 2 is Inf, from node 2 to node 3 is 10, from node 3 to node 4 is 50, from node 4 to node 5 is 20, from node 5 to node 6 is 60.

V=[0 inf 10 inf 30 100;
inf 0 5 inf inf inf;
inf inf 0 50 inf inf;
inf inf inf 0 inf 10;
inf inf inf 20 0 60;
inf inf inf inf inf 0];


octave:3> dijkstra(V,1)
warning: Matlab-style short-circuit operation performed for operator &
warning: called from
    dijkstra at line 25 column 9
d =

     0   Inf    10    50    30    60

I will post some undergraduate school coding scripts at my English blog. Recently I found a directory in my laptop which stored a lot of programming scripts for my undergraduate and postgraduate study, including computing methods, computer graphics, bio0ormatics pipelines, etc. I would like to read those codes and learn from them for a new purpose, it may provide my new view to understanding my research problems.

Kruskal’s algorithm is a minimum-spanning-tree algorithm to find the minimum distance(edge) that could connect with all vertices.

The steps for implementing Kruskal’s algorithm are as follows¹:

• Sort all the edges from low weight to high
• Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
• Keep adding edges until we reach all vertices.

Only the undirected graph is considered in this algorithm. First of all, let’s show you what is an undirected graph and what is Adjacency Matrix.

An undirected graph is a graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are bidirectional².

An undirected graph is plotted by using igraph package in R. The input matrix is a adjacency matrix.

library(igraph)
adjm <- matrix(c(0,10,0,0,0,11,0,0,0,
                 10,0,18,0,0,0,12,12,0,
                 0,18,0,22,0,0,0,8,0,
                 0,0,22,0,20,0,24,21,16,
                 0,0,0,20,0,26,0,0,7,
                 11,0,0,0,26,0,17,0,0,
                 0,12,0,24,0,17,0,0,19,
                 0,12,8,21,0,0,0,0,0,
                 0,0,0,16,7,0,19,0,0),nrow = 9)
g2 <- graph_from_adjacency_matrix(adjm, weighted=TRUE, mode="undirected")

plot(g2, edge.label = E(g2)$weight) #edge.width=E(g2)$weight #edge.width=edge.betweenness(g2)

For a simple graph with vertex set \(V\), the adjacency matrix is a square \(\vert V \vert \times \vert V \vert\) matrix \(A\) such that its element \(A_{ij}\) is one when there is an edge from vertex \(i\) to vertex \(j\), and zero when there is no edge.

Sometimes we could also define zero is the edge weight of vertex \(i\) to vertex \(i\), INF is the edge weight of two different vertices when there is no edge.

Please note that the adjacency matrix of undirected graph is always symmetric.

At here I use MATLAB(Octave) to reproducing this algorithm, you will find matrix is the best thing in the world, many useful functions integrated into the MATLAB, they make things easier.

V=[0    10    inf    inf    inf    11    inf    inf    inf;
10    0    18    inf    inf    inf    12    12    inf;
inf    18    0    22    inf    inf    inf    8    inf;
inf    inf    22    0    20    inf    24    21    16;
inf    inf    inf    20    0    26    inf    inf    7;
11    inf    inf    inf    26    0    17    inf    inf;
inf    12    inf    24    inf    17    0    inf    19;
inf    12    8    21    inf    inf    inf    0    inf;
inf    inf    inf    16    7    inf    19    inf    0];

function F=kruskal(V)
A=V;
[m,n]=size(A);
k=[1:m]; % k is a vector to store the Connected Components
F=zeros(m-1,3);
i=0;
while i~=m-1
    [a b]=min(A);%find the minimum edge start from each row (point), and the end point index
    [c d]=min(a);%find the minimum edge among all points and the start point index
    if k(d)~=k(b(d))% check if the two vertices (points) are belongs to the same connected component, to avoid ring
        i=i+1;
        F(i,:)=[d b(d) A(d,b(d))];% assign the minimum edge to result
        t=k(b(d));% store the connected component
        k(b(d))=k(d); %make the two points in the same connected component
        for j=1:m % serch other points that should be updated in the new connected component
            if k(j)==t
                k(j)=k(d);
            end
        end
    end
    A(d,b(d))=inf;A(b(d),d)=inf; % set the value to INF
end
end

The result of this function will return a matrix of \(N \times 3\).

Each row is a edge between element 1 and element 2, the third column shows the edge weight.

octave:5> kruskal(V)
ans =

    5    9    7
    3    8    8
    1    2   10
    1    6   11
    2    7   12
    2    8   12
    4    9   16
    7    9   19

library(igraph)
adjm <- matrix(c(0,10,0,0,0,11,0,0,0,
                 10,0,18,0,0,0,12,12,0,
                 0,18,0,22,0,0,0,8,0,
                 0,0,22,0,20,0,24,21,16,
                 0,0,0,20,0,26,0,0,7,
                 11,0,0,0,26,0,17,0,0,
                 0,12,0,24,0,17,0,0,19,
                 0,12,8,21,0,0,0,0,0,
                 0,0,0,16,7,0,19,0,0),nrow = 9)

edgecolor=rep("gray",nrow(as.data.frame(get.edgelist(g2))))
edgecolor[c(13,7,1,2,4,5,11,15)]="red"
g2 <- graph_from_adjacency_matrix(adjm, weighted=TRUE, mode="undirected")
plot(g2, edge.label = E(g2)$weight,edge.color=edgecolor)

I try to avoid to explain connected component in this article, but you could see it in my code, if you are interested in learning more about graph and tree, please google the term.

There are usually five purposes for rename a file (multiple files):

1. Replace (delete/remove) the spaces in a filename
2. Rename the suffix of a file
3. Add date in a filename
4. Uppercase/lowercase first letter(all letters) in a filename
5. Replace a specific part of a filename

Here, I will show you some script to do all jobs.

1. Replace (delete/remove) the spaces in a filename

## generate some files with spaces in the filenames
touch "A filename with space.txt"
touch "B filename with space.txt"

## Replace the space with underline
for filename in *\ *; 
do
  mv "$filename" "${filename// /_}"
done

## Delete the space in a filename
for filename in *\ *; 
do
  mv "$filename" "${filename// /}"
done

2. Rename the suffix of a file

## generate some files
touch "A.txt"
touch "B.txt"

for filename in *.txt;
do
  mv "$filename" "${filename//.txt/.TXT}"
done

3. Add date in a filename

## generate some files
touch "A.txt"
touch "B.txt"

DATE=`date +%F` 
for filename in *.txt;
do 
  mv "$filename" "$DATE-$filename"
done

4. Uppercase/lowercase first letter(all letters) in a filename

## generate some files
touch "aaaapple.txt"
touch "bbbbanana.txt"

## Uppercase first letter
for filename in *.txt;
do 
  fn="${filename%.*}"
  mv "$filename"  ${fn^}.${filename#*.}
done

## Lowercase first letter
for filename in *.txt;
do 
  fn="${filename%.*}"
  mv "$filename"  ${fn,}.${filename#*.}
done

## From lowercase to uppercase
for filename in *.txt;
do 
  fn="${filename%.*}"
  mv "$filename" ${fn^^}.${filename#*.}
done

## From uppercase to lowercase
for filename in *.txt;
do 
  fn="${filename%.*}"
  mv "$filename"  ${fn,,}.${filename#*.}
done

## Highlight character p in the filename
for filename in *.txt;
do 
  fn="${filename%.*}"
  mv "$filename"  ${fn^^p}.${filename#*.}
done

5. Replace a specific part of a filename

## generate some files
touch "abc.txt"
touch "bcd.txt"

for filename in *.txt;
do 
  fn="${filename%.*}"
  mv "$filename"  ${fn/bc/ZZZ}.${filename#*.}
done

Q.E.D.

The first day of 2019 (Yes, we go to hospital at 1st Jan 2019) starts with sent my family member to the hospital to do the biopsy, the last day of 2019 starts with told my family member to do the routing injection of Goserelin. I withdrew my Ph.D. applications in January and found a job near the hospital to take care of my family in my way. The main duty of my job is performing In silico proficiency testing program in China mainland.

it’s been a difficult year for me and my family, I didn’t write a lot this year. Maybe, I would make some treatment data public to seek suggestions from the internet later.

I wish we still have a lot of time to share together.

I’ve been reading books of old

The legends and the myths

Achilles and his gold

Hercules and his gifts

Spiderman’s control

And Batman with his fists

And clearly I don’t see myself upon that list

But he said, where’d you wanna go?

How much you wanna risk?

I’m not looking for somebody

With some superhuman gifts

Some superhero

Some fairytale bliss

Just something I can turn to

Somebody I can hug

I want something just like this

I want to you be healthy, stay with me for another 10 years, 20 years, 30 years, 40 years…

I’ve been reading books of old

The legends and the myths

The testaments they told

The moon and its eclipse

And Superman unrolls

A suit before he lifts

But I’m not the kind of person that it fits

She said, where’d you wanna go?

How much you wanna risk?

I’m not looking for somebody

With some superhuman gifts

Some superhero

Some fairytale bliss

Just something I can turn to

Somebody I can hug

I want something just like this

I want to you be healthy, stay with me for another 10 years, 20 years, 30 years, 40 years…