Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph.
More...
#include <ogdf/graphalg/MaxAdjOrdering.h>
|
| 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...
|
|
|
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...
|
|
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 52 of file MaxAdjOrdering.h.
◆ MaxAdjOrdering()
ogdf::MaxAdjOrdering::MaxAdjOrdering |
( |
| ) |
|
◆ ~MaxAdjOrdering()
ogdf::MaxAdjOrdering::~MaxAdjOrdering |
( |
| ) |
|
◆ calc() [1/4]
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]
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]
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]
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]
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]
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()
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]
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]
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()
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]
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]
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: