ogdf::GreedyCycleRemoval Class Reference

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

#include <ogdf/layered/GreedyCycleRemoval.h>

Inheritance diagram for ogdf::GreedyCycleRemoval:

List of all members.

Public Member Functions
void	call (const Graph &G, List< edge > &arcSet)
	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 ()
void	callAndDelete (Graph &G)
	Makes G acyclic by removing edges.
void	callAndReverse (Graph &G, List< edge > &reversed)
	Makes G acyclic by reversing edges.
void	callAndReverse (Graph &G)
	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 65 of file GreedyCycleRemoval.h.

---

Member Function Documentation

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

virtual

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

Implements ogdf::AcyclicSubgraphModule.

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

private

---

Member Data Documentation

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

private

Definition at line 76 of file GreedyCycleRemoval.h.

int ogdf::GreedyCycleRemoval::m_counter

private

Definition at line 73 of file GreedyCycleRemoval.h.

NodeArray<int> ogdf::GreedyCycleRemoval::m_in

private

Definition at line 75 of file GreedyCycleRemoval.h.

NodeArray<int> ogdf::GreedyCycleRemoval::m_index

private

Definition at line 75 of file GreedyCycleRemoval.h.

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

private

Definition at line 77 of file GreedyCycleRemoval.h.

int ogdf::GreedyCycleRemoval::m_max

private

Definition at line 73 of file GreedyCycleRemoval.h.

int ogdf::GreedyCycleRemoval::m_min

private

Definition at line 73 of file GreedyCycleRemoval.h.

NodeArray<int> ogdf::GreedyCycleRemoval::m_out

private

Definition at line 75 of file GreedyCycleRemoval.h.

NodeArray<bool> ogdf::GreedyCycleRemoval::m_visited

private

Definition at line 78 of file GreedyCycleRemoval.h.

---

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

• ogdf/layered/GreedyCycleRemoval.h