Provides functions dealing with connectivity in graphs and clustered. More...

Classes
class	ogdf::ConnectivityTester
	Naive implementation for testing the connectivity of a graph. More...

class	ogdf::MaxAdjOrdering
	Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph. More...

class	ogdf::Triconnectivity
	realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph More...

Methods for clustered graphs
bool	ogdf::isCConnected (const ClusterGraph &C)
	Returns true iff cluster graph `C` is c-connected.

void	ogdf::makeCConnected (ClusterGraph &C, Graph &G, List< edge > &addedEdges, bool simple=true)
	Makes a cluster graph c-connected by adding edges.

Methods for connectivity
bool	ogdf::isConnected (const Graph &G)
	Returns true iff `G` is connected.

void	ogdf::makeConnected (Graph &G, List< edge > &added)
	Makes `G` connected by adding a minimum number of edges.

void	ogdf::makeConnected (Graph &G)
	makes `G` connected by adding a minimum number of edges.

int	ogdf::connectedComponents (const Graph &G, NodeArray< int > &component, List< node > isolated=nullptr, ArrayBuffer< node > reprs=nullptr)
	Computes the connected components of `G` and optionally generates a list of isolated nodes.

int	ogdf::connectedComponents (const Graph &G)
	Computes the amount of connected components of `G`.

bool	ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, bool onlyOne=false)
	Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices.

bool	ogdf::isBiconnected (const Graph &G, node &cutVertex)
	Returns true iff `G` is biconnected.

bool	ogdf::isBiconnected (const Graph &G)
	Returns true iff `G` is biconnected.

void	ogdf::makeBiconnected (Graph &G, List< edge > &added)
	Makes `G` biconnected by adding edges.

void	ogdf::makeBiconnected (Graph &G)
	Makes `G` biconnected by adding edges.

int	ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
	Computes the biconnected components of `G`.

int	ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component)
	Computes the biconnected components of `G`.

bool	ogdf::isTwoEdgeConnected (const Graph &graph)
	Returns true iff `graph` is 2-edge-connected.

bool	ogdf::isTriconnected (const Graph &G, node &s1, node &s2)
	Returns true iff `G` is triconnected.

bool	ogdf::isTriconnected (const Graph &G)
	Returns true iff `G` is triconnected.

bool	ogdf::isTriconnectedPrimitive (const Graph &G, node &s1, node &s2)
	Returns true iff `G` is triconnected (using a quadratic time algorithm!).

bool	ogdf::isTriconnectedPrimitive (const Graph &G)
	Returns true iff `G` is triconnected (using a quadratic time algorithm!).

void	ogdf::triangulate (Graph &G)
	Triangulates a planarly embedded graph `G` by adding edges.

int	ogdf::connectedIsolatedComponents (const Graph &G, List< node > &isolated, NodeArray< int > &component)

bool	ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, ArrayBuffer< Tuple2< node, node > > &addEdges, bool onlyOne=false)
	Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices.

bool	ogdf::isTwoEdgeConnected (const Graph &graph, edge &bridge)
	Returns true iff `graph` is 2-edge-connected.

Methods for directed graphs
int	ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
	Computes the strongly connected components of the digraph `G`.

Detailed Description

Provides functions dealing with connectivity in graphs and clustered.

Function Documentation

◆ biconnectedComponents() [1/2]

int ogdf::biconnectedComponents	(	const Graph &	G,
		EdgeArray< int > &	component
	)

inline

Computes the biconnected components of G.

Assigns component numbers (0, 1, ...) to the edges of G. The component number of each edge is stored in the edge array component. Each self-loop is counted as one biconnected component and has its own component number.

Parameters

G	is the input graph.
component	is assigned a mapping from edges to component numbers.

Returns: the number of biconnected components (including self-loops) + the number of nodes without neighbours (that is, the number of nodes who have no incident edges or whose incident edges are all self-loops).

Definition at line 603 of file simple_graph_alg.h.

◆ biconnectedComponents() [2/2]

int ogdf::biconnectedComponents	(	const Graph &	G,
		EdgeArray< int > &	component,
		int &	nonEmptyComponents
	)

Computes the biconnected components of G.

Assigns component numbers (0, 1, ...) to the edges of G. The component number of each edge is stored in the edge array component. Each self-loop is counted as one biconnected component and has its own component number.

Parameters

G	is the input graph.
component	is assigned a mapping from edges to component numbers.

Returns: the number of biconnected components (including self-loops) + the number of nodes without neighbours (that is, the number of nodes who have no incident edges or whose incident edges are all self-loops).

Parameters

nonEmptyComponents is the number of non-empty components. The indices of component range from 0 to nonEmptyComponents - 1.

◆ connectedComponents() [1/2]

int ogdf::connectedComponents ( const Graph & G )

inline

Computes the amount of connected components of G.

Parameters

G	is the input graph.

Returns: the amount of connected components.

Definition at line 497 of file simple_graph_alg.h.

◆ connectedComponents() [2/2]

int ogdf::connectedComponents	(	const Graph &	G,
		NodeArray< int > &	component,
		List< node > *	isolated = `nullptr`,
		ArrayBuffer< node > *	reprs = `nullptr`
	)

Computes the connected components of G and optionally generates a list of isolated nodes.

Assigns component numbers (0, 1, ...) to the nodes of G. The component number of each node is stored in the node array component.

Parameters

G	is the input graph.
component	is assigned a mapping from nodes to component numbers.
isolated	if non-null, will contain the list of isolated nodes afterwards. An isolated node is a node without incident edges.
reprs	if non-null, will contain a node from component c at index c afterwards.

Returns: the number of connected components.

◆ connectedIsolatedComponents()

int ogdf::connectedIsolatedComponents	(	const Graph &	G,
		List< node > &	isolated,
		NodeArray< int > &	component
	)

inline

Deprecated:: "connectedComponents() should be used instead."

See also: ogdf::connectedComponents(const Graph&, NodeArray<int>&, List<node>*, ArrayBuffer<node>*)

Definition at line 508 of file simple_graph_alg.h.

◆ findCutVertices() [1/2]

bool ogdf::findCutVertices	(	const Graph &	G,
		ArrayBuffer< node > &	cutVertices,
		ArrayBuffer< Tuple2< node, node > > &	addEdges,
		bool	onlyOne = `false`
	)

Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices.

Precondition: G must be connected.

Parameters

G	is the graph whose cut vertices should be found.
cutVertices	is assigned the cut vertices of the graph.
onlyOne	should be set to true if the search should stop after finding one cut vertex, to false if all cut vertices should be found.

Returns: true if the graph contains at least one cut vertex, false otherwise.

Parameters

addEdges is assigned the tuples of nodes which have to be connected in order to turn each cut vertex into a non-cut vertex.

◆ findCutVertices() [2/2]

bool ogdf::findCutVertices	(	const Graph &	G,
		ArrayBuffer< node > &	cutVertices,
		bool	onlyOne = `false`
	)

inline

Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut vertices.

Precondition: G must be connected.

Parameters

G	is the graph whose cut vertices should be found.
cutVertices	is assigned the cut vertices of the graph.
onlyOne	should be set to true if the search should stop after finding one cut vertex, to false if all cut vertices should be found.

Returns: true if the graph contains at least one cut vertex, false otherwise.

Definition at line 534 of file simple_graph_alg.h.

◆ isBiconnected() [1/2]

bool ogdf::isBiconnected ( const Graph & G )

inline

Returns true iff G is biconnected.

Parameters

G	is the input graph.

Definition at line 555 of file simple_graph_alg.h.

◆ isBiconnected() [2/2]

bool ogdf::isBiconnected	(	const Graph &	G,
		node &	cutVertex
	)

Returns true iff G is biconnected.

Parameters

G	is the input graph.
cutVertex	If false is returned and `G` is connected, `cutVertex` is assigned a cut vertex in `G`, else it is assigned nullptr.

◆ isCConnected()

bool ogdf::isCConnected ( const ClusterGraph & C )

Returns true iff cluster graph C is c-connected.

◆ isConnected()

bool ogdf::isConnected ( const Graph & G )

Returns true iff G is connected.

Parameters

G	is the input graph.

Returns: true if G is connected, false otherwise.

◆ isTriconnected() [1/2]

bool ogdf::isTriconnected ( const Graph & G )

inline

Returns true iff G is triconnected.

Parameters

G	is the input graph.

Returns: true if G is triconnected, false otherwise.

Definition at line 656 of file simple_graph_alg.h.

◆ isTriconnected() [2/2]

bool ogdf::isTriconnected	(	const Graph &	G,
		node &	s1,
		node &	s2
	)

Returns true iff G is triconnected.

If G is not triconnected then

s1 and s2 are both nullptr if G is not connected.
s1 is a cut vertex and s2 is nullptr if G is connected but not biconnected.
s1 and s2 are a separation pair if G is bi- but not triconnected.

Parameters

G	is the input graph.
s1	is assigned a cut vertex or one node of a separation pair, if `G` is not triconnected (see above).
s2	is assigned one node of a separation pair, if `G` is not triconnected (see above).

Returns: true if G is triconnected, false otherwise.

◆ isTriconnectedPrimitive() [1/2]

bool ogdf::isTriconnectedPrimitive ( const Graph & G )

inline

Returns true iff G is triconnected (using a quadratic time algorithm!).

Warning: This method has quadratic running time. An efficient linear time version is provided by isTriconnected().

Parameters

G	is the input graph.

Returns: true if G is triconnected, false otherwise.

Definition at line 690 of file simple_graph_alg.h.

◆ isTriconnectedPrimitive() [2/2]

bool ogdf::isTriconnectedPrimitive	(	const Graph &	G,
		node &	s1,
		node &	s2
	)

Returns true iff G is triconnected (using a quadratic time algorithm!).

If G is not triconnected then

s1 and s2 are both nullptr if G is not connected.
s1 is a cut vertex and s2 is nullptr if G is connected but not biconnected.
s1 and s2 are a separation pair if G is bi- but not triconnected.

Warning: This method has quadratic running time. An efficient linear time version is provided by isTriconnected().

Parameters

G	is the input graph.
s1	is assigned a cut vertex of one node of a separation pair, if `G` is not triconnected (see above).
s2	is assigned one node of a separation pair, if `G` is not triconnected (see above).

Returns: true if G is triconnected, false otherwise.

◆ isTwoEdgeConnected() [1/2]

bool ogdf::isTwoEdgeConnected ( const Graph & graph )

inline

Returns true iff graph is 2-edge-connected.

Implementation of the algorithm to determine 2-edge-connectivity from the following publication:

Jens M. Schmidt: A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Information Processing Letters (2013)

It runs in O(|E|+|V|) as it relies on two DFS.

Parameters

graph is the input graph.

Definition at line 628 of file simple_graph_alg.h.

◆ isTwoEdgeConnected() [2/2]

bool ogdf::isTwoEdgeConnected	(	const Graph &	graph,
		edge &	bridge
	)

Returns true iff graph is 2-edge-connected.

Implementation of the algorithm to determine 2-edge-connectivity from the following publication:

Jens M. Schmidt: A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Information Processing Letters (2013)

It runs in O(|E|+|V|) as it relies on two DFS.

Parameters

graph	is the input graph.
bridge	If false is returned and `graph` is connected, `bridge` is assigned a bridge in `graph`, else it is assigned `nullptr`

◆ makeBiconnected() [1/2]

void ogdf::makeBiconnected ( Graph & G )

inline

Makes G biconnected by adding edges.

Parameters

G	is the input graph.

Definition at line 575 of file simple_graph_alg.h.

◆ makeBiconnected() [2/2]

void ogdf::makeBiconnected	(	Graph &	G,
		List< edge > &	added
	)

Makes G biconnected by adding edges.

Parameters

G	is the input graph.
added	is assigned the list of inserted edges.

◆ makeCConnected()

void ogdf::makeCConnected	(	ClusterGraph &	C,
		Graph &	G,
		List< edge > &	addedEdges,
		bool	simple = `true`
	)

Makes a cluster graph c-connected by adding edges.

Parameters

C	is the input cluster graph.
G	is the graph associated with the cluster graph `C`; the function adds new edges to this graph.
addedEdges	is assigned the list of newly created edges.
simple	selects the method used: If set to true, a simple variant that does not guarantee to preserve planarity is used.

◆ makeConnected() [1/2]

void ogdf::makeConnected ( Graph & G )

inline

makes G connected by adding a minimum number of edges.

Parameters

G	is the input graph.

Definition at line 467 of file simple_graph_alg.h.

◆ makeConnected() [2/2]

void ogdf::makeConnected	(	Graph &	G,
		List< edge > &	added
	)

Makes G connected by adding a minimum number of edges.

Parameters

G	is the input graph.
added	is assigned the added edges.

◆ strongComponents()

int ogdf::strongComponents	(	const Graph &	G,
		NodeArray< int > &	component
	)

Computes the strongly connected components of the digraph G.

The function implements the algorithm by Tarjan.

Parameters

G	is the input graph.
component	is assigned a mapping from nodes to component numbers (0, 1, ...).

Returns: the number of strongly connected components.

◆ triangulate()

void ogdf::triangulate ( Graph & G )

Triangulates a planarly embedded graph G by adding edges.

The result of this function is that G is made maximally planar by adding new edges. G will also be planarly embedded such that each face is a triangle.

Precondition: G is planar, simple and represents a combinatorial embedding (i.e. G is planarly embedded).

Parameters

G	is the input graph to which edges will be added.

OpenGraph DrawingFramework

Classes

Methods for clustered graphs

Methods for connectivity

Methods for directed graphs

Detailed Description

Function Documentation

◆ biconnectedComponents() [1/2]

◆ biconnectedComponents() [2/2]

◆ connectedComponents() [1/2]

◆ connectedComponents() [2/2]

◆ connectedIsolatedComponents()

◆ findCutVertices() [1/2]

◆ findCutVertices() [2/2]

◆ isBiconnected() [1/2]

◆ isBiconnected() [2/2]

◆ isCConnected()

◆ isConnected()

◆ isTriconnected() [1/2]

◆ isTriconnected() [2/2]

◆ isTriconnectedPrimitive() [1/2]

◆ isTriconnectedPrimitive() [2/2]

◆ isTwoEdgeConnected() [1/2]

◆ isTwoEdgeConnected() [2/2]

◆ makeBiconnected() [1/2]

◆ makeBiconnected() [2/2]

◆ makeCConnected()

◆ makeConnected() [1/2]

◆ makeConnected() [2/2]

◆ strongComponents()

◆ triangulate()

Open
Graph Drawing
Framework