1 /**
2 * @file: agraph.h
3 * Abstract Graph for testing of graph's properties and usage model.
4 *
5 * @defgroup AGr Test Graph
6 *
7 * @ingroup GraphBase
8 * AGraph, ANode and AEdge classes present mimnimal code
9 * that you need to write to employ Graph Library functionality.
10 * AGraph classes differ from base in only one member of ( int) type
11 */
12 /*
13 * Copyright (c) 2009, Boris Shurygin
14 * All rights reserved.
15 *
16 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
17 *
18 * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
19 *
20 * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
21 *
22 * 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26 #ifndef AGRAPH_H
27 #define AGRAPH_H
28
29 /* Predeclarations */
30 class ANode;
31 class AEdge;
32 class AGraph;
33
34 /**
35 * Abstract node
36 *
37 * @ingroup AGr
38 */
39 class ANode: public Node
40 {
41 int dummy;
42 /** We can't create nodes separately, do it through newNode method of graph */
43 ANode( AGraph *graph_p, int _id);
44 friend class AGraph;
45 public:
46 /** Get next graph's node */
nextNode()47 inline ANode* nextNode()
48 {
49 return static_cast< ANode*>( Node::nextNode());
50 }
51 /** Get prev graph's node */
prevNode()52 inline ANode* prevNode()
53 {
54 return static_cast< ANode*>( Node::prevNode());
55 }
56 /** Edge connection reimplementation */
57 inline void AddEdgeInDir( AEdge *edge, GraphDir dir);
58 /** Add predecessor */
59 inline void AddPred( AEdge *edge);
60 /** Add successor */
61 inline void AddSucc( AEdge *edge);
62 /** Get first edge in given direction */
63 inline AEdge* firstEdgeInDir( GraphDir dir);
64 /** Get first successor */
65 inline AEdge* firstSucc();
66 /** Get first predecessor */
67 inline AEdge* firstPred();
68
69 };
70
71 /**
72 * Abstract edge
73 *
74 * @ingroup AGr
75 */
76 class AEdge: public Edge
77 {
78 //int dummy;
79
80 /** Constructors are made private, only nodes and graph can create edges */
81 AEdge( AGraph *graph_p, int _id, ANode *_pred, ANode* _succ);
82
83 friend class AGraph;
84 friend class ANode;
85 public:
86 /** Get node in given direction */
node(GraphDir dir)87 inline ANode *node( GraphDir dir) const
88 {
89 return static_cast< ANode *>( Edge::node( dir));
90 }
91 /** Get predecessor */
pred()92 inline ANode *pred() const
93 {
94 return node( GRAPH_DIR_UP);
95 }
96 /** Get successor */
succ()97 inline ANode *succ() const
98 {
99 return node( GRAPH_DIR_DOWN);
100 }
101 /** insert node on this edge */
insertNode()102 virtual ANode *insertNode()
103 {
104 return static_cast< ANode *>( Edge::insertNode());
105 }
106 /** Next edge in graph's list */
nextEdge()107 inline AEdge* nextEdge()
108 {
109 return static_cast< AEdge *>( Edge::nextEdge());
110 }
111 /** Next edge in give direction */
nextEdgeInDir(GraphDir dir)112 inline AEdge* nextEdgeInDir( GraphDir dir)
113 {
114 return static_cast< AEdge *>( Edge::nextEdgeInDir( dir));
115 }
116 /** Next successor */
nextSucc()117 inline AEdge* nextSucc()
118 {
119 return nextEdgeInDir( GRAPH_DIR_DOWN);
120 }
121 /** Next predecessor */
nextPred()122 inline AEdge* nextPred()
123 {
124 return nextEdgeInDir( GRAPH_DIR_UP);
125 }
126 };
127
128 /**
129 * Testing-purpose graph
130 *
131 * @ingroup AGr
132 */
133 class AGraph: public Graph
134 {
135 int dummy; //Dummy class member
136
137
138 /** Node creation overload */
139 Node * createNode( int _id);
140 /** Edge creation overload */
141 Edge * createEdge( int _id, Node *_pred, Node* _succ);
142
143 public:
144
145 /** New graphical node */
newNode()146 ANode* newNode()
147 {
148 return static_cast< ANode*>( Graph::newNode());
149 }
150
151 /** New graphical edge */
newEdge(ANode * pred,ANode * succ)152 AEdge* newEdge( ANode* pred, ANode* succ)
153 {
154 return static_cast< AEdge *>( Graph::newEdge( pred, succ));
155 }
156
157 /** Get graph's first edge */
firstEdge()158 inline AEdge* firstEdge()
159 {
160 return static_cast< AEdge *>( Graph::firstEdge());
161 }
162 /** Get graph's first node */
firstNode()163 inline ANode* firstNode()
164 {
165 return static_cast< ANode *>( Graph::firstNode());
166 }
167 /** Pools' creation routine */
createPools()168 void createPools()
169 {
170 node_pool = new FixedPool< ANode>();
171 edge_pool = new FixedPool< AEdge>();
172 }
173 /** Constructor */
AGraph(bool create_pools)174 AGraph( bool create_pools): Graph( false)
175 {
176 if ( create_pools)
177 createPools();
178 }
179 };
180
181 /** Node constructor */
ANode(AGraph * graph_p,int _id)182 inline ANode::ANode( AGraph *graph_p, int _id):
183 Node( graph_p, _id)
184 {
185
186 }
187
188 /** Edge constructor */
AEdge(AGraph * graph_p,int _id,ANode * _pred,ANode * _succ)189 inline AEdge::AEdge( AGraph *graph_p, int _id, ANode *_pred, ANode* _succ):
190 Edge( graph_p, _id, _pred, _succ)
191 {
192
193 }
194
195 /** Node creation overload */
createNode(int _id)196 inline Node * AGraph::createNode( int _id)
197 {
198 return new ( nodePool()) ANode( this, _id);
199 }
200 /** Edge creation overload */
createEdge(int _id,Node * _pred,Node * _succ)201 inline Edge * AGraph::createEdge( int _id, Node *_pred, Node* _succ)
202 {
203 return new ( edgePool()) AEdge( this, _id, static_cast<ANode*>( _pred), static_cast< ANode *>(_succ));
204 }
205
206 /** Get first edge in given direction */
207 inline AEdge*
firstEdgeInDir(GraphDir dir)208 ANode::firstEdgeInDir( GraphDir dir)
209 {
210 return static_cast< AEdge*>( Node::firstEdgeInDir( dir));
211 }
212 /** Get first successor */
213 inline AEdge*
firstSucc()214 ANode::firstSucc()
215 {
216 return firstEdgeInDir( GRAPH_DIR_DOWN);
217 }
218 /** Get first predecessor */
219 inline AEdge*
firstPred()220 ANode::firstPred()
221 {
222 return firstEdgeInDir( GRAPH_DIR_UP);
223 }
224
225 /** Edge connection reimplementation */
226 inline void
AddEdgeInDir(AEdge * edge,GraphDir dir)227 ANode::AddEdgeInDir( AEdge *edge, GraphDir dir)
228 {
229 Node::AddEdgeInDir( edge, dir);
230 }
231 /** Add predecessor */
232 inline void
AddPred(AEdge * edge)233 ANode::AddPred( AEdge *edge)
234 {
235 AddEdgeInDir( edge, GRAPH_DIR_UP);
236 }
237 /** Add successor */
238 inline void
AddSucc(AEdge * edge)239 ANode::AddSucc( AEdge *edge)
240 {
241 AddEdgeInDir( edge, GRAPH_DIR_DOWN);
242 }
243 #endif
244