generate_fundamental_cycles {gor}

Generate fundamental cycles in a connected graph

Description

Generation of a system of fundamental cycles in a connected graph with respect of a given spanning tree.

Usage

generate_fundamental_cycles(eT, eG)

Arguments

eT

Spanning tree of the graph in edgelist representation, see as_edgelist.

eG

Graph in edgelist representation, see as_edgelist.

Details

The routine loops through the edges of the graph outside the spanning tree (there are |E| - |V| + 1 of them); in each step, it adds an edge to the tree, thus closing a cycle, which has some "hair" in it in the form of dangling vertices. Then all those dangling vertices are removed from the cycle (the "hair" is "shaven").

Value

A matrix with the fundamental cycles in its rows, in edge vector representation, that is, a binary vector with 1 if the edge belongs to the cycle and 0 otherwise. This interpretation of the edge vectors of each fundamental cycle refers to the edgelist of the graph given in eG.

Author(s)

Cesar Asensio

See Also

shave_cycle shaves hairy cycles, apply_incidence_map applies the incidence map of a graph to an edge vector.

Examples

g <- make_graph("Dodecahedron")
n <- gorder(g)
b <- bfs(g, 1, father = TRUE)                 # BFS tree
T <- make_graph(rbind(b$father[2:n], 2:n), n) # Tree as igraph graph
eT <- as_edgelist(T)
eG <- as_edgelist(g)
C <- generate_fundamental_cycles(eT, eG)      # Fundamental cycles
mu <- gsize(g) - gorder(g) + 1                # Cyclomatic number
z <- layout_with_gem(g)
for (i in 1:mu) {                             # Cycle drawing
    c1 <- make_graph(t(eG[which(C[i,] == 1),]) , dir = FALSE)
    plot(g, layout = z)
    plot(c1, layout = z, add = TRUE, edge.color = "cyan4",
         edge.lty = "dashed", edge.width = 3)
    title(paste0("Cycle ", i, " of ", mu))
    #Sys.sleep(1) # Adjust time to see the cycles
}