P.I.G.A.L.E.
1.3.9
Public Implementation of a Graph Algorithm
Library and Editor
H. de Fraysseix      P. Ossona de Mendez

---

DFSKura2 Class Reference

Inheritance diagram for DFSKura2:

[legend]

Collaboration diagram for DFSKura2:

[legend]

List of all members.

Public Member Functions

• DFSKura2 (DFSGraph &DG)
• ~DFSKura2 ()
• void DFSDualOrder ()
• int SmallerThan (tvertex v, tvertex w)
• int SmallerEqual (tvertex v, tvertex w)
• int Comparable (tvertex v, tvertex w)
• int ComparableDifferent (tvertex v, tvertex w)
• int OrdInterlaced (tedge e, tedge f)
• int Interlaced (tedge e, tedge f)
• int OrdChainInterlaced (tedge e, tedge f)
• tvertex infimum (tvertex v, tvertex w)
• tedge HighestCove (tvertex v1, tvertex v2)
• tvertex cover (tvertex from, tvertex to)
• void ComputeAncestors ()
• void Flash (tedge e, short c)
• void FlashBest (tedge e, short c)
• bool KuraFound ()
• int GetRetVal ()

Protected Member Functions

• void Compute ()
• void ComputeImportantVertices ()
• void ComputeDownEdge ()
• tedge FindInterlaced (tedge e, tvertex lv, tvertex tv)
• tedge FindLastInterlaced (tedge e, tvertex lv, tvertex tv)
• bool IsDownEdgeOk (tedge e)
• bool IsDownEdgeEqualOk (tedge e)
• bool IsNPEdgeOk (tedge e)
• tedge FindLowEdge (tedge e)
• void Keep (tedge e, short c)
• void UnKeep (tedge e, short c)

Private Attributes

• Prop< bool > mark
• Prop< int > DualOrder
• Prop< tvertex > low
• Prop< tedge > elow
• svector< tvertex > ancestor
• svector< tvertex > ancestor_son
• tedge down_edge
• tedge down_edge_equal
• tvertex down_vertex
• tvertex fils1
• tvertex fils2
• tvertex branch
• tvertex npattach
• tvertex l1
• tvertex l2
• tvertex lp
• tvertex t1
• tvertex t2
• bool Success
• int RetVal
• short lastc
• tedge laste

---

Constructor & Destructor Documentation

DFSKura2

(

DFSGraph &

DG

)

[inline]

~DFSKura2

(

)

[inline]

---

Member Function Documentation

void DFSDualOrder

(

)

int SmallerThan	(	tvertex	v,
		tvertex	w
	)			[inline]

int SmallerEqual	(	tvertex	v,
		tvertex	w
	)			[inline]

int Comparable	(	tvertex	v,
		tvertex	w
	)			[inline]

int ComparableDifferent	(	tvertex	v,
		tvertex	w
	)			[inline]

int OrdInterlaced	(	tedge	e,
		tedge	f
	)			[inline]

int Interlaced	(	tedge	e,
		tedge	f
	)			[inline]

int OrdChainInterlaced	(	tedge	e,
		tedge	f
	)			[inline]

tvertex infimum	(	tvertex	v,
		tvertex	w
	)

tedge HighestCove	(	tvertex	v1,
		tvertex	v2
	)

tvertex cover	(	tvertex	from,
		tvertex	to
	)

void ComputeAncestors

(

)

void Flash	(	tedge	e,
		short	c
	)			[inline]

void FlashBest	(	tedge	e,
		short	c
	)			[inline]

bool KuraFound

(

)

[inline]

int GetRetVal

(

)

[inline]

void Compute

(

)

[protected]

void ComputeImportantVertices

(

)

[inline, protected]

void ComputeDownEdge

(

)

[protected]

tedge FindInterlaced	(	tedge	e,
		tvertex	lv,
		tvertex	tv
	)			[protected]

tedge FindLastInterlaced	(	tedge	e,
		tvertex	lv,
		tvertex	tv
	)			[protected]

bool IsDownEdgeOk

(

tedge

e

)

[inline, protected]

bool IsDownEdgeEqualOk

(

tedge

e

)

[inline, protected]

bool IsNPEdgeOk

(

tedge

e

)

[inline, protected]

tedge FindLowEdge

(

tedge

e

)

[inline, protected]

void Keep	(	tedge	e,
		short	c
	)			[inline, protected]

void UnKeep	(	tedge	e,
		short	c
	)			[inline, protected]

---

Member Data Documentation

Prop<bool> mark [private]

Prop<int> DualOrder [private]

Prop<tvertex> low [private]

Prop<tedge> elow [private]

svector<tvertex> ancestor [private]

svector<tvertex> ancestor_son [private]

tedge down_edge [private]

tedge down_edge_equal [private]

tvertex down_vertex [private]

tvertex fils1 [private]

tvertex fils2 [private]

tvertex branch [private]

tvertex npattach [private]

tvertex l1 [private]

tvertex l2 [private]

tvertex lp [private]

tvertex t1 [private]

tvertex t2 [private]

bool Success [private]

int RetVal [private]

short lastc [private]

tedge laste [private]

---