/usr/include/libwildmagic/Wm5PlanarGraph.h is in libwildmagic-dev 5.13-1+b2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | // Geometric Tools, LLC
// Copyright (c) 1998-2014
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt
// http://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
//
// File Version: 5.0.0 (2010/01/01)
#ifndef WM5PLANARGRAPH_H
#define WM5PLANARGRAPH_H
#include "Wm5MathematicsLIB.h"
#include "Wm5EdgeKey.h"
#include "Wm5Memory.h"
// The Point2 template class must represent a 2-tuple, each component of some
// scalar type Numeric. Point2 must define the following member functions.
// Point2::Point2 ();
// Point2::(Numeric, Numeric);
// Point2::~Point2 ();
// Point2& Point2::operator= (const Point2&);
// Point2 Point2::operator- (const Point2&) const;
// Numeric Point2::operator[] (int i) const;
namespace Wm5
{
template <typename Point2>
class PlanarGraph
{
public:
PlanarGraph ();
virtual ~PlanarGraph ();
class Vertex
{
public:
Vertex (const Point2& position, int index);
~Vertex ();
void Insert (Vertex* adjacent);
void Remove (Vertex* adjacent);
// The planar position for the vertex.
Point2 Position;
// A unique identifier for the vertex.
int Index;
// The adjacent vertices.
std::vector<Vertex*> Adjacent;
};
typedef std::map<int,Vertex*> Vertices;
typedef std::map<EdgeKey,bool> Edges;
const Vertices& GetVertices () const;
const Vertex* GetVertex (int iIndex) const;
bool InsertVertex (const Point2& position, int iIndex);
bool RemoveVertex (int iIndex);
const Edges& GetEdges () const;
bool InsertEdge (int iIndex0, int iIndex1);
bool RemoveEdge (int iIndex0, int iIndex1);
// Traverse the graph and extract the isolated vertices, filaments, and
// minimal cycles. See MinimalCycleBasis.pdf for the details.
enum PrimitiveType
{
PT_ISOLATED_VERTEX,
PT_FILAMENT,
PT_MINIMAL_CYCLE
};
class Primitive
{
public:
Primitive (PrimitiveType type);
PrimitiveType Type;
std::vector<std::pair<Point2,int> > Sequence;
};
// The extraction of primitives destroys the graph. If you need the
// graph to persist, make a copy of it and call this function from the
// copy.
void ExtractPrimitives (std::vector<Primitive*>& primitives);
protected:
// For sorting of the heap of vertex pointers.
class VertexPtr
{
public:
VertexPtr (Vertex* vertex);
inline operator Vertex* ()
{
return mVertex;
}
// Lexicographical ordering of vertices. The query (x0,y0) < (x1,y1)
// is true iff ((x0 < x1) || ((x0 == x1) && (y0 < y1))).
bool operator< (const VertexPtr& vertexPtr) const;
private:
Vertex* mVertex;
};
void SetCycleEdge (int index0, int index1, bool cycleEdge);
bool GetCycleEdge (int index0, int index1) const;
void ExtractIsolatedVertex (Vertex* V0, std::set<VertexPtr>& heap,
std::vector<Primitive*>& primitives);
void ExtractFilament (Vertex* V0, Vertex* V1,
std::set<VertexPtr>& heap, std::vector<Primitive*>& primitives);
void ExtractPrimitive (Vertex* V0, std::set<VertexPtr>& heap,
std::vector<Primitive*>& primitives);
Vertex* GetClockwiseMost (Vertex* VPrev, Vertex* VCurr);
Vertex* GetCounterclockwiseMost (Vertex* VPrev, Vertex* VCurr);
Vertices mVertices;
Edges mEdges;
};
#include "Wm5PlanarGraph.inl"
}
#endif
|