PIGALE 1.3.9 Documentation (original) (raw)

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

• Main Page

• Modules

• Namespaces

• Classes

• Files

• Related Pages

• Alphabetical List

• Class List

• Class Hierarchy

• Class Members

TopologicalGraph Class Reference

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

Member Function Documentation

| void keeponly | ( | | ) | [inline] | | ------------- | - | | - | ---------- |

| void StrictReset | ( | | ) | [inline] | | ---------------- | - | | - | ---------- |

| const Graph& me | ( | | ) | const [inline] | | ---------------------------------- | - | | - | ---------------- |

| Graph* SmallDup | ( | | ) | const | | ----------------------------------- | - | | - | ----- |

| void SwitchOrientations | ( | | ) | | ----------------------- | - | | - |

| void RestoreOrientation | ( | | ) | | ----------------------- | - | | - |

| int RemoveIsolatedVertices | ( | | ) | | -------------------------- | - | | - |

| int NumberOfConnectedComponents | ( | | ) | [inline] | | ------------------------------- | - | | - | ---------- |

| int ColorConnectedComponents | ( | | ) | | ---------------------------- | - | | - |

| bool CheckBiconnected | ( | | ) | | --------------------- | - | | - |

Reimplemented from Graph.

| bool CheckTriconnected | ( | | ) | | ---------------------- | - | | - |

| bool CheckFourconnected | ( | | ) | | ----------------------- | - | | - |

| bool CheckSubdivTriconnected | ( | | ) | | ---------------------------- | - | | - |

| bool CheckSerieParallel | ( | | ) | | ----------------------- | - | | - |

| int MakeConnectedVertex | ( | | ) | | ----------------------- | - | | - |

| bool CheckPlanar | ( | | ) | [inline] | | ---------------- | - | | - | ---------- |

| int ZigZagTriangulate | ( | | ) | | --------------------- | - | | - |

| int VertexQuadrangulate | ( | | ) | | ----------------------- | - | | - |

| int VertexTriangulate | ( | | ) | | --------------------- | - | | - |

| int NpBiconnectVertex | ( | | ) | | --------------------- | - | | - |

| int TriconTriangulate | ( | | ) | | --------------------- | - | | - |

Reimplemented from Graph.

| int KCotreeCritical | ( | int & | | ) | | ------------------- | - | ----- | | - |

Reimplemented from Graph.

| void ZigZag | ( | | ) | [protected] | | ----------- | - | | - | ------------- |

Member Data Documentation

Generated on Thu Jan 31 16:52:13 2008 for Pigale by 1.5.4