Line graph of a graph

This function calculates the line graph of another graph.

Usage

make_line_graph(graph)

line_graph(graph)

Arguments

graph: The input graph, it can be directed or undirected.

Value

A new graph object.

Details

The line graph L(G) of a G undirected graph is defined as follows. L(G) has one vertex for each edge in G and two vertices in L(G) are connected by an edge if their corresponding edges share an end point.

The line graph L(G) of a G directed graph is slightly different, L(G) has one vertex for each edge in G and two vertices in L(G) are connected by a directed edge if the target of the first vertex's corresponding edge is the same as the source of the second vertex's corresponding edge.

linegraph()

Author

Gabor Csardi csardi.gabor@gmail.com, the first version of the C code was written by Vincent Matossian.

Examples


# generate the first De-Bruijn graphs
g <- make_full_graph(2, directed = TRUE, loops = TRUE)
make_line_graph(g)
#> ── <igraph> Line graph ────────────────────────────────────────────── a82b7c6 ──
#> ℹ directed
#> ℹ 4 vertices · 8 edges
#> 
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph:  name <chr>
#> 
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 1 → 1  3 → 1  1 → 2  3 → 2  2 → 3  4 → 3  2 → 4  4 → 4 
make_line_graph(make_line_graph(g))
#> ── <igraph> Line graph ────────────────────────────────────────────── 57735f8 ──
#> ℹ directed
#> ℹ 8 vertices · 16 edges
#> 
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph:  name <chr>
#> 
#> ── Edges ───────────────────────────────────────────────────────────────────────
#>  [1] 1 → 1  2 → 1  5 → 2  6 → 2  1 → 3  2 → 3  5 → 4  6 → 4  3 → 5  4 → 5 
#> [11] 7 → 6  8 → 6  3 → 7  4 → 7  7 → 8  8 → 8 
make_line_graph(make_line_graph(make_line_graph(g)))
#> ── <igraph> Line graph ────────────────────────────────────────────── d5743c9 ──
#> ℹ directed
#> ℹ 16 vertices · 32 edges
#> 
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph:  name <chr>
#> 
#> ── Edges ───────────────────────────────────────────────────────────────────────
#>  [1] 1 → 1    2 → 1    3 → 2    4 → 2    9 → 3    10 → 3   11 → 4   12 → 4  
#>  [9] 1 → 5    2 → 5    3 → 6    4 → 6    9 → 7    10 → 7   11 → 8   12 → 8  
#> [17] 5 → 9    6 → 9    7 → 10   8 → 10   13 → 11  14 → 11  15 → 12  16 → 12 
#> [25] 5 → 13   6 → 13   7 → 14   8 → 14   13 → 15  14 → 15  15 → 16  16 → 16