gor (version 2.0)

generate_fundamental_cycles: 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)

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.

Arguments

eT

Spanning tree of the graph in edgelist representation, see igraph::as_edgelist().

eG

Graph in edgelist representation, see igraph::as_edgelist().

Author

Cesar Asensio

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").

See Also

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

Examples

library(igraph)
g <- make_graph("Dodecahedron")
n <- gorder(g)
T <- bfs_tree(g, 1)                           # BFS tree
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),]), n = n, 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(2)   # Adjust time to see the cycles
}