src/qanGraph.h

   1 /*
   2 Qanava - GraphT drawing library for QT
   3 Copyright (C) 2006 Benoit AUTHEMAN
   4
   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.
   9
  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.
  14
  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
  18 */
  19
  20 //-----------------------------------------------------------------------------
  21 // This file is a part of the Qanava software.
  22 //
  23 // \file        laGraph.h
  24 // \author      Benoit Autheman (benoit@libqanava.org)
  25 // \date        2004 February 15
  26 //-----------------------------------------------------------------------------
  27
  28
  29 #ifndef laGraph_h
  30 #define laGraph_h
  31
  32
  33 // Qanava headers
  34 #include "./qanEdge.h"
  35 #include "./qanNode.h"
  36 #include "./qanGraphScene.h"
  37
  38
  39 // QT headers
  40 #include <QMap>
  41 #include <QList>
  42 #include <QStandardItemModel>
  43
  44
  45 //-----------------------------------------------------------------------------
  46 namespace qan { // ::qan
  47
  48                 //! Model a standard weighted directed graph using a node-list, edge-list representation.
  49                 /*!
  50                         \nosubgrouping
  51                 */
  52                 template < class M, class O >
  53                 class GraphT
  54                 {
  55                 public:
  56
  57                         /*! \name GraphT Constructor/Destructor *///------------------------
  58                         //@{
  59                 public:
  60
  61                         //! GraphT default constructor.
  62                         GraphT( );
  63
  64                         //! GraphT default destructor. All registered nodes and edges are invalid after graph destruction.
  65                         ~GraphT( );
  66
  67                         M&                      getM( ) { return _m; }
  68                         const M&        getM( ) const { return _m; }
  69
  70                         O&                      getO( ) { return _o; }
  71                         const O&        getO( ) const { return _o; }
  72
  73                 private:
  74
  75                         //! GraphT empty private copy constructor.
  76                         GraphT( const GraphT& graph );
  77
  78                         M       _m;
  79                         O       _o;
  80                         //@}
  81                         //-----------------------------------------------------------------
  82
  83
  84
  85                         /*! \name Edge/Node Management *///--------------------------------
  86                         //@{
  87                 public:
  88
  89                         //! Clear the graph from all its edges and nodes.
  90                         void                    clear( );
  91
  92                         //! Set a node object unique key.
  93                         void                    setNodeObject( Node& node, void* object );
  94
  95                         void                    modifyNode( Node& node, const QString& name, int type = -1, void* object = 0 );
  96
  97                         void                    modifyEdge( Edge& edge, Node& a, Node& b, float weight = 1.f );
  98
  99                         typedef                 QList< GraphT< M, O >* >        List;
 100                         //@}
 101                         //-----------------------------------------------------------------
 102
 103
 104                         /*! \name Edge/Node Management *///--------------------------------
 105                         //@{
 106                 public:
 107
 108                         void                    addNode( Node* node, void* object = 0 );
 109
 110                         Node*                   addNode( const QString& name, int type = -1, void* object = 0 );
 111
 112                         void                    insertNode( Node* node, void* object = 0 );
 113
 114                         Node*                   insertNode( const QString& name, int type = -1, void* object = 0 );
 115
 116                         void                    removeNode( Node& node );
 117
 118
 119                         void                    addEdge( Edge* edge );
 120
 121                         Edge*                   addEdge( Node& a, Node& b, float weight = 1.f );
 122
 123                         void                    insertEdge( Edge* edge );
 124
 125                         Edge*                   insertEdge( Node& a, Node& b, float weight = 1.f );
 126
 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.
 128                         /*!
 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.
 131                          */
 132                         Edge*                   insertNode( Node* node, Node& superNode );
 133
 134                         void                    removeEdge( Edge& edge );
 135
 136                         bool                    hasEdge( Node& a, Node& b ) const;
 137
 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( );
 142
 143                 private:
 144
 145                         //! List of nodes currently registered in this graph.
 146                         Node::List              _nodes;
 147
 148                         //! Set of nodes currently registered in this graph (used for fast node search).
 149                         Node::Set               _nodesSet;
 150
 151                         //! Map an object to its associed node.
 152                         typedef QMap< void*, Node* >    ObjectNodeMap;
 153
 154                         //! .
 155                         typedef QMap< Node*, void* >    NodeObjectMap;
 156
 157                         //! Map an object to its associed graph node.
 158                         ObjectNodeMap   _objectNodeMap;
 159
 160                         //! .
 161                         NodeObjectMap   _nodeObjectMap;
 162
 163                         //! List of edges currently connecting the registered nodes in this graph.
 164                         Edge::List              _edges;
 165                         //@}
 166                         //-----------------------------------------------------------------
 167
 168
 169
 170
 171                         /*! \name GraphT Consultation Management *///-----------------------
 172                         //@{
 173                 public:
 174
 175                         //! Get graph node count.
 176                         unsigned int    getNodeCount( ) const { return _nodes.size( ); }
 177
 178                         //! Get graph's nodes list (list must be used read-only).
 179                         Node::List&             getNodes( ) { return _nodes; }
 180
 181                         //! Get graph's edges list (list must be used read-only).
 182                         Edge::List&             getEdges( ) { return _edges; }
 183
 184                         //! Collect a set of unique node registered in this graph.
 185                         void                    collectNodes( Node::Set& nodes ) const;
 186                         //@}
 187                         //-----------------------------------------------------------------
 188
 189
 190
 191                         /*! \name Search Management *///-----------------------------------
 192                         //@{
 193                 public:
 194
 195                         //! Find a node of a given label in the graph.
 196                         Node*                   findNode( const QString& label );
 197
 198                         //! Find a node given its associed key memory object (if such key has been specified during node adjunction).
 199                         Node*                   findNode( void* object );
 200
 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 );
 204
 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;
 208
 209                         //! Find a node object for a specific node (if such an object has been specified during node adjunction).
 210                         void*                   findObject( Node* node );
 211
 212                         //! Search for a specific node in this graph and return true if the node is found.
 213                         bool                    hasNode( Node* node ) const;
 214                         //@}
 215                         //-----------------------------------------------------------------
 216
 217
 218
 219                         /*! \name Root Node Management *///--------------------------------
 220                         //@{
 221                 public:
 222
 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; }
 226
 227                         //! Remove a node from the root node list
 228                         void                    removeRootNode( Node& node ) { _rootNodes.removeAll( &node ); _rootNodesSet.remove( &node ); }
 229
 230                         //! Get the currently registered root node for this graph.
 231                         Node::List&             getRootNodes( ) { return _rootNodes; }
 232
 233                         //! Get the currently registered root node for this graph.
 234                         Node::Set&              getRootNodesSet( ) { return _rootNodesSet; }
 235
 236                         //! Generate the root set by automatically looking for nodes with no super nodes (O(n), n numbers of nodes).
 237                         void                    generateRootNodes( );
 238
 239                         //! Test if a given node is a graph root node.
 240                         bool                    isRootNode( const Node& node ) const;
 241
 242                 private:
 243
 244                         //! Ordered root nodes for this graph's subgraphs.
 245                         Node::List              _rootNodes;
 246
 247                         //! Root nodes of graph's subgraphs (used only to test root node existence).
 248                         Node::Set               _rootNodesSet;
 249                         //@}
 250                         //-----------------------------------------------------------------
 251
 252
 253                         /*! \name Node Attributes Management *///--------------------------
 254                         //@{
 255                 public:
 256
 257                         template < typename T >
 258                                 void            addAttribute( const QString& name, T t )
 259                         {
 260                                 _attributesNames.push_back( name );
 261                                 for ( Node::List::iterator nodeIter = getNodes( ).begin( ); nodeIter != getNodes( ).end( ); nodeIter++ )
 262                                         ( *nodeIter )->addAttribute< T >( t );
 263                         }
 264
 265                         QString                 getAttributeName( int role )
 266                         {
 267                                 return ( role < _attributesNames.size( ) ? _attributesNames[ role ] : QString( "" ) );
 268                         }
 269
 270                         template < typename T >
 271                                 void            setAttribute( Node* node, const QString& name, T& value )
 272                         {
 273                                 int role = hasAttribute( name );
 274                                 if ( role >= 0)
 275                                         setAttribute< T >( node, role, value );
 276                         }
 277
 278                         template < typename T >
 279                                 void            setAttribute( Node* node, unsigned int role, T& value )
 280                         {
 281                                 node->setAttribute< T >( role, value );
 282                         }
 283
 284                         int                             hasAttribute( const QString& name ) const
 285                         {
 286                                 int r = 0;
 287                                 Strings::const_iterator nameIter = _attributesNames.begin( );
 288                                 for ( ; nameIter != _attributesNames.end( ); nameIter++, r++ )
 289                                         if ( *nameIter == name )
 290                                                 return r;
 291                                 return -1;
 292                         }
 293
 294                         unsigned int    getAttributesCount( ) const { return _attributesNames.size( ); }
 295
 296                 protected:
 297
 298                         void                    initNodeAttributes( Node& node )
 299                         {
 300                                 node.initAttributes( _attributesNames.size( ) );
 301                         }
 302
 303                         typedef QList< QString >        Strings;
 304
 305                         Strings                 _attributesNames;
 306                         //@}
 307                         //-----------------------------------------------------------------
 308                 };
 309
 310                 typedef GraphT< GraphScene, GraphModel > Graph;
 311 } // ::qan
 312
 313 #include "./qanGraph.hpp"
 314 //-----------------------------------------------------------------------------
 315
 316
 317 #endif // laGraph_h
 318