rustworkx.graph_line_graph

graph_line_graph(graph, /)

Constructs the line graph of a PyGraph object.

The line graph L(G) of a graph G represents the adjacencies between edges of G. L(G) contains a vertex for every edge in G, and L(G) contains an edge between two vertices if the corresponding edges in G have a vertex in common.

Parameters:

PyGraph – The input PyGraph object

Returns:

A new PyGraph object that is the line graph of graph, and the dictionary where the keys are indices of edges in``graph`` and the values are the corresponding indices of nodes in the linear graph.

Return type:

Tuple[PyGraph, dict]

import rustworkx as rx

graph = rx.PyGraph()
node_a = graph.add_node("a")
node_b = graph.add_node("b")
node_c = graph.add_node("c")
node_d = graph.add_node("d")
edge_ab = graph.add_edge(node_a, node_b, 1)
edge_ac = graph.add_edge(node_a, node_c, 1)
edge_bc = graph.add_edge(node_b, node_c, 1)
edge_ad = graph.add_edge(node_a, node_d, 1)

out_graph, out_edge_map = rx.graph_line_graph(graph)
assert out_graph.node_indices() == [0, 1, 2, 3]
assert out_graph.edge_list() == [(3, 1), (3, 0), (1, 0), (2, 0), (2, 1)]
assert out_edge_map == {edge_ab: 0, edge_ac: 1, edge_bc: 2, edge_ad: 3}