org.jgrapht.alg.transform

Class LineGraphConverter<V,E,EE>

java.lang.Object

org.jgrapht.alg.transform.LineGraphConverter<V,E,EE>

Type Parameters:

V - vertex type of input graph

E - edge type of input graph

EE - edge type of target graph

public class LineGraphConverter<V,E,EE>
extends Object

Converter which produces the line graph of a given input graph. The line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$. The line graph of a directed graph $G$ is the directed graph $L(G)$ whose vertex set corresponds to the arc set of $G$ and having an arc directed from an edge $e_1$ to an edge $e_2$ if in $G$, the head of $e_1$ meets the tail of $e_2$

More formally, let $G = (V, E)$ be a graph then its line graph $L(G)$ is such that

• Each vertex of $L(G)$ represents an edge of $G$
• If $G$ is undirected: two vertices of $L(G)$ are adjacent if and only if their corresponding edges share a common endpoint ("are incident") in $G$
• If $G$ is directed: two vertices of $L(G)$ corresponding to respectively arcs $(u,v)$ and $(r,s)$ in $G$ are adjacent if and only if $v=r$.

Author:

Joris Kinable, Nikhil Sharma

Constructor Summary

Constructors

Constructor and Description
LineGraphConverter(Graph<V,E> graph) Line Graph Converter

Method Summary

Modifier and Type	Method and Description
void	convertToLineGraph(Graph<E,EE> target) Constructs a line graph $L(G)$ of the input graph $G(V,E)$.
void	convertToLineGraph(Graph<E,EE> target, BiFunction<E,E,Double> weightFunction) Constructs a line graph of the input graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LineGraphConverter

public LineGraphConverter(Graph<V,E> graph)

Line Graph Converter

Parameters:

graph - graph to be converted. This implementation supports multigraphs and pseudographs.

Method Detail

convertToLineGraph

public void convertToLineGraph(Graph<E,EE> target)

Constructs a line graph $L(G)$ of the input graph $G(V,E)$. If the input graph is directed, the result is a line digraph. The result is stored in the target graph.

Parameters:

target - target graph

convertToLineGraph

public void convertToLineGraph(Graph<E,EE> target,
                               BiFunction<E,E,Double> weightFunction)

Constructs a line graph of the input graph. If the input graph is directed, the result is a line digraph. The result is stored in the target graph. A weight function is provided to set edge weights of the line graph edges. Notice that the target graph must be a weighted graph for this to work. Recall that in a line graph $L(G)$ of a graph $G(V,E)$ there exists an edge $e$ between $e_1\in E$ and $e_2\in E$ if the head of $e_1$ is incident to the tail of $e_2$. To determine the weight of $e$ in $L(G)$, the weight function takes as input $e_1$ and $e_2$.

Note: a special case arises when graph $G$ contains self-loops. Self-loops (as well as multiple edges) simply add additional nodes to line graph $L(G)$. When $G$ is directed, a self-loop $e=(v,v)$ in $G$ results in a vertex $e$ in $L(G)$, and in addition a self-loop $(e,e)$ in $L(G)$, since, by definition, the head of $e$ in $G$ is incident to its own tail. When $G$ is undirected, a self-loop $e=(v,v)$ in $G$ results in a vertex $e$ in $L(G)$, but no self-loop $(e,e)$ is added to $L(G)$, since, by convention, the line graph of an undirected graph is commonly assumed to be a simple graph.

Parameters:

target - target graph

weightFunction - weight function