How to define the mapping for a vetrex contraction?

Question

I have a graph $G=(V, E)$. I need to make a vetrex contraction by the rules:

Find all articulation vertices with degree is greater than 2 and contract all vertices into them that can only be reached through this vertex. The original graph in left, the expected graph in right. It is should be noted: instead of leaves "14", "8" and "3" can be subgraphs with more that one vertex.

First, I have found the bridge edges (red color) and two types of the articulation vertices: a) on a chain (red color), b) not on a chain (green color). The criteria for articulation classifucation is a vertex degree (2 or not 2).

My attemp is:

library(igraph)
set.seed(44)
n = 20
m = 35
G <-  sample_gnm(n=n, m=m)
V(G)$group <- 1:n

V(G)$color <- "black"
E(G)$color <- "black"
ind <- articulation.points(G)

V(G)$color[ind] <- ifelse(degree(G, V(G)[ind])==2, "red", "green")
if(degree(G, V(G)[ind])==2) V(G)[ind]$group =  0   

num_comp <- length(decompose.graph(G))

for (i in 1:m) {
G_sub <- delete.edges(G, i)
if (length(decompose.graph(G_sub)) > num_comp) E(G)$color[i] <- "red"
}
plot(G, layout = layout.fruchterman.reingold, 
         vertex.size = 15, vertex.color= V(G)$color,
         vertex.label.color = "white" )  


g2 <- contract(G, mapping = factor(V(G)$group),
                        vertex.attr.comb=toString)

plot(g2, layout = layout.fruchterman.reingold, 
         vertex.size = 15, vertex.color= V(G)$color,
         vertex.label.color = "white" ) 

Question. How to define the mapping?

Edit. After the ThomasIsCoding's answer I'd add the figure for the remark: It is should be noted: instead of leaves "14", "8" and "3" can be subgraphs with more that one vertex. For instance, I can have the case:

set.seed(44)
n <- 20
m <- 35
G <- sample_gnm(n = n, m = m) %>%
     add_vertices(1) %>%
     add_vertices(1) %>%
     add_edges(c(3,21, 3,22, 21,22))
plot(G)

In the figure below one can see the five bridges. The degree of vertices 8 and 14 equal to one, but vertex 3 in not a leaf now.

My problem is: how to distinguish the chain and no chain.

for (k in ind) { 
    nbs <- neighbors(G, k)
    if (degree(G, k) == 2) # chain 
        V(G)$group <- replace(V(G)$group, 
                      match(nbs[degree(G, nbs) == 1], V(G)), match(k, V(G)))
    else                   # no chain   
    V(G)$group <- ...
}

Also weak place is: To which subgraph (A or B) should the vertex contraction operation be applied? In the original case the one vetrex were contracted only. The original task come from the simplification big graph for future analysis. And I think I can make the simplification based on bridges and cut-vertices. But now I am thinking on the selection subgraph for the vetrex contraction. The ccurrent point of view: apply the the vertex contraction for the subgraph with the minimal geodesic spanning tree.

Answer 1

You can try the code below to produce the mapping argument (see the for loop part)

library(igraph)
set.seed(44)
n <- 20
m <- 35
G <- sample_gnm(n = n, m = m)
V(G)$group <- 1:n
ind <- articulation.points(G)
for (k in ind) {
    nbs <- neighbors(G, k)
    V(G)$group <- replace(V(G)$group, match(nbs[degree(G, nbs) == 1], V(G)), match(k, V(G)))
}
g2 <- contract(G, mapping = factor(V(G)$group))