Module linegraph 

Line graph constructor (ALGO-CN-015).

Counterpart of igraph_linegraph() in references/igraph/src/constructors/linegraph.c:31-174.

The line graph L(G) of G has one vertex for every edge of G (edge id e ↔ L-vertex id e). Adjacency depends on the directedness of G:

• Undirected G: two distinct L-vertices e1, e2 are connected by an L-edge for every shared endpoint between the two G-edges. Multigraphs therefore yield multi-L-edges (one per shared endpoint). A G-self-loop counts its endpoint twice — so an L-vertex from a self-loop has a single L-self-loop on itself, plus two L-edges to every other G-edge sharing the same vertex (since the loop “uses two endpoints” at that vertex).
• Directed G: an L-arc goes from e ↦ e1 whenever the target of e equals the source of e1 — i.e. the two G-arcs can be chained.

The result is directed iff G is directed.

Edge emission order in both branches matches upstream byte-for-byte so the three-source conformance test can compare raw ordered edge lists rather than canonicalised multisets.

Time complexity: O(|V(G)| + |E(G)|) — exactly the same as upstream; the inner walks are bounded by Σ_v deg(v) = 2|E| so amortised cost per L-edge is constant.

Functions

linegraph

Build the line graph L(G) of graph.