1 // 2 // graph.h 3 // 4 5 #ifndef __GRAPH_H__ 6 #define __GRAPH_H__ 7 8 #include "wx/string.h" 9 10 #include <iostream> 11 #include <iterator> 12 #include <map> 13 #include <set> 14 #include <vector> 15 #include "matrix.h" 16 17 18 class Edge; 19 class Polynomial; 20 class Vertex; 21 22 23 class Graph 24 { 25 private: 26 std::vector<Edge *> E; 27 std::vector<Vertex *> V; 28 std::map<const wxString, wxString> tags; 29 30 std::map<const wxString, Vertex *> Vmap; 31 32 void reindex (); 33 public: 34 35 typedef std::vector<Edge *>::iterator e_iterator; 36 typedef std::vector<Vertex *>::iterator v_iterator; 37 typedef std::vector<Edge *>::const_iterator e_const_iterator; 38 typedef std::vector<Vertex *>::const_iterator v_const_iterator; 39 40 typedef std::map<const wxString, wxString>::const_iterator tag_iterator; 41 42 43 Edge *e_selected_head; 44 Vertex *v_selected_head; 45 46 Graph (); 47 Graph (const Graph &other); 48 ~Graph (); 49 50 friend std::ostream &operator<< (std::ostream &o, const Graph &g); 51 52 static Graph *load (const wxString &fname, bool &success); 53 static Graph *load (const char *fname, bool &success); 54 void save (const wxString &fname) const; 55 void save (const char *fname) const; 56 57 wxString get_tag (const char *tag) const; 58 wxString get_tag (const wxString tag) const; 59 void set_tag (const char *tag, const wxString value); 60 void set_tag (const wxString tag, const wxString value); 61 62 void clear (); 63 void add (Edge *e); 64 void add (Vertex *v); 65 void rename (Vertex *v, const wxString &new_label); 66 Vertex *find (const char *label) const; 67 Vertex *find (const wxString &label) const; 68 Edge *find (const Vertex *v1, const Vertex *v2, bool dir = false) const; 69 void remove (Edge *e); 70 void remove (Vertex *v); 71 void select (Edge *e); 72 void select (Vertex *v); 73 void unselect (Edge *e); 74 void unselect (Vertex *v); 75 void unselect_all (); 76 77 wxString unique_label (int level = 0) const; 78 bool are_adjacent (const Vertex *v1, const Vertex *v2, 79 bool dir = false) const; 80 void identify (Vertex *v1, Vertex *v2); 81 Graph *subgraph_marked () const; 82 Graph *line_graph () const; 83 Graph *flattened () const; 84 85 86 e_iterator e_begin (); 87 e_iterator e_end (); 88 v_iterator v_begin (); 89 v_iterator v_end (); 90 e_const_iterator e_begin () const; 91 e_const_iterator e_end () const; 92 v_const_iterator v_begin () const; 93 v_const_iterator v_end () const; 94 Vertex *operator[] (unsigned int i); 95 const Vertex *operator[] (unsigned int i) const; 96 97 tag_iterator tag_begin () const; 98 tag_iterator tag_end () const; 99 100 unsigned int order () const; 101 unsigned int num_edges () const; 102 103 104 //********************************************* 105 // The following methods are all in graph2.cc * 106 //********************************************* 107 108 109 private: 110 bool is_bridge (Edge *e) const; 111 public: 112 bool is_undirected () const; 113 bool is_connected (bool dir = false, Vertex *start = 0) const; 114 bool is_strongly_connected () const; 115 void eulericity (bool &euler, bool &semi, wxString &tour) const; 116 void mark_shortest_path (Vertex *v1, Vertex *v2); 117 int diameter (bool sel = false); 118 int radius (bool sel = false); 119 Matrix adjacency_matrix () const; 120 121 void bfs (Vertex *v, wxString &s); 122 void dfs (Vertex *v, wxString &s); 123 124 void minimum_spanning_tree (std::set<Edge *> &result) const; 125 126 int ford_fulkerson (Vertex *src, Vertex *dest); 127 128 int chromatic_number () const; 129 Polynomial chromatic_polynomial () const; 130 bool try_colouring (unsigned int colours); 131 132 private: 133 void traversal_visit (Vertex *v, wxString &s, int &cnt); 134 int dfs_do (Vertex *v, wxString &s, int cnt); 135 bool check_colouring (unsigned int colours) const; 136 137 // Destructive! 138 Polynomial chromatic_poly (double startP, double endP); 139 }; 140 141 142 #endif // __GRAPH_H__ 143