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

---

TopologicalGraph Class Reference

Inheritance diagram for TopologicalGraph:

[legend]

Collaboration diagram for TopologicalGraph:

[legend]

List of all members.

Public Member Functions

• void init ()
• void keep ()
• void keepr ()
• void keeponly ()
• TopologicalGraph (Graph &G, int)
• TopologicalGraph (GraphContainer &G)
• TopologicalGraph (GraphAccess &G)
• ~TopologicalGraph ()
• void StrictReset ()
• Graph & me ()
• const Graph & me () const
• tbrin FirstBrin (const tvertex &v) const
• tedge FirstEdge (const tvertex &v) const
• tbrin NextCirBrin (const tbrin &b) const
• tbrin PrevCirBrin (const tbrin &b) const
• tbrin NextBrin (tvertex v, tbrin b) const
• tbrin PrevBrin (tvertex v, tbrin b) const
• tedge NextCirEdge (tvertex v, tedge e) const
• tedge PrevCirEdge (const tvertex &v, const tedge &e) const
• tedge NextEdge (const tvertex &v, const tedge &e) const
• tedge PrevEdge (const tvertex &v, const tedge &e) const
• Graph * SmallDup () const
• tedge NewEdge (const tbrin &ref1, const tbrin &ref2)
• tedge NewEdge (const tvertex &vv1, const tvertex &vv2, tedge e0=0)
• void DeleteEdge (const tedge &e)
• void MoveBrin (const tbrin &b, const tvertex &to)
• void MoveBrinToFirst (const tbrin &b)
• tvertex ContractEdge (const tedge &e)
• tvertex BissectEdge (const tedge &e)
• void ReverseEdge (const tedge &e)
• void SwitchOrientations ()
• void FixOrientation ()
• void RestoreOrientation ()
• tvertex NewVertex ()
• void DeleteVertex (const tvertex &v)
• int Degree (const tvertex &v)
• int InDegree (const tvertex &v)
• int OutDegree (const tvertex &v)
• int RemoveLoops ()
• bool CheckNoLoops ()
• int RemoveIsolatedVertices ()
• int ComputeGenus ()
• int NumFaces ()
• int Genus ()
• int FaceNumberIsthmus (const tbrin &b0)
• int FaceWalkLength (const tbrin &b0)
• int FaceLength (const tbrin &b0)
• int LongestFaceWalk (tbrin &b, int &len)
• int LongestFace (tbrin &b, int &len)
• bool DebugCir ()
• int NumberOfConnectedComponents ()
• int DFS (svector< tvertex > &nvin, svector< tbrin > &tb, svector< int > &dfsnum, tbrin b0=tbrin(1))
• int DFS (svector< tvertex > &nvin, tbrin b0=tbrin(1))
• int DFSRenum (svector< tvertex > &nvin, svector< tedge > &ie, tbrin b0=tbrin(1))
• int Simplify ()
• int ExpandEdges ()
• int RemoveIsthmus ()
• bool CheckSimple ()
• bool CheckRegular (int &d)
• bool MinMaxDegree (int &dmin, int &dmax)
• bool CheckConnected ()
• int ColorConnectedComponents ()
• bool CheckBiconnected ()
• bool CheckTriconnected ()
• bool CheckFourconnected ()
• bool CheckNoC3Sep ()
• bool CheckSubdivTriconnected ()
• bool CheckBipartite (bool Color=false)
• bool CheckHypergraph (tvertex v0, bool v0ise=false)
• bool CheckAcyclic (int &ns, int &nt)
• bool TopSort (svector< tbrin > &topin, svector< tvertex > &order, bool revert=false)
• bool CheckSerieParallel ()
• int BFS (svector< int > &comp)
• int MakeConnected (bool mark_roots=false)
• int MakeConnectedVertex ()
• bool FindPlanarMap ()
• bool CheckPlanar ()
• void ZigZag (tbrin start)
• int ZigZagTriangulate ()
• svector< tbrin > & ComputeFpbrin ()
• int Rotate (tedge e)
• int Opt2Biconnect ()
• tedge IdentifyEdge (tvertex &v1, tvertex &v2)
• int VertexQuadrangulate ()
• int _VertexQuadrangulate (bool First)
• int VertexTriangulate ()
• GraphContainer * DualGraph ()
• GraphContainer * AngleGraph ()
• int Biconnect ()
• int Opt6Biconnect ()
• int NpBiconnect (bool withVertices=false)
• int NpBiconnectVertex ()
• int BipolarPlan (tbrin FirstBrin)
• int PseudoBipolarPlan (tbrin &st_brin, int &NumberOfSinks)
• int SchnyderOrient (tbrin FirstBrin)
• int Schnyder (bool schnyderRect, bool schnyderColor, bool schnyderLongestFace, tbrin FirstBrin)
• int SchnyderXYZ (bool schnyderColor, bool schnyderLongestFace, tbrin FirstBrin, svector< int > &x, svector< int > &y, svector< int > &z)
• int SchnyderV (bool schnyderRect, bool schnyderColor, bool schnyderLongestFace, tbrin FirstBrin)
• int InfOrient ()
• int TriconTriangulate ()
• int Tricon3orient ()
• int MaxPlanar ()
• int MaxPlanar (svector< bool > &mark)
• int Planarity (tbrin b0=1)
• int NewPlanarity (tbrin b0=1)
• int CotreeCritical (int &ret)
• int CotreeCritical (svector< bool > &mark)
• int KCotreeCritical (int &)
• int Kuratowski ()
• int Kuratowski (svector< bool > &mark)
• int KKuratowski ()
• int TestPlanar ()
• int TestNewPlanar ()
• int TestPlanar2 ()
• GraphContainer * Vis_a_vis_Graph ()
• GraphContainer * CrossingEdgesGraph ()

Public Attributes

• int ConstructedCir
• int ConstructedPbrin
• Prop< tbrin > cir
• Prop< tbrin > acir
• Prop< tbrin > pbrin
• Prop1< tbrin > extbrin
• Prop1< int > planarMap
• int genus

Protected Member Functions

• void PrivateReverseEdge (const tedge &e)
• tbrin NewSwapLabel (const tbrin &b, const tedge &ref)
• void SwapEdge (const tedge &e)
• void SwapVertex (const tvertex &v)
• void UnlinkBrin (const tbrin &b)
• void InsertBrin (const tvertex &v, const tbrin &b)
• int ComputeSTlist (tbrin st_brin)
• void ZigZag ()

---

Constructor & Destructor Documentation

TopologicalGraph	(	Graph &	G,
		int
	)			[inline]

TopologicalGraph

(

GraphContainer &

G

)

[inline]

TopologicalGraph

(

GraphAccess &

G

)

[inline]

~TopologicalGraph

(

)

[inline]

---

Member Function Documentation

void init

(

)

Reimplemented in GeometricGraph, and SplitGraph.

void keep

(

)

[inline]

Reimplemented from Graph.

Reimplemented in GeometricGraph.

void keepr

(

)

[inline]

Reimplemented from Graph.

Reimplemented in GeometricGraph.

void keeponly

(

)

[inline]

Reimplemented from Graph.

Reimplemented in GeometricGraph.

void PrivateReverseEdge

(

const tedge &

e

)

[protected]

void StrictReset

(

)

[inline]

Reimplemented from Graph.

Reimplemented in GeometricGraph.

Graph& me

(

)

[inline]

Reimplemented from Graph.

Reimplemented in GeometricGraph.

const Graph& me

(

)

const [inline]

Reimplemented from Graph.

Reimplemented in GeometricGraph.

tbrin FirstBrin

(

const tvertex &

v

)

const [inline]

tedge FirstEdge

(

const tvertex &

v

)

const [inline]

tbrin NextCirBrin

(

const tbrin &

b

)

const [inline]

tbrin PrevCirBrin

(

const tbrin &

b

)

const [inline]

tbrin NextBrin	(	tvertex	v,
		tbrin	b
	)			const [inline]

tbrin PrevBrin	(	tvertex	v,
		tbrin	b
	)			const [inline]

tedge NextCirEdge	(	tvertex	v,
		tedge	e
	)			const [inline]

tedge PrevCirEdge	(	const tvertex &	v,
		const tedge &	e
	)			const [inline]

tedge NextEdge	(	const tvertex &	v,
		const tedge &	e
	)			const [inline]

tedge PrevEdge	(	const tvertex &	v,
		const tedge &	e
	)			const [inline]

Graph* SmallDup

(

)

const

tedge NewEdge	(	const tbrin &	ref1,
		const tbrin &	ref2
	)

Reimplemented in GeometricGraph.

tedge NewEdge	(	const tvertex &	vv1,
		const tvertex &	vv2,
		tedge	e0 = 0
	)

void DeleteEdge

(

const tedge &

e

)

void MoveBrin	(	const tbrin &	b,
		const tvertex &	to
	)

void MoveBrinToFirst

(

const tbrin &

b

)

tvertex ContractEdge

(

const tedge &

e

)

tvertex BissectEdge

(

const tedge &

e

)

Reimplemented in GeometricGraph.

void ReverseEdge

(

const tedge &

e

)

void SwitchOrientations

(

)

void FixOrientation

(

)

void RestoreOrientation

(

)

tvertex NewVertex

(

)

void DeleteVertex

(

const tvertex &

v

)

int Degree

(

const tvertex &

v

)

int InDegree

(

const tvertex &

v

)

int OutDegree

(

const tvertex &

v

)

int RemoveLoops

(

)

bool CheckNoLoops

(

)

int RemoveIsolatedVertices

(

)

int ComputeGenus

(

)

int NumFaces

(

)

int Genus

(

)

[inline]

int FaceNumberIsthmus

(

const tbrin &

b0

)

int FaceWalkLength

(

const tbrin &

b0

)

int FaceLength

(

const tbrin &

b0

)

[inline]

int LongestFaceWalk	(	tbrin &	b,
		int &	len
	)

int LongestFace	(	tbrin &	b,
		int &	len
	)

bool DebugCir

(

)

int NumberOfConnectedComponents

(

)

[inline]

int DFS	(	svector< tvertex > &	nvin,
		svector< tbrin > &	tb,
		svector< int > &	dfsnum,
		tbrin	b0 = tbrin(1)
	)

int DFS	(	svector< tvertex > &	nvin,
		tbrin	b0 = tbrin(1)
	)

int DFSRenum	(	svector< tvertex > &	nvin,
		svector< tedge > &	ie,
		tbrin	b0 = tbrin(1)
	)

int Simplify

(

)

int ExpandEdges

(

)

int RemoveIsthmus

(

)

bool CheckSimple

(

)

bool CheckRegular

(

int &

d

)

bool MinMaxDegree	(	int &	dmin,
		int &	dmax
	)

bool CheckConnected

(

)

int ColorConnectedComponents

(

)

bool CheckBiconnected

(

)

Reimplemented from Graph.

bool CheckTriconnected

(

)

bool CheckFourconnected

(

)

bool CheckNoC3Sep

(

)

bool CheckSubdivTriconnected

(

)

bool CheckBipartite

(

bool

Color = false

)

bool CheckHypergraph	(	tvertex	v0,
		bool	v0ise = false
	)

bool CheckAcyclic	(	int &	ns,
		int &	nt
	)

bool TopSort	(	svector< tbrin > &	topin,
		svector< tvertex > &	order,
		bool	revert = false
	)

bool CheckSerieParallel

(

)

int BFS

(

svector< int > &

comp

)

int MakeConnected

(

bool

mark_roots = false

)

int MakeConnectedVertex

(

)

bool FindPlanarMap

(

)

bool CheckPlanar

(

)

[inline]

void ZigZag

(

tbrin

start

)

int ZigZagTriangulate

(

)

svector< tbrin > & ComputeFpbrin

(

)

int Rotate

(

tedge

e

)

int Opt2Biconnect

(

)

tedge IdentifyEdge	(	tvertex &	v1,
		tvertex &	v2
	)

int VertexQuadrangulate

(

)

int _VertexQuadrangulate

(

bool

First

)

int VertexTriangulate

(

)

GraphContainer * DualGraph

(

)

Reimplemented in GeometricGraph.

GraphContainer * AngleGraph

(

)

Reimplemented in GeometricGraph.

int Biconnect

(

)

int Opt6Biconnect

(

)

int NpBiconnect

(

bool

withVertices = false

)

int NpBiconnectVertex

(

)

int BipolarPlan

(

tbrin

FirstBrin

)

int PseudoBipolarPlan	(	tbrin &	st_brin,
		int &	NumberOfSinks
	)

int SchnyderOrient

(

tbrin

FirstBrin

)

int Schnyder	(	bool	schnyderRect,
		bool	schnyderColor,
		bool	schnyderLongestFace,
		tbrin	FirstBrin
	)

int SchnyderXYZ	(	bool	schnyderColor,
		bool	schnyderLongestFace,
		tbrin	FirstBrin,
		svector< int > &	x,
		svector< int > &	y,
		svector< int > &	z
	)

int SchnyderV	(	bool	schnyderRect,
		bool	schnyderColor,
		bool	schnyderLongestFace,
		tbrin	FirstBrin
	)

int InfOrient

(

)

int TriconTriangulate

(

)

int Tricon3orient

(

)

int MaxPlanar

(

)

int MaxPlanar

(

svector< bool > &

mark

)

int Planarity

(

tbrin

b0 = 1

)

Reimplemented from Graph.

int NewPlanarity

(

tbrin

b0 = 1

)

int CotreeCritical

(

int &

ret

)

int CotreeCritical

(

svector< bool > &

mark

)

int KCotreeCritical

(

int &

)

int Kuratowski

(

)

int Kuratowski

(

svector< bool > &

mark

)

int KKuratowski

(

)

int TestPlanar

(

)

Reimplemented from Graph.

int TestNewPlanar

(

)

int TestPlanar2

(

)

GraphContainer * Vis_a_vis_Graph

(

)

GraphContainer * CrossingEdgesGraph

(

)

tbrin NewSwapLabel	(	const tbrin &	b,
		const tedge &	ref
	)			[inline, protected]

void SwapEdge

(

const tedge &

e

)

[protected]

void SwapVertex

(

const tvertex &

v

)

[protected]

void UnlinkBrin

(

const tbrin &

b

)

[protected]

void InsertBrin	(	const tvertex &	v,
		const tbrin &	b
	)			[protected]

int ComputeSTlist

(

tbrin

st_brin

)

[protected]

void ZigZag

(

)

[protected]

---

Member Data Documentation

int ConstructedCir

int ConstructedPbrin

Prop<tbrin> cir

Prop<tbrin> acir

Prop<tbrin> pbrin

Prop1<tbrin> extbrin

Prop1<int> planarMap

int genus

---