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...

Functions
bool	ogdf::maximumDensitySubgraph (Graph &G, NodeSet &subgraphNodes, std::function< node(node)> resultNodeMap=[](node v) { return v;}, int64_t timelimit=-1)
	Calculates the maximum density subgraph of G.

Detailed Description

Provides functions dealing with induced subgraphs and finding cliques.

Function Documentation

maximumDensitySubgraph()

bool ogdf::maximumDensitySubgraph	(	Graph &	G,
		NodeSet &	subgraphNodes,
		std::function< node(node)>	resultNodeMap = [](node v) { return v;},
		int64_t	timelimit = -1
	)

Calculates the maximum density subgraph of G.

Returns the subgraph of G given by the nodes of the subgraph. The subgraph with the highest density, which is \(\frac{|E|}{|V|}\) of the subgraph, is returned. The graph is treated as undirected and unweighted.

The algorithm is based on: A. V. Goldberg. Finding a maximum density subgraph. EECS Department, University of California, Berkeley. Technical Report No. UCB/CSD-84-171, 1984. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-171.pdf

Internally, the MinSTCutMaxFlow algorithm (using MaxFlowGoldbergTarjan) is called \(\mathcal{O}(\log n)\) times. Assuming a runtime of \(\mathcal{O}(mn^2)\) for the min cut algorithm, the overall runtime is \(\mathcal{O}(mn^2\log n)\).

Side Effect

Note that the input graph G is modified. If this is not wanted, use a GraphCopy or GraphCopySimple.

resultNodeMap

resultNodeMap can be used if subgraphNodes does not belong to G. This helps when passing in a GraphCopy or GraphCopySimple:

NodeSet subgraphNodes(G);
GraphCopySimple GC(G);
maximumDensitySubgraph(GC, subgraphNodes, [&](node n){ return GC.original(n);});

Parameters

G	is the input graph.
subgraphNodes	is the set of nodes inducing the subgraph.
resultNodeMap	maps each subgraph node (nodes of G) to some other node
timelimit	set to a value greater than -1 to set a timelimit in milliseconds. Note that 0 is a valid timelimit. When encountering a timelimit there is no valid result.

Returns

true, if the algorithm was successful and did not run into a timeout.