2 Qanava - GraphT drawing library for QT
3 Copyright (C) 2006 Benoit AUTHEMAN
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 //-----------------------------------------------------------------------------
21 // This file is a part of the Qanava software.
24 // \author Benoit Autheman (benoit@libqanava.org)
25 // \date 2004 February 15
26 //-----------------------------------------------------------------------------
34 #include "./qanEdge.h"
35 #include "./qanNode.h"
36 #include "./qanGraphScene.h"
42 #include <QStandardItemModel>
45 //-----------------------------------------------------------------------------
46 namespace qan
{ // ::qan
48 //! Model a standard weighted directed graph using a node-list, edge-list representation.
52 template < class M
, class O
>
57 /*! \name GraphT Constructor/Destructor *///------------------------
61 //! GraphT default constructor.
64 //! GraphT default destructor. All registered nodes and edges are invalid after graph destruction.
67 M
& getM( ) { return _m
; }
68 const M
& getM( ) const { return _m
; }
70 O
& getO( ) { return _o
; }
71 const O
& getO( ) const { return _o
; }
75 //! GraphT empty private copy constructor.
76 GraphT( const GraphT
& graph
);
81 //-----------------------------------------------------------------
85 /*! \name Edge/Node Management *///--------------------------------
89 //! Clear the graph from all its edges and nodes.
92 //! Set a node object unique key.
93 void setNodeObject( Node
& node
, void* object
);
95 void modifyNode( Node
& node
, const QString
& name
, int type
= -1, void* object
= 0 );
97 void modifyEdge( Edge
& edge
, Node
& a
, Node
& b
, float weight
= 1.f
);
99 typedef QList
< GraphT
< M
, O
>* > List
;
101 //-----------------------------------------------------------------
104 /*! \name Edge/Node Management *///--------------------------------
108 void addNode( Node
* node
, void* object
= 0 );
110 Node
* addNode( const QString
& name
, int type
= -1, void* object
= 0 );
112 void insertNode( Node
* node
, void* object
= 0 );
114 Node
* insertNode( const QString
& name
, int type
= -1, void* object
= 0 );
116 void removeNode( Node
& node
);
119 void addEdge( Edge
* edge
);
121 Edge
* addEdge( Node
& a
, Node
& b
, float weight
= 1.f
);
123 void insertEdge( Edge
* edge
);
125 Edge
* insertEdge( Node
& a
, Node
& b
, float weight
= 1.f
);
127 //! Insert a new leaf node in this graph using an existing node as the super node, and return an edge from the super node to node.
129 \param node Node that must be inserted in the graph (graph will take ownership of the node).
130 \param superNode Already existing node that will be used as a super node, and the source of the returned edge.
132 Edge
* insertNode( Node
* node
, Node
& superNode
);
134 void removeEdge( Edge
& edge
);
136 bool hasEdge( Node
& a
, Node
& b
) const;
138 //! Take care of updating models when topology has been initialized using create* methods.
139 /*! This method is usualy usefull before connecting a graph to a view when it has been initialized
140 whitout using the insert methods who are automatically taking care of updating models. */
141 void updateModels( );
145 //! List of nodes currently registered in this graph.
148 //! Set of nodes currently registered in this graph (used for fast node search).
151 //! Map an object to its associed node.
152 typedef QMap
< void*, Node
* > ObjectNodeMap
;
155 typedef QMap
< Node
*, void* > NodeObjectMap
;
157 //! Map an object to its associed graph node.
158 ObjectNodeMap _objectNodeMap
;
161 NodeObjectMap _nodeObjectMap
;
163 //! List of edges currently connecting the registered nodes in this graph.
166 //-----------------------------------------------------------------
171 /*! \name GraphT Consultation Management *///-----------------------
175 //! Get graph node count.
176 unsigned int getNodeCount( ) const { return _nodes
.size( ); }
178 //! Get graph's nodes list (list must be used read-only).
179 Node::List
& getNodes( ) { return _nodes
; }
181 //! Get graph's edges list (list must be used read-only).
182 Edge::List
& getEdges( ) { return _edges
; }
184 //! Collect a set of unique node registered in this graph.
185 void collectNodes( Node::Set
& nodes
) const;
187 //-----------------------------------------------------------------
191 /*! \name Search Management *///-----------------------------------
195 //! Find a node of a given label in the graph.
196 Node
* findNode( const QString
& label
);
198 //! Find a node given its associed key memory object (if such key has been specified during node adjunction).
199 Node
* findNode( void* object
);
201 //! Find the nth registered node in this graph (For internal use only).
202 /*! This method should only be used in repositories just after node loading when their initial order has not been altered. */
203 Node
* findNode( int node
);
205 //! Get the index where a node is currently registered in this graph.
206 /*! This method should only be used in repositories just after node loading when their initial order has not been altered. */
207 int findNode( const Node
& node
) const;
209 //! Find a node object for a specific node (if such an object has been specified during node adjunction).
210 void* findObject( Node
* node
);
212 //! Search for a specific node in this graph and return true if the node is found.
213 bool hasNode( Node
* node
) const;
215 //-----------------------------------------------------------------
219 /*! \name Root Node Management *///--------------------------------
223 //! Add a root to this graph (ie a node that doesn't have super nodes.)
224 /*! \param node must be already registered in the graph. */
225 void addRootNode( Node
& node
) { _rootNodes
<< &node
; _rootNodesSet
<< &node
; }
227 //! Remove a node from the root node list
228 void removeRootNode( Node
& node
) { _rootNodes
.removeAll( &node
); _rootNodesSet
.remove( &node
); }
230 //! Get the currently registered root node for this graph.
231 Node::List
& getRootNodes( ) { return _rootNodes
; }
233 //! Get the currently registered root node for this graph.
234 Node::Set
& getRootNodesSet( ) { return _rootNodesSet
; }
236 //! Generate the root set by automatically looking for nodes with no super nodes (O(n), n numbers of nodes).
237 void generateRootNodes( );
239 //! Test if a given node is a graph root node.
240 bool isRootNode( const Node
& node
) const;
244 //! Ordered root nodes for this graph's subgraphs.
245 Node::List _rootNodes
;
247 //! Root nodes of graph's subgraphs (used only to test root node existence).
248 Node::Set _rootNodesSet
;
250 //-----------------------------------------------------------------
253 /*! \name Node Attributes Management *///--------------------------
257 template < typename T
>
258 void addAttribute( const QString
& name
, T t
)
260 _attributesNames
.push_back( name
);
261 for ( Node::List::iterator nodeIter
= getNodes( ).begin( ); nodeIter
!= getNodes( ).end( ); nodeIter
++ )
262 ( *nodeIter
)->addAttribute
< T
>( t
);
265 QString
getAttributeName( int role
)
267 return ( role
< _attributesNames
.size( ) ? _attributesNames
[ role
] : QString( "" ) );
270 template < typename T
>
271 void setAttribute( Node
* node
, const QString
& name
, T
& value
)
273 int role
= hasAttribute( name
);
275 setAttribute
< T
>( node
, role
, value
);
278 template < typename T
>
279 void setAttribute( Node
* node
, unsigned int role
, T
& value
)
281 node
->setAttribute
< T
>( role
, value
);
284 int hasAttribute( const QString
& name
) const
287 Strings::const_iterator nameIter
= _attributesNames
.begin( );
288 for ( ; nameIter
!= _attributesNames
.end( ); nameIter
++, r
++ )
289 if ( *nameIter
== name
)
294 unsigned int getAttributesCount( ) const { return _attributesNames
.size( ); }
298 void initNodeAttributes( Node
& node
)
300 node
.initAttributes( _attributesNames
.size( ) );
303 typedef QList
< QString
> Strings
;
305 Strings _attributesNames
;
307 //-----------------------------------------------------------------
310 typedef GraphT
< GraphScene
, GraphModel
> Graph
;
313 #include "./qanGraph.hpp"
314 //-----------------------------------------------------------------------------