org.jgrapht.generate

Class ComplementGraphGenerator<V,E>

java.lang.Object

org.jgrapht.generate.ComplementGraphGenerator<V,E>

Type Parameters:

V - vertex type

E - edge type

All Implemented Interfaces:

GraphGenerator<V,E,V>

public class ComplementGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>

Generator which produces the complement graph of a given input graph. The complement $\overline{G}$ of a graph $G$ consists of the same vertices as $G$, but whose edge set consists of the edges not in $G$.

More formally, let $G = (V, E)$ be a graph and let $K$ consist of all 2-element subsets of $V$. Then $\overline{G} = (V, K \setminus E)$ is the complement of $G$, where $K \setminus E$ is the relative complement of $E$ in $K$. For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of $V$ in place of the set $K$ in the formula above.

The complement is not defined for multigraphs. If a multigraph is provided as input to this generator, it will be treated as if it is a simple graph.

Since:

Sept 2017

Author:

Joris Kinable

Constructor Summary

Constructors

Constructor and Description
ComplementGraphGenerator(Graph<V,E> graph) Complement Graph Generator
ComplementGraphGenerator(Graph<V,E> graph, boolean generateSelfLoops) Complement Graph Generator.

Method Summary

Modifier and Type	Method and Description
void	generateGraph(Graph<V,E> target, Map<String,V> resultMap) Generate a graph structure.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.generate.GraphGenerator

generateGraph, generateGraph, generateGraph

Constructor Detail

ComplementGraphGenerator

public ComplementGraphGenerator(Graph<V,E> graph)

Complement Graph Generator

Parameters:

graph - input graph

ComplementGraphGenerator

public ComplementGraphGenerator(Graph<V,E> graph,
                                boolean generateSelfLoops)

Complement Graph Generator. If the target graph allows self-loops the complement of $G$ may be defined by adding a self-loop to every vertex that does not have one in $G$. This behavior can be controlled using the boolean generateSelfLoops.

Parameters:

graph - input graph

generateSelfLoops - indicator whether self loops should be generated. If false, no self-loops are generated, independent of whether the target graph supports self-loops.

Method Detail

generateGraph

public void generateGraph(Graph<V,E> target,
                          Map<String,V> resultMap)

Description copied from interface: GraphGenerator

Generate a graph structure. The topology of the generated graph is dependent on the implementation. For graphs in which not all vertices share the same automorphism equivalence class, the generator may produce a labeling indicating the roles played by generated elements. This is the purpose of the resultMap parameter. For example, a generator for a wheel graph would designate a hub vertex. Role names used as keys in resultMap should be declared as public static final Strings by implementation classes.

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

resultMap - if non-null, receives implementation-specific mappings from String roles to graph elements (or collections of graph elements)