# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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< true > &subgraphNodes, std::function< node(node)> resultNodeMap=[](node v) { return v;}, int64_t timelimit=-1)
Calculates the maximum density subgraph of G.

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

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<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<class LISTITERATOR >
void ogdf::inducedSubGraph (const Graph &G, LISTITERATOR start, GraphCopySimple &subGraph)
Computes the subgraph induced by a list of nodes.

template<class NODELISTITERATOR , class EDGELIST >
void ogdf::inducedSubgraph (Graph &G, NODELISTITERATOR &it, EDGELIST &E)
Computes the edges in a node-induced subgraph.

## Detailed Description

Provides functions dealing with induced subgraphs and finding cliques.

## ◆ 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 55 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 72 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 109 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 146 of file extended_graph_alg.h.

## ◆ inducedSubgraph()

 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 179 of file extended_graph_alg.h.

## ◆ maximumDensitySubgraph()

 bool ogdf::maximumDensitySubgraph ( Graph & G, NodeSet< true > & 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:
maximumDensitySubgraph(GC, subgraphNodes, [&](node n){ return GC.original(n);});
Copies of graphs with mapping between nodes and edges.
Definition GraphCopy.h:59
Class for the representation of nodes.
Definition Graph_d.h:177
Node sets.
Definition NodeSet.h:54
bool maximumDensitySubgraph(Graph &G, NodeSet< true > &subgraphNodes, std::function< node(node)> resultNodeMap=[](node v) { return v;}, int64_t timelimit=-1)
Calculates the maximum density subgraph of G.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
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.