Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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

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
LISTITERATORis the type of iterators for the input list of nodes.
Parameters
Gis the input graph.
startis a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraphis 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
LISTITERATORis the type of iterators for the input list of nodes.
Parameters
Gis the input graph.
startis a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraphis assigned the computed subgraph.
nodeTableOrig2Newis 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
LISTITERATORis the type of iterators for the input list of nodes.
Parameters
Gis the input graph.
startis a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraphis assigned the computed subgraph.
nodeTableOrig2Newis assigned a mapping from the nodes in G to the nodes in subGraph.
edgeTableOrig2Newis 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
LISTITERATORis the type of iterators for the input list of nodes.
Parameters
Gis the input graph.
startis a list iterator pointing to the first element in a list of nodes, for which an induced subgraph shall be computed.
subGraphis 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
NODELISTITERATORis the type of iterators for the input list of nodes.
EDGELISTis the type of the returned edge list.
Parameters
Gis the input graph.
itis a list iterator pointing to the first element in a list of nodes, whose induced subgraph is considered.
Eis 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
Gis the input graph.
subgraphNodesis the set of nodes inducing the subgraph.
resultNodeMapmaps each subgraph node (nodes of G) to some other node
timelimitset 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.