 # OpenGraph DrawingFramework

v. 2020.02 (Catalpa)

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

#include <ogdf/graphalg/MaxAdjOrdering.h>

## Public Member Functions

Standard constructor. More...

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

Standard constructor.

Standard destructor.

## ◆ calc() [1/4]

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

Calculates one MAO starting with the node with index 0.

Parameters
 G is the Graph to work on MAO is 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
 G is the Graph to work on MAO is the pointer to a list that stores the MAO Forests is 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
 G is the Graph to work on s Node to start the MAO with MAO is 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
 G is the Graph to work on s Node to start the MAO with MAO is the pointer to a list that stores the MAO Forests is 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
 G is the Graph to work on MAOs List 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
 G is the graph to work on MAOs List of all MAOs. So it must be a list of lists of vertices. Fs List 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
 G is the Graph to work on MAO is 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
 n Number of nodes currentOrder The partial MAO to this point currentForest The partial forest decomposition to this point currentUnsorted Nodes that are still left to sort r Values on the nodes that count the edges to the partial MAO MAOs The list of all MAOs to this point Fs The 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
 n Number of nodes currentOrder The partial MAO to this point currentUnsorted Nodes that are still left to sort r Values on the nodes that count the edges to the partial MAO MAOs The 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
 G is the graph to work on Orderings contains Lists that are supposedly MAOs Perms contains 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
 G is the graph to work on Ordering is 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
 G is the graph to work on Ordering is 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
 GA Graphattributes of the Graph to paint MAO Mao 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
 GA Graphattributes of the Graph to paint MAO Mao to use for ordering the nodes F A Forest can also be included

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