00001 //---------------------------------------------------------------------- 00002 // The Motion Strategy Library (MSL) 00003 //---------------------------------------------------------------------- 00004 // 00005 // Copyright (c) University of Illinois and Steven M. LaValle. 00006 // All Rights Reserved. 00007 // 00008 // Permission to use, copy, and distribute this software and its 00009 // documentation is hereby granted free of charge, provided that 00010 // (1) it is not a component of a commercial product, and 00011 // (2) this notice appears in all copies of the software and 00012 // related documentation. 00013 // 00014 // The University of Illinois and the author make no representations 00015 // about the suitability or fitness of this software for any purpose. 00016 // It is provided "as is" without express or implied warranty. 00017 //---------------------------------------------------------------------- 00018 00019 00020 #ifndef MSL_GRAPH_H 00021 #define MSL_GRAPH_H 00022 00023 #include <list.h> 00024 #include <string> 00025 00026 #include "graph.h" 00027 #include "vector.h" 00028 00029 class MSLEdge; 00030 00031 class MSLVertex { 00032 private: 00033 MSLVector state; 00034 double cost; 00035 list<MSLEdge*> edges; 00036 int id; 00037 bool mark; 00038 00039 public: 00041 MSLVector State() const {return state; }; 00042 00044 inline list<MSLEdge*> const Edges() {return edges; }; 00045 00047 inline double Cost() const {return cost; }; 00048 00050 inline void SetCost(const double &x) {cost = x; }; 00051 00053 inline void SetID(const int &i) {id = i; }; 00054 00056 inline int ID() const {return id; }; 00057 00059 inline void Mark() {mark = true; }; 00060 00062 inline void Unmark() {mark = false; }; 00063 00065 inline bool IsMarked() {return mark; }; 00066 00067 MSLVertex(); 00068 MSLVertex(const MSLVector &x); 00069 ~MSLVertex(); 00070 00071 friend istream& operator>> (istream& is, MSLVertex& n) { return is; }; 00072 friend ostream& operator<< (ostream& os, const MSLVertex& n); 00073 friend istream& operator>> (istream& is, list<MSLVertex*> & nl); 00074 friend ostream& operator<< (ostream& os, const list<MSLVertex*> & nl); 00075 00076 friend class MSLEdge; 00077 friend class MSLGraph; 00078 }; 00079 00080 00081 00082 class MSLEdge { 00083 private: 00084 MSLVector input; 00085 MSLVertex* source; 00086 MSLVertex* target; 00087 double time; 00088 double cost; 00089 public: 00090 MSLEdge(); 00091 MSLEdge(MSLVertex* v1, MSLVertex* v2, 00092 const MSLVector &u, double t); 00093 MSLEdge(MSLVertex* v1, MSLVertex* v2, double t); 00094 MSLEdge(MSLVertex* v1, MSLVertex* v2); 00095 ~MSLEdge() {}; 00096 00098 inline double Time() {return time; }; 00099 00101 inline double Cost() {return cost; }; 00102 00104 inline void SetCost(const double &x) {cost = x; }; 00105 00107 inline MSLVector Input() {return input; }; 00108 00110 inline MSLVertex* Source() {return source; }; 00111 00113 inline MSLVertex* Target() {return target; }; 00114 00115 friend istream& operator>> (istream& is, MSLEdge& e) { return is; }; 00116 friend ostream& operator<< (ostream& os, const MSLEdge& e); 00117 }; 00118 00119 00121 class MSLVertexLess { 00122 public: 00123 bool operator() (MSLVertex* p, MSLVertex* q) const { 00124 return p->Cost() < q->Cost(); 00125 } 00126 }; 00127 00128 00130 class MSLVertexGreater { 00131 public: 00132 bool operator() (MSLVertex* p, MSLVertex* q) const { 00133 return p->Cost() > q->Cost(); 00134 } 00135 }; 00136 00137 00138 class MSLGraph { 00139 private: 00140 list<MSLVertex*> vertices; 00141 list<MSLEdge*> edges; 00142 int numvertices; 00143 int numedges; 00144 public: 00145 00146 MSLGraph(); 00147 ~MSLGraph(); 00148 00149 MSLVertex* AddVertex(const MSLVector &x); 00150 MSLEdge* AddEdge(MSLVertex* v1, MSLVertex* v2); 00151 MSLEdge* AddEdge(MSLVertex* v1, MSLVertex* v2, double time); 00152 MSLEdge* AddEdge(MSLVertex* v1, MSLVertex* v2, 00153 const MSLVector &u, double time); 00154 bool IsEdge(MSLVertex* v1, MSLVertex* v2); 00155 MSLVertex* FindVertex(int nid); 00156 inline list<MSLVertex*> const Vertices() { return vertices; }; 00157 inline list<MSLEdge*> const Edges() { return edges; }; 00158 inline int Size() {return numvertices+numedges;} 00159 inline int NumVertices() {return numvertices;} 00160 inline int NumEdges() {return numedges;} 00161 00162 void Clear(); 00163 00164 friend istream& operator>> (istream& is, MSLGraph& n); 00165 friend ostream& operator<< (ostream& os, const MSLGraph& n); 00166 }; 00167 00168 #endif 00169