Open
Graph Drawing
Framework

 v. 2020.02 (Catalpa)
 

ogdf::MaxAdjOrdering Class Reference

Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph. More...

#include <ogdf/graphalg/MaxAdjOrdering.h>

Public Member Functions

 MaxAdjOrdering ()
 Standard constructor. More...
 
 ~MaxAdjOrdering ()
 Standard destructor. More...
 
void calc (const Graph *G, ListPure< node > *MAO)
 Calculates one MAO starting with the node with index 0. More...
 
void calc (const Graph *G, ListPure< node > *MAO, ListPure< ListPure< edge >> *Forests)
 Calculates one MAO starting with the node with index 0. More...
 
void calc (const Graph *G, node s, ListPure< node > *MAO)
 Calculates one MAO starting with a given node. More...
 
void calc (const Graph *G, node s, ListPure< node > *MAO, ListPure< ListPure< edge >> *Forests)
 Calculates one MAO starting with a given node. More...
 
void calcAll (const Graph *G, ListPure< ListPure< node >> *MAOs)
 Calculates all MAOs of a given graph. More...
 
void calcAll (const Graph *G, ListPure< ListPure< node >> *MAOs, ListPure< ListPure< ListPure< edge >>> *Fs)
 Calculates all MAOs including their associated forest decompositions of a given graph. More...
 
void calcBfs (const Graph *G, ListPure< node > *MAO)
 Calculates one MAO starting with the node with index 0 and lex-bfs tie breaking. More...
 
bool testIfAllMAOs (const Graph *G, ListPure< ListPure< node >> *Orderings, ListPure< ListPure< node >> *Perms)
 testIfAllMAOs checks all permutations (must be provided) if they are a MAO and if yes searches this ordering in the provided list. More...
 
bool testIfMAO (const Graph *G, ListPure< node > *Ordering)
 Test if a given ordering is a MAO. More...
 
bool testIfMAOBfs (const Graph *G, ListPure< node > *Ordering)
 Test if a given ordering is a MAO that follows lex-bfs tie breaking. More...
 
void visualize (GraphAttributes *GA, ListPure< node > *MAO)
 Convenient way to visualize a MAO with the LinearLayout class. More...
 
void visualize (GraphAttributes *GA, ListPure< node > *MAO, ListPure< ListPure< edge >> *F)
 Convenient way to visualize a MAO with the LinearLayout class. More...
 

Private Member Functions

void m_calcAllMAOs_recursion (int n, ListPure< node > currentOrder, ListPure< ListPure< edge >> currentForest, ListPure< node > currentUnsorted, NodeArray< int > r, ListPure< ListPure< node >> *MAOs, ListPure< ListPure< ListPure< edge >>> *Fs)
 This method gets called recursively to generate all MAOs and their induced forest decompositions of the edges via backtracking. More...
 
void m_calcAllMAOs_recursion (int n, ListPure< node > currentOrder, ListPure< node > currentUnsorted, NodeArray< int > r, ListPure< ListPure< node >> *MAOs)
 This method gets called recursively to generate all MAOs via backtracking. More...
 

Detailed Description

Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph.

The class MaxAdjOrdering provides one algorithm to calculate a MAO or all MAOs of a given graph. It returns a ListPure of nodes or a list of ListPures that contain the ordering.

Definition at line 51 of file MaxAdjOrdering.h.

Constructor & Destructor Documentation

◆ MaxAdjOrdering()

ogdf::MaxAdjOrdering::MaxAdjOrdering ( )

Standard constructor.

◆ ~MaxAdjOrdering()

ogdf::MaxAdjOrdering::~MaxAdjOrdering ( )

Standard destructor.

Member Function Documentation

◆ calc() [1/4]

void ogdf::MaxAdjOrdering::calc ( const Graph G,
ListPure< node > *  MAO 
)

Calculates one MAO starting with the node with index 0.

Parameters
Gis the Graph to work on
MAOis the pointer to a list that stores the MAO

◆ calc() [2/4]

void ogdf::MaxAdjOrdering::calc ( const Graph G,
ListPure< node > *  MAO,
ListPure< ListPure< edge >> *  Forests 
)

Calculates one MAO starting with the node with index 0.

Parameters
Gis the Graph to work on
MAOis the pointer to a list that stores the MAO
Forestsis the pointer to a list that stores the forest decomposition associated with the MAO

◆ calc() [3/4]

void ogdf::MaxAdjOrdering::calc ( const Graph G,
node  s,
ListPure< node > *  MAO 
)

Calculates one MAO starting with a given node.

Parameters
Gis the Graph to work on
sNode to start the MAO with
MAOis the pointer to a list that stores the MAO

◆ calc() [4/4]

void ogdf::MaxAdjOrdering::calc ( const Graph G,
node  s,
ListPure< node > *  MAO,
ListPure< ListPure< edge >> *  Forests 
)

Calculates one MAO starting with a given node.

Parameters
Gis the Graph to work on
sNode to start the MAO with
MAOis the pointer to a list that stores the MAO
Forestsis the pointer to a list that stores the forest decomposition associated with the MAO

◆ calcAll() [1/2]

void ogdf::MaxAdjOrdering::calcAll ( const Graph G,
ListPure< ListPure< node >> *  MAOs 
)

Calculates all MAOs of a given graph.

Parameters
Gis the Graph to work on
MAOsList of all MAOs. So it must be a list of lists

◆ calcAll() [2/2]

void ogdf::MaxAdjOrdering::calcAll ( const Graph G,
ListPure< ListPure< node >> *  MAOs,
ListPure< ListPure< ListPure< edge >>> *  Fs 
)

Calculates all MAOs including their associated forest decompositions of a given graph.

Parameters
Gis the graph to work on
MAOsList of all MAOs. So it must be a list of lists of vertices.
FsList of all forest decompositions. So it must be a list of lists of lists of edges.

◆ calcBfs()

void ogdf::MaxAdjOrdering::calcBfs ( const Graph G,
ListPure< node > *  MAO 
)

Calculates one MAO starting with the node with index 0 and lex-bfs tie breaking.

Parameters
Gis the Graph to work on
MAOis the pointer to a list that stores the MAO

◆ m_calcAllMAOs_recursion() [1/2]

void ogdf::MaxAdjOrdering::m_calcAllMAOs_recursion ( int  n,
ListPure< node currentOrder,
ListPure< ListPure< edge >>  currentForest,
ListPure< node currentUnsorted,
NodeArray< int >  r,
ListPure< ListPure< node >> *  MAOs,
ListPure< ListPure< ListPure< edge >>> *  Fs 
)
private

This method gets called recursively to generate all MAOs and their induced forest decompositions of the edges via backtracking.

Parameters
nNumber of nodes
currentOrderThe partial MAO to this point
currentForestThe partial forest decomposition to this point
currentUnsortedNodes that are still left to sort
rValues on the nodes that count the edges to the partial MAO
MAOsThe list of all MAOs to this point
FsThe list of all forests to this point

◆ m_calcAllMAOs_recursion() [2/2]

void ogdf::MaxAdjOrdering::m_calcAllMAOs_recursion ( int  n,
ListPure< node currentOrder,
ListPure< node currentUnsorted,
NodeArray< int >  r,
ListPure< ListPure< node >> *  MAOs 
)
private

This method gets called recursively to generate all MAOs via backtracking.

Parameters
nNumber of nodes
currentOrderThe partial MAO to this point
currentUnsortedNodes that are still left to sort
rValues on the nodes that count the edges to the partial MAO
MAOsThe list of all MAOs to this point

◆ testIfAllMAOs()

bool ogdf::MaxAdjOrdering::testIfAllMAOs ( const Graph G,
ListPure< ListPure< node >> *  Orderings,
ListPure< ListPure< node >> *  Perms 
)

testIfAllMAOs checks all permutations (must be provided) if they are a MAO and if yes searches this ordering in the provided list.

If one permutation is no MAO it still gets searched to rule out any false elements in Perms. So we make sure we generated all MAOs of G.

Parameters
Gis the graph to work on
Orderingscontains Lists that are supposedly MAOs
Permscontains all permutations of a graph with the same size as G
Returns

◆ testIfMAO()

bool ogdf::MaxAdjOrdering::testIfMAO ( const Graph G,
ListPure< node > *  Ordering 
)

Test if a given ordering is a MAO.

Parameters
Gis the graph to work on
Orderingis a ListPure that contains a permutation of the nodes

◆ testIfMAOBfs()

bool ogdf::MaxAdjOrdering::testIfMAOBfs ( const Graph G,
ListPure< node > *  Ordering 
)

Test if a given ordering is a MAO that follows lex-bfs tie breaking.

Parameters
Gis the graph to work on
Orderingis a ListPure that contains a permutation of the nodes

◆ visualize() [1/2]

void ogdf::MaxAdjOrdering::visualize ( GraphAttributes GA,
ListPure< node > *  MAO 
)

Convenient way to visualize a MAO with the LinearLayout class.

Parameters
GAGraphattributes of the Graph to paint
MAOMao to use for ordering the nodes

◆ visualize() [2/2]

void ogdf::MaxAdjOrdering::visualize ( GraphAttributes GA,
ListPure< node > *  MAO,
ListPure< ListPure< edge >> *  F 
)

Convenient way to visualize a MAO with the LinearLayout class.

Parameters
GAGraphattributes of the Graph to paint
MAOMao to use for ordering the nodes
FA Forest can also be included

The documentation for this class was generated from the following file: