line_graph

Contents

line_graph#

graph_tool.generation.line_graph(g)[source]#

Return the line graph of the given graph g.

Notes

Given an undirected graph \(G\), its line graph \(L(G)\) is a graph such that:

  1. Each vertex of \(L(G)\) represents an edge of \(G\); and

  2. Two vertices of \(L(G)\) are adjacent if and only if their corresponding edges share a common endpoint (“are adjacent”) in \(G\).

For a directed graph, the second criterion becomes:

  1. Two vertices representing directed edges from \(u\) to \(v\) and from \(w\) to \(x\) in \(G\) are connected by an edge from \(uv\) to \(wx\) in the line digraph when \(v = w\).

References

Examples

>>> g = gt.collection.data["lesmis"]
>>> lg, vmap = gt.line_graph(g)
>>> pos = gt.graph_draw(lg, output="lesmis-lg.pdf")
../_images/lesmis-lg.png

Line graph of the coappearance of characters in Victor Hugo’s novel “Les Misérables”.#

Contents