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

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:

include/ogdf/graphalg/MaxAdjOrdering.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MaxAdjOrdering()

◆ ~MaxAdjOrdering()

Member Function Documentation

◆ calc() [1/4]

◆ calc() [2/4]

◆ calc() [3/4]

◆ calc() [4/4]

◆ calcAll() [1/2]

◆ calcAll() [2/2]

◆ calcBfs()

◆ m_calcAllMAOs_recursion() [1/2]

◆ m_calcAllMAOs_recursion() [2/2]

◆ testIfAllMAOs()

◆ testIfMAO()

◆ testIfMAOBfs()

◆ visualize() [1/2]

◆ visualize() [2/2]

Open
Graph Drawing
Framework