Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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