34 ///using good source browsers like e.g. \c emacs. |
45 ///using good source browsers like e.g. \c emacs. |
35 /// |
46 /// |
36 ///For example |
47 ///For example |
37 ///\code check(0==1,"This is obviously false.");\endcode will |
48 ///\code check(0==1,"This is obviously false.");\endcode will |
38 ///print this (and then exits). |
49 ///print this (and then exits). |
39 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim |
50 ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim |
40 /// |
51 /// |
41 ///\todo It should be in \c error.h |
52 ///\todo It should be in \c error.h |
42 #define check(rc, msg) \ |
53 #define check(rc, msg) \ |
43 if(!(rc)) { \ |
54 if(!(rc)) { \ |
44 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \ |
55 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \ |
45 abort(); \ |
56 abort(); \ |
46 } else { } \ |
57 } else { } \ |
47 |
58 |
|
59 ///Structure returned by \ref addPetersen(). |
|
60 |
|
61 ///Structure returned by \ref addPetersen(). |
|
62 /// |
|
63 template<class Digraph> struct PetStruct |
|
64 { |
|
65 ///Vector containing the outer nodes. |
|
66 std::vector<typename Digraph::Node> outer; |
|
67 ///Vector containing the inner nodes. |
|
68 std::vector<typename Digraph::Node> inner; |
|
69 ///Vector containing the arcs of the inner circle. |
|
70 std::vector<typename Digraph::Arc> incir; |
|
71 ///Vector containing the arcs of the outer circle. |
|
72 std::vector<typename Digraph::Arc> outcir; |
|
73 ///Vector containing the chord arcs. |
|
74 std::vector<typename Digraph::Arc> chords; |
|
75 }; |
|
76 |
|
77 |
|
78 |
|
79 ///Adds a Petersen digraph to \c G. |
|
80 |
|
81 ///Adds a Petersen digraph to \c G. |
|
82 ///\return The nodes and arcs of the generated digraph. |
|
83 |
|
84 template<typename Digraph> |
|
85 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) |
|
86 { |
|
87 PetStruct<Digraph> n; |
|
88 |
|
89 for(int i=0;i<num;i++) { |
|
90 n.outer.push_back(G.addNode()); |
|
91 n.inner.push_back(G.addNode()); |
|
92 } |
|
93 |
|
94 for(int i=0;i<num;i++) { |
|
95 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); |
|
96 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); |
|
97 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); |
|
98 } |
|
99 return n; |
|
100 } |
|
101 |
|
102 /// \brief Adds to the digraph the reverse pair of all arcs. |
|
103 /// |
|
104 /// Adds to the digraph the reverse pair of all arcs. |
|
105 /// |
|
106 template<class Digraph> void bidirDigraph(Digraph &G) |
|
107 { |
|
108 typedef typename Digraph::Arc Arc; |
|
109 typedef typename Digraph::ArcIt ArcIt; |
|
110 |
|
111 std::vector<Arc> ee; |
|
112 |
|
113 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); |
|
114 |
|
115 for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++) |
|
116 G.addArc(G.target(*p),G.source(*p)); |
|
117 } |
|
118 |
|
119 |
|
120 /// \brief Checks the bidirectioned Petersen digraph. |
|
121 /// |
|
122 /// Checks the bidirectioned Petersen digraph. |
|
123 /// |
|
124 template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5) |
|
125 { |
|
126 typedef typename Digraph::Node Node; |
|
127 |
|
128 typedef typename Digraph::ArcIt ArcIt; |
|
129 typedef typename Digraph::NodeIt NodeIt; |
|
130 |
|
131 checkDigraphNodeList(G, 2 * num); |
|
132 checkDigraphArcList(G, 6 * num); |
|
133 |
|
134 for(NodeIt n(G);n!=INVALID;++n) { |
|
135 checkDigraphInArcList(G, n, 3); |
|
136 checkDigraphOutArcList(G, n, 3); |
|
137 } |
|
138 } |
|
139 |
|
140 ///Structure returned by \ref addUPetersen(). |
|
141 |
|
142 ///Structure returned by \ref addUPetersen(). |
|
143 /// |
|
144 template<class Digraph> struct UPetStruct |
|
145 { |
|
146 ///Vector containing the outer nodes. |
|
147 std::vector<typename Digraph::Node> outer; |
|
148 ///Vector containing the inner nodes. |
|
149 std::vector<typename Digraph::Node> inner; |
|
150 ///Vector containing the arcs of the inner circle. |
|
151 std::vector<typename Digraph::Edge> incir; |
|
152 ///Vector containing the arcs of the outer circle. |
|
153 std::vector<typename Digraph::Edge> outcir; |
|
154 ///Vector containing the chord arcs. |
|
155 std::vector<typename Digraph::Edge> chords; |
|
156 }; |
|
157 |
|
158 ///Adds a Petersen digraph to the undirected \c G. |
|
159 |
|
160 ///Adds a Petersen digraph to the undirected \c G. |
|
161 ///\return The nodes and arcs of the generated digraph. |
|
162 |
|
163 template<typename Digraph> |
|
164 UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5) |
|
165 { |
|
166 UPetStruct<Digraph> n; |
|
167 |
|
168 for(int i=0;i<num;i++) { |
|
169 n.outer.push_back(G.addNode()); |
|
170 n.inner.push_back(G.addNode()); |
|
171 } |
|
172 |
|
173 for(int i=0;i<num;i++) { |
|
174 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); |
|
175 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5])); |
|
176 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5])); |
|
177 } |
|
178 return n; |
|
179 } |
|
180 |
48 #endif |
181 #endif |