Induced Subgraphs and Cliques

Provides functions dealing with induced subgraphs and finding cliques. More...

Classes
class	ogdf::CliqueFinderHeuristic
	Finds cliques and dense subgraphs using a heuristic. More...
class	ogdf::CliqueFinderModule
	Finds cliques. More...
class	ogdf::CliqueFinderSPQR
	Finds cliques using SPQR trees. More...

Methods for induced subgraphs
template<class LISTITERATOR >
void	ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, Graph &subGraph)
	Computes the subgraph induced by a list of nodes. More...
template<class LISTITERATOR >
void	ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, Graph &subGraph, NodeArray< node > &nodeTableOrig2New)
	Computes the subgraph induced by a list of nodes (plus a mapping from original nodes to new copies). More...
template<class LISTITERATOR >
void	ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, Graph &subGraph, NodeArray< node > &nodeTableOrig2New, EdgeArray< edge > &edgeTableOrig2New)
	Computes the subgraph induced by a list of nodes (plus mappings from original nodes and edges to new copies). More...
template<class LISTITERATOR >
void	ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, GraphCopySimple &subGraph)
	Computes the subgraph induced by a list of nodes. More...
template<class NODELISTITERATOR , class EDGELIST >
void	ogdf::inducedSubgraph (Graph &G, NODELISTITERATOR &it, EDGELIST &E)
	Computes the edges in a node-induced subgraph. More...

Detailed Description

Provides functions dealing with induced subgraphs and finding cliques.

Function Documentation

inducedSubGraph() [1/4]

template<class LISTITERATOR >

void ogdf::inducedSubGraph	(	const Graph &	G,
		LISTITERATOR	start,
		Graph &	subGraph
	)

Computes the subgraph induced by a list of nodes.

Template Parameters

LISTITERATOR

is the type of iterators for the input list of nodes.

Parameters

G	is the input graph.
start	is a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraph	is assigned the computed subgraph.

Definition at line 56 of file extended_graph_alg.h.

inducedSubGraph() [2/4]

template<class LISTITERATOR >

void ogdf::inducedSubGraph	(	const Graph &	G,
		LISTITERATOR	start,
		Graph &	subGraph,
		NodeArray< node > &	nodeTableOrig2New
	)

Computes the subgraph induced by a list of nodes (plus a mapping from original nodes to new copies).

Template Parameters

LISTITERATOR

is the type of iterators for the input list of nodes.

Parameters

G	is the input graph.
start	is a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraph	is assigned the computed subgraph.
nodeTableOrig2New	is assigned a mapping from the nodes in G to the nodes in subGraph.

Definition at line 74 of file extended_graph_alg.h.

inducedSubGraph() [3/4]

template<class LISTITERATOR >

void ogdf::inducedSubGraph	(	const Graph &	G,
		LISTITERATOR	start,
		Graph &	subGraph,
		NodeArray< node > &	nodeTableOrig2New,
		EdgeArray< edge > &	edgeTableOrig2New
	)

Computes the subgraph induced by a list of nodes (plus mappings from original nodes and edges to new copies).

Template Parameters

LISTITERATOR

is the type of iterators for the input list of nodes.

Parameters

G	is the input graph.
start	is a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraph	is assigned the computed subgraph.
nodeTableOrig2New	is assigned a mapping from the nodes in G to the nodes in subGraph.
edgeTableOrig2New	is assigned a mapping from the edges in G to the egdes in subGraph.

Definition at line 119 of file extended_graph_alg.h.

inducedSubGraph() [4/4]

template<class LISTITERATOR >

void ogdf::inducedSubGraph	(	const Graph &	G,
		LISTITERATOR	start,
		GraphCopySimple &	subGraph
	)

Computes the subgraph induced by a list of nodes.

Template Parameters

LISTITERATOR

is the type of iterators for the input list of nodes.

Parameters

G	is the input graph.
start	is a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraph	is assigned the computed subgraph, which will be set as a copy of G.

Definition at line 168 of file extended_graph_alg.h.

inducedSubgraph()

template<class NODELISTITERATOR , class EDGELIST >

void ogdf::inducedSubgraph	(	Graph &	G,
		NODELISTITERATOR &	it,
		EDGELIST &	E
	)

Computes the edges in a node-induced subgraph.

Template Parameters

NODELISTITERATOR	is the type of iterators for the input list of nodes.
EDGELIST	is the type of the returned edge list.

Parameters

G	is the input graph.
it	is a list iterator pointing to the first element in a list of nodes, whose induced subgraph is considered.
E	is assigned the list of edges in the node-induced subgraph.

Definition at line 210 of file extended_graph_alg.h.