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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
/**
* @file: edge.h
* Edge class definition
*/
/*
* Graph library, internal representation of graphs in ShowGraph tool.
* Copyright (c) 2009, Boris Shurygin
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
*
* 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.
*
* 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.
*
* 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.
*/
#ifndef EDGE_H
#define EDGE_H
/**
* Edge lists identificators
* @ingroup GraphBase
*/
enum EdgeListType
{
EDGE_LIST_PREDS,
EDGE_LIST_SUCCS,
EDGE_LIST_GRAPH,
EDGE_LISTS_NUM
};
/**
* @class Edge
* @brief Representation of graph edge
* @ingroup GraphBase
*
* @par
* Edge class implements basic concept of graph edge. Every edge has two adjacent nodes.
* Use pred() and succ() routines to get them. Edge is a member of 3 lists: edge list in graph,
* pred list in succ node and succ list in pred node. To traverse these lists use nextEdge(),
* nextPred() and nextSucc() routines. Also for debug purposes all edges in a graph
* have unique id, which can be usefull for printing to console or setting breakpoint conditions.
*
* @par
* An edge can be @ref Marked "marked" and @ref Numbered "numbered". @ref Mark "Markers" and
* @ref Nums "numerations" are managed by @ref Graph "graph". Note that @ref Node "nodes" can be marked with the
* same marker or numbered in the same numeration.
* Also for debug purposes all nodes in a graph
* have unique id, which can be usefull for printing to console or setting breakpoint conditions.
*
* @par
* Edges reside in memory pool that is controlled by Graph. Operator new can't be called
* directly. Edges can be only created by calling Graph::newEdge().
*
* @par
* Every edge have associated QDomElement for XML export support. The updateElement() routine should be called before
* export to get element in sync with edge's properties.
*
* @sa Graph
* @sa Node
* @sa Mark
* @sa Nums
*/
class Edge:
public MListIface< Edge, // List item
MListItem< EDGE_LISTS_NUM>, // base class: pure multi-list item
EDGE_LISTS_NUM >, // Lists number
public Marked,
public Numbered,
public PoolObj
{
public:
/** Get edge's unique ID */
inline GraphUid id() const;
/** Get edge's graph */
inline Graph * graph() const;
/**
* Destructor.
* Delete edge from list in graph.
* Deletion from node lists MUST be performed manually.
*/
virtual ~Edge();
/**
* Connect edge to a node in specified direction.
* Note that node treats this edge in opposite direction. I.e. an edge that has node in
* GRAPH_DIR_UP is treated as edge in GRAPH_DIR_DOWN directions inside that node
*/
inline void setNode( Node *n, GraphDir dir);
/** Connect edge with given node as a predecessor */
inline void setPred( Node *n);
/** Connect edge with given node as a successor */
inline void setSucc( Node *n);
/** Get node in specified direction */
inline Node *node( GraphDir dir) const;
inline Node *pred() const;/**< Get predecessor node of edge */
inline Node *succ() const;/**< Get successor node of edge */
/** Return next edge of the graph */
inline Edge* nextEdge();
/** Return next edge of the same node in given direction */
inline Edge* nextEdgeInDir( GraphDir dir);
inline Edge* nextSucc();/**< Next successor */
inline Edge* nextPred();/**< Next predecessor */
/** Print edge in dot fomat to stdout */
virtual void debugPrint();
/** Return corresponding document element */
inline QDomElement elem() const;
/** Set document element */
inline void setElement( QDomElement elem);
/** Update DOM element */
virtual void updateElement();
/** Read properties from XML */
virtual void readFromElement( QDomElement elem);
/**
* Insert a node on this edge
*
* Creates a node on edge and a new edge from new node to former successor of original edge.
* Original edge goes to new node.
* Return new node.
*/
virtual Node *insertNode();
private:
/** Representation in document */
QDomElement element;
/** Graph part */
GraphUid uid; //Unique ID
Graph * graph_p; //Graph
/** Nodes */
Node *nodes[ GRAPH_DIRS_NUM]; //Adjacent nodes
/** Node checking routine */
bool checkNodes( Node* _pred, Node* _succ);
protected:
/** Graph should have access to Edge's members */
friend class Graph;
/** Node should have access to Edge's members */
friend class Node;
/** Constructors are made private, only nodes and graph can create edges */
Edge( Graph *_graph_p, GraphUid _id, Node *_pred, Node* _succ):
uid(_id), graph_p(_graph_p)
{
GRAPH_ASSERTD( checkNodes( _pred, _succ),
"Predecessor and sucessor used in edge construction belong to different graphs");
setPred( _pred);
setSucc( _succ);
}
/**
* Detach edge from a node.
* Made private as it is low-level routine needed for implementation of edge-node relationship
*/
inline void detachFromNode( GraphDir dir);
/**
* Remove myself from graph's list of edges
*/
inline void detachFromGraph()
{
detach( EDGE_LIST_GRAPH);
}
};
#endif
|
