ogdf::GreedyCycleRemoval Class Reference

Greedy algorithm for computing a maximal acyclic subgraph. More...

#include <ogdf/layered/GreedyCycleRemoval.h>

Inheritance diagram for ogdf::GreedyCycleRemoval:

Public Member Functions
	GreedyCycleRemoval ()
virtual void	call (const Graph &G, List< edge > &arcSet) override
	Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.
Public Member Functions inherited from ogdf::AcyclicSubgraphModule
	AcyclicSubgraphModule ()
	Initializes an acyclic subgraph module.
virtual	~AcyclicSubgraphModule ()
	Destruction.
void	callAndDelete (Graph &G)
	Makes G acyclic by removing edges.
void	callAndReverse (Graph &G)
	Makes G acyclic by reversing edges.
void	callAndReverse (Graph &G, List< edge > &reversed)
	Makes G acyclic by reversing edges.
void	operator() (const Graph &G, List< edge > &arcSet)
	Computes the set of edges arcSet which have to be removed for obtaining an acyclic subgraph of G.

Private Member Functions
void	dfs (node v, const Graph &G)

Private Attributes
Array< ListPure< node > >	m_B
int	m_counter
NodeArray< int >	m_in
NodeArray< int >	m_index
NodeArray< ListIterator< node > >	m_item
int	m_max
int	m_min
NodeArray< int >	m_out
NodeArray< bool >	m_visited

Detailed Description

Greedy algorithm for computing a maximal acyclic subgraph.

The algorithm applies a greedy heuristic to compute a maximal acyclic subgraph and works in linear-time.

Definition at line 47 of file GreedyCycleRemoval.h.

Constructor & Destructor Documentation

GreedyCycleRemoval()

ogdf::GreedyCycleRemoval::GreedyCycleRemoval ( )

inline

Definition at line 49 of file GreedyCycleRemoval.h.

Member Function Documentation

call()

virtual void ogdf::GreedyCycleRemoval::call ( const Graph &  G, List< edge > &  arcSet  )

overridevirtual

Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.

Implements ogdf::AcyclicSubgraphModule.

dfs()

void ogdf::GreedyCycleRemoval::dfs ( node  v, const Graph &  G  )

private

Member Data Documentation

m_B

Array<ListPure<node> > ogdf::GreedyCycleRemoval::m_B

private

Definition at line 60 of file GreedyCycleRemoval.h.

m_counter

int ogdf::GreedyCycleRemoval::m_counter

private

Definition at line 57 of file GreedyCycleRemoval.h.

m_in

NodeArray<int> ogdf::GreedyCycleRemoval::m_in

private

Definition at line 59 of file GreedyCycleRemoval.h.

m_index

NodeArray<int> ogdf::GreedyCycleRemoval::m_index

private

Definition at line 59 of file GreedyCycleRemoval.h.

m_item

NodeArray<ListIterator<node> > ogdf::GreedyCycleRemoval::m_item

private

Definition at line 61 of file GreedyCycleRemoval.h.

m_max

int ogdf::GreedyCycleRemoval::m_max

private

Definition at line 57 of file GreedyCycleRemoval.h.

m_min

int ogdf::GreedyCycleRemoval::m_min

private

Definition at line 57 of file GreedyCycleRemoval.h.

m_out

NodeArray<int> ogdf::GreedyCycleRemoval::m_out

private

Definition at line 59 of file GreedyCycleRemoval.h.

m_visited

NodeArray<bool> ogdf::GreedyCycleRemoval::m_visited

private

Definition at line 62 of file GreedyCycleRemoval.h.

---

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

• include/ogdf/layered/GreedyCycleRemoval.h