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

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


Provides functions dealing with induced subgraphs and finding cliques.
◆ inducedSubGraph() [1/4]
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]
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]
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]
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()
Computes the edges in a nodeinduced 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 nodeinduced subgraph. 
Definition at line 179 of file extended_graph_alg.h.
◆ maximumDensitySubgraph()
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/CSD84171, 1984. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD84171.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:
Copies of graphs with mapping between nodes and edges.
Class for the representation of nodes.
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.