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 "./qanGraphItemModel.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 >
  53                 class GraphT : public M
  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                 private:
  68
  69                         //! GraphT empty private copy constructor.
  70                         GraphT( const GraphT& graph );
  71                         //@}
  72                         //-----------------------------------------------------------------
  73
  74
  75
  76                         /*! \name Edge/Node Management *///--------------------------------
  77                         //@{
  78                 public:
  79
  80                         //! Clear the graph from all its edges and nodes.
  81                         void                    clear( );
  82
  83                         //! Set a node object unique key.
  84                         void                    setNodeObject( Node& node, void* object );
  85
  86                         void                    modifyNode( Node& node, const QString& name, int type = -1, void* object = 0 );
  87
  88                         void                    modifyEdge( Edge& edge, Node& a, Node& b, float weight = 1.f );
  89
  90                         typedef                 QList< GraphT< M >* >   List;
  91                         //@}
  92                         //-----------------------------------------------------------------
  93
  94
  95                         /*! \name Edge/Node Management *///--------------------------------
  96                         //@{
  97                 public:
  98
  99                         void                    addNode( Node* node, void* object = 0 );
 100
 101                         Node*                   addNode( const QString& name, int type = -1, void* object = 0 );
 102
 103                         void                    insertNode( Node* node, void* object = 0 );
 104
 105                         Node*                   insertNode( const QString& name, int type = -1, void* object = 0 );
 106
 107                         void                    removeNode( Node& node );
 108
 109
 110                         void                    addEdge( Edge* edge );
 111
 112                         Edge*                   addEdge( Node& a, Node& b, float weight = 1.f );
 113
 114                         void                    insertEdge( Edge* edge );
 115
 116                         Edge*                   insertEdge( Node& a, Node& b, float weight = 1.f );
 117
 118                         //! 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.
 119                         /*!
 120                                 \param  node            Node that must be inserted in the graph (graph will take ownership of the node).
 121                                 \param  superNode       Already existing node that will be used as a super node, and the source of the returned edge.
 122                          */
 123                         Edge*                   insertNode( Node* node, Node& superNode );
 124
 125                         void                    removeEdge( Edge& edge );
 126
 127                         bool                    hasEdge( Node& a, Node& b ) const;
 128
 129
 130                 private:
 131
 132                         //! List of nodes currently registered in this graph.
 133                         Node::List              _nodes;
 134
 135                         //! Set of nodes currently registered in this graph (used for fast node search).
 136                         Node::Set               _nodesSet;
 137
 138                         //! Map an object to its associed node.
 139                         typedef QMap< void*, Node* >    ObjectNodeMap;
 140
 141                         //! .
 142                         typedef QMap< Node*, void* >    NodeObjectMap;
 143
 144                         //! Map an object to its associed graph node.
 145                         ObjectNodeMap   _objectNodeMap;
 146
 147                         //! .
 148                         NodeObjectMap   _nodeObjectMap;
 149
 150                         //! List of edges currently connecting the registered nodes in this graph.
 151                         Edge::List              _edges;
 152                         //@}
 153                         //-----------------------------------------------------------------
 154
 155
 156
 157
 158                         /*! \name GraphT Consultation Management *///-----------------------
 159                         //@{
 160                 public:
 161
 162                         //! Get graph node count.
 163                         unsigned int    getNodeCount( ) const { return _nodes.size( ); }
 164
 165                         //! Get graph's nodes list (list must be used read-only).
 166                         Node::List&             getNodes( ) { return _nodes; }
 167
 168                         //! Get graph's edges list (list must be used read-only).
 169                         Edge::List&             getEdges( ) { return _edges; }
 170
 171                         //! Collect a set of unique node registered in this graph.
 172                         void                    collectNodes( Node::Set& nodes ) const;
 173                         //@}
 174                         //-----------------------------------------------------------------
 175
 176
 177
 178                         /*! \name Search Management *///-----------------------------------
 179                         //@{
 180                 public:
 181
 182                         //! Find a node of a given label in the graph.
 183                         Node*                   findNode( const QString& label );
 184
 185                         //! Find a node given its associed key memory object (if such key has been specified during node adjunction).
 186                         Node*                   findNode( void* object );
 187
 188                         //! Find the nth registered node in this graph (For internal use only).
 189                         /*! This method should only be used in repositories just after node loading when their initial order has not been altered. */
 190                         Node*                   findNode( int node );
 191
 192                         //! Get the index where a node is currently registered in this graph.
 193                         /*! This method should only be used in repositories just after node loading when their initial order has not been altered. */
 194                         int                             findNode( const Node& node ) const;
 195
 196                         //! Find a node object for a specific node (if such an object has been specified during node adjunction).
 197                         void*                   findObject( Node* node );
 198
 199                         //! Search for a specific node in this graph and return true if the node is found.
 200                         bool                    hasNode( Node* node ) const;
 201                         //@}
 202                         //-----------------------------------------------------------------
 203
 204
 205
 206                         /*! \name Root Node Management *///--------------------------------
 207                         //@{
 208                 public:
 209
 210                         //! Add a root to this graph (ie a node that doesn't have super nodes.)
 211                         /*! \param node must be already registered in the graph.                */
 212                         void                    addRootNode( Node& node ) { _rootNodes << &node; _rootNodesSet << &node; }
 213
 214                         //! Remove a node from the root node list
 215                         void                    removeRootNode( Node& node ) { _rootNodes.removeAll( &node ); _rootNodesSet.remove( &node ); }
 216
 217                         //! Get the currently registered root node for this graph.
 218                         Node::List&             getRootNodes( ) { return _rootNodes; }
 219
 220                         //! Get the currently registered root node for this graph.
 221                         Node::Set&              getRootNodesSet( ) { return _rootNodesSet; }
 222
 223                         //! Generate the root set by automatically looking for nodes with no super nodes (O(n), n numbers of nodes).
 224                         void                    generateRootNodes( );
 225
 226                         //! Test if a given node is a graph root node.
 227                         bool                    isRootNode( const Node& node ) const;
 228
 229                 private:
 230
 231                         //! Ordered root nodes for this graph's subgraphs.
 232                         Node::List              _rootNodes;
 233
 234                         //! Root nodes of graph's subgraphs (used only to test root node existence).
 235                         Node::Set               _rootNodesSet;
 236                         //@}
 237                         //-----------------------------------------------------------------
 238
 239
 240                         /*! \name Node Attributes Management *///--------------------------
 241                         //@{
 242                 public:
 243
 244                         template < typename T >
 245                                 void            addAttribute( const QString& name, T t )
 246                         {
 247                                 _attributesNames.push_back( name );
 248                                 for ( Node::List::iterator nodeIter = getNodes( ).begin( ); nodeIter != getNodes( ).end( ); nodeIter++ )
 249                                         ( *nodeIter )->addAttribute< T >( t );
 250                         }
 251
 252                         QString                 getAttributeName( int role )
 253                         {
 254                                 return ( role < _attributesNames.size( ) ? _attributesNames[ role ] : QString( "" ) );
 255                         }
 256
 257                         template < typename T >
 258                                 void            setAttribute( Node* node, const QString& name, T& value )
 259                         {
 260                                 int role = hasAttribute( name );
 261                                 if ( role >= 0)
 262                                         setAttribute< T >( node, role, value );
 263                         }
 264
 265                         template < typename T >
 266                                 void            setAttribute( Node* node, unsigned int role, T& value )
 267                         {
 268                                 node->setAttribute< T >( role, value );
 269                         }
 270
 271                         int                             hasAttribute( const QString& name ) const
 272                         {
 273                                 int r = 0;
 274                                 Strings::const_iterator nameIter = _attributesNames.begin( );
 275                                 for ( ; nameIter != _attributesNames.end( ); nameIter++, r++ )
 276                                         if ( *nameIter == name )
 277                                                 return r;
 278                                 return -1;
 279                         }
 280
 281                         unsigned int    getAttributesCount( ) const { return _attributesNames.size( ); }
 282
 283                 protected:
 284
 285                         void                    initNodeAttributes( Node& node )
 286                         {
 287                                 node.initAttributes( _attributesNames.size( ) );
 288                         }
 289
 290                         typedef QList< QString >        Strings;
 291
 292                         Strings                 _attributesNames;
 293                         //@}
 294                         //-----------------------------------------------------------------
 295                 };
 296
 297                 typedef GraphT< GraphItemModel > Graph;
 298 } // ::qan
 299
 300 #include "./qanGraph.hpp"
 301 //-----------------------------------------------------------------------------
 302
 303
 304 #endif // laGraph_h
 305