src/qanGraph.hpp

   1 /*
   2 Qanava - Graph 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.cpp
  24 // \author      Benoit Autheman (benoit@libqanava.org)
  25 // \date        2004 February 15
  26 //-----------------------------------------------------------------------------
  27
  28 // Qt headers
  29 #include <QDateTime>
  30
  31
  32 namespace qan { // ::qan
  33
  34
  35 /* GraphT Constructor/Destructor *///-------------------------------------------
  36 template < class M, class O >
  37 GraphT< M, O >::GraphT( ) :
  38         _m( ), _o( )
  39 {
  40         _m.init( _rootNodes );
  41         _o.init( _rootNodes );
  42
  43         addAttribute< int >( "Type", 0 );
  44         addAttribute< QString >( "Label", QString( "" ) );
  45         addAttribute< VectorF >( "Position", VectorF( 2 ) );
  46         addAttribute< VectorF >( "Dimension", VectorF( 2 ) );
  47         addAttribute< QDateTime >( "Date", QDateTime( ) );
  48 }
  49
  50 template < class M, class O >
  51 GraphT< M, O >::~GraphT( )
  52 {
  53         clear( );
  54 }
  55 //-----------------------------------------------------------------------------
  56
  57
  58 template < class M, class O >
  59 void    GraphT< M, O >::modifyNode( Node& node, const QString& name, int type, void* object )
  60 {
  61         node.setLabel( name );
  62
  63         if ( type != -1 )
  64                 node.setType( type );
  65
  66         if ( object != 0 )
  67                 setNodeObject( node, object );
  68
  69         _m.nodeChanged( node );
  70         _o.nodeChanged( node );
  71 }
  72
  73 template < class M, class O >
  74 void    GraphT< M, O >::setNodeObject( Node& node, void* object )
  75 {
  76         // Map the registered node to a given memory object that act as a key
  77         if ( object != 0 )
  78         {
  79                 _objectNodeMap.insert( object, &node );
  80                 _nodeObjectMap.insert( &node, object );
  81         }
  82 }
  83
  84
  85
  86 /* Edge/Node Management *///---------------------------------------------------
  87 template < class M, class O >
  88 void    GraphT< M, O >::addNode( Node* node, void* object )
  89 {
  90         assert( node != 0 );
  91         initNodeAttributes( *node );
  92
  93         _nodes.push_back( node );
  94         _nodesSet.insert( node );
  95
  96         if ( object != 0 )
  97                 setNodeObject( *node, object );
  98
  99         if ( node->getInDegree( ) == 0 )
 100                 addRootNode( *node );
 101 }
 102
 103 template < class M, class O >
 104 Node*   GraphT< M, O >::addNode( const QString& name, int type, void* object )
 105 {
 106         Node* node = new Node( name, type );
 107         addNode( node, object );
 108         return node;
 109 }
 110
 111 template < class M, class O >
 112 void    GraphT< M, O >::insertNode( Node* node, void* object )
 113 {
 114         assert( node != 0 );
 115         addNode( node, object );
 116         _m.nodeInserted( *node );
 117         _o.nodeInserted( *node );
 118 }
 119
 120 template < class M, class O >
 121 Node*   GraphT< M, O >::insertNode( const QString& name, int type, void* object )
 122 {
 123         Node* node = new Node( name, type );
 124         insertNode( node, object );
 125         return node;
 126 }
 127
 128 template < class M, class O >
 129 void    GraphT< M, O >::removeNode( Node& node )
 130 {
 131         // Test if node subnodes will eventually became root nodes after their super node removal
 132         Node::List rootNodes;
 133         Node::List outNodes; node.collectOutNodes( outNodes );
 134         for ( Node::List::iterator outNodeIter = outNodes.begin( ); outNodeIter != outNodes.end( ); outNodeIter++ )
 135         {
 136                 Node* outNode = *outNodeIter;
 137                 if ( !isRootNode( *outNode ) && outNode->getInDegree( ) <= 1 )
 138                         rootNodes.push_back( outNode );
 139         }
 140
 141         // Add orphan out nodes as root node (node is removed to force view update and maintain graph coherency for listeners)
 142         // Oprhan out nodes are removed before 'node' so that they still have a valid parent in
 143         // an eventual associed view (for example in a QAbstractItem view, removing node would cause
 144         // the model to have a gap preventing node out nodes to be destroyed).
 145         for ( Node::List::iterator rootNodeIter = rootNodes.begin( ); rootNodeIter != rootNodes.end( ); rootNodeIter++ )
 146         {
 147                 Node& rootNode = **rootNodeIter;
 148                 //_m.nodeInsertedBegin( rootNode );
 149                 addRootNode( rootNode );
 150                 _m.nodeInserted( rootNode );
 151                 _o.nodeInserted( rootNode );
 152         }
 153
 154
 155         //_m.nodeRemovedBegin( node );
 156
 157         // Disconnect node from its "in edges".
 158         Edge::List::iterator inEdgeIter = node.getInEdges( ).begin( );
 159         for ( ; inEdgeIter != node.getInEdges( ).end( ); inEdgeIter++ )
 160         {
 161                 Edge& inEdge = ( **inEdgeIter );
 162                 inEdge.getSrc( ).getOutEdges( ).removeAll( &inEdge );
 163         }
 164         node.getInEdges( ).clear( );
 165
 166         // Disconnect node from its "out edges".
 167         Edge::List::iterator outEdgeIter = node.getOutEdges( ).begin( );
 168         for ( ; outEdgeIter != node.getOutEdges( ).end( ); outEdgeIter++ )
 169         {
 170                 Edge& outEdge = ( **outEdgeIter );
 171                 outEdge.getDst( ).getInEdges( ).removeAll( &outEdge );
 172         }
 173         node.getOutEdges( ).clear( );
 174
 175         // Remove node from the graph various node list
 176         _nodes.removeAll( &node );
 177         _nodesSet.remove( &node );
 178         void* object = findObject( &node );
 179         if ( object != 0 )
 180                 _objectNodeMap.remove( object );
 181         _nodeObjectMap.remove( &node );
 182         removeRootNode( node );
 183
 184         _m.nodeRemoved( node );
 185         _o.nodeRemoved( node );
 186 }
 187
 188 template < class M, class O >
 189 void    GraphT< M, O >::addEdge( Edge* edge )
 190 {
 191         assert( edge != 0 );
 192         if ( edge->hasSrc( ) )
 193                 edge->getSrc( ).addOutEdge( *edge );
 194         if ( edge->hasDst( ) )
 195         {
 196                 edge->getDst( ).addInEdge( *edge );
 197                 removeRootNode( edge->getDst( ) );   // Dst can't be a root node, supress it to maintain coherency
 198         }
 199         _edges.push_back( edge );
 200 }
 201
 202 template < class M, class O >
 203 Edge*   GraphT< M, O >::addEdge( Node& a, Node& b, float weight )
 204 {
 205         Edge* edge = new Edge( &a, &b, weight );
 206         addEdge( edge );
 207         return edge;
 208 }
 209
 210
 211 template < class M, class O >
 212 void    GraphT< M, O >::insertEdge( Edge* edge )
 213 {
 214
 215 }
 216
 217 template < class M, class O >
 218 Edge*   GraphT< M, O >::insertEdge( Node& src, Node& dst, float weight )
 219 {
 220         // Save destination node topology.
 221 /*      Edge::List inEdges;
 222         std::copy( dst.getInEdges( ).begin( ), dst.getInEdges( ).end( ), std::back_insert_iterator< Edge::List >( inEdges ) );
 223         Edge::List outEdges;
 224         std::copy( dst.getOutEdges( ).begin( ), dst.getOutEdges( ).end( ), std::back_insert_iterator< Edge::List >( outEdges ) );
 225
 226         // Delete the node to force view update (and eventually move the node to its correct position)
 227         void* object = findObject( &dst );
 228         removeNode( dst );
 229
 230         // Restore destination node in and out edges (and reconnect theses edges to their extremity node).
 231         for ( Edge::List::iterator inEdgeIter = inEdges.begin( ); inEdgeIter != inEdges.end( ); inEdgeIter++ )
 232         {
 233                 Edge* inEdge = *inEdgeIter;
 234                 dst.addInEdge( *inEdge );
 235                 inEdge->getSrc( ).addOutEdge( *inEdge );
 236         }
 237         for ( Edge::List::iterator outEdgeIter = outEdges.begin( ); outEdgeIter != outEdges.end( ); outEdgeIter++ )
 238         {
 239                 Edge* outEdge = *outEdgeIter;
 240                 dst.addOutEdge( *outEdge );
 241                 outEdge->getDst( ).addInEdge( *outEdge );
 242
 243                 // Remove (eventually) out node from root node
 244                 removeRootNode( outEdge->getDst( ) );
 245         }*/
 246
 247         // Insert back the node to its new correct view position
 248         Edge* edge = addEdge( src, dst, weight );
 249         //insertNode( &dst, object );
 250         _m.edgeInserted( *edge );
 251         _o.edgeInserted( *edge );
 252         return edge;
 253 }
 254
 255 template < class M, class O >
 256 Edge*   GraphT< M, O >::insertNode( Node* node, Node& superNode )
 257 {
 258         return 0;
 259 }
 260
 261 /*!
 262         \return true is there is an edge between a and b (whatever is orientation is), false otherwise.
 263  */
 264 template < class M, class O >
 265 bool    GraphT< M, O >::hasEdge( Node& a, Node& b ) const
 266 {
 267         Node::Set adjacentA;
 268         a.getAdjacentNodesSet( adjacentA );
 269         if ( adjacentA.find( &b ) != adjacentA.end( ) )
 270                 return true;
 271
 272         Node::Set adjacentB;
 273         b.getAdjacentNodesSet( adjacentB );
 274         if ( adjacentB.find( &a ) != adjacentB.end( ) )
 275                 return true;
 276
 277         return false;
 278 }
 279
 280 template < class M, class O >
 281 void    GraphT< M, O >::updateModels( )
 282 {
 283         _m.init( _rootNodes );
 284         _o.init( _rootNodes );
 285 }
 286
 287 /*!
 288         \return a pointer on the node of request label. 0 if no such node exists.
 289 */
 290 template < class M, class O >
 291 Node*   GraphT< M, O >::findNode( const QString& label )
 292 {
 293         for ( Node::List::iterator nodeIter = _nodes.begin( ); nodeIter != _nodes.end( ); nodeIter++ )
 294         {
 295                 Node* node = *nodeIter;
 296                 if ( node->getLabel( ) == label )
 297                         return node;
 298         }
 299         return 0;
 300 }
 301
 302 template < class M, class O >
 303 Node*   GraphT< M, O >::findNode( void* object )
 304 {
 305         return _objectNodeMap.value( object, 0 );
 306 }
 307
 308 template < class M, class O >
 309 Node*   GraphT< M, O >::findNode( int node )
 310 {
 311         Node::List::iterator nodeIter = _nodes.begin( );
 312         int n = 0;
 313         while ( n < node )
 314         {
 315                 nodeIter++;
 316                 n++;
 317         }
 318         if ( nodeIter != _nodes.end( ) )
 319                 return *nodeIter;
 320         return 0;
 321 }
 322
 323 /*!
 324         \result The node index if node is registered in this graph, -1 if there is no node or index.
 325  */
 326 template < class M, class O >
 327 int             GraphT< M, O >::findNode( const Node& node ) const
 328 {
 329         Node::List::const_iterator nodeIter = _nodes.begin( );
 330         int n = 0;
 331         while ( nodeIter != _nodes.end( ) && ( *nodeIter != &node ) )
 332         {
 333                 nodeIter++;
 334                 n++;
 335         }
 336         if ( nodeIter != _nodes.end( ) )
 337                 return n;
 338         return -1;
 339 }
 340
 341 template < class M, class O >
 342 void*   GraphT< M, O >::findObject( Node* node )
 343 {
 344         NodeObjectMap::iterator objectIter = _nodeObjectMap.find( node );
 345         return ( objectIter != _nodeObjectMap.end( ) ? objectIter.value( ) : 0 );
 346 }
 347
 348 /*!
 349         \param  node    Node to be searched in this graph.
 350         \return                 true if the node is found, false otherwise.
 351  */
 352 template < class M, class O >
 353 bool    GraphT< M, O >::hasNode( Node* node ) const
 354 {
 355         return ( _nodesSet.find( node ) != _nodesSet.end( ) );
 356 }
 357
 358 template < class M, class O >
 359 void    GraphT< M, O >::collectNodes( Node::Set& nodes ) const
 360 {
 361         nodes.reserve( _nodes.size( ) );
 362         foreach ( Node* node, _nodes )
 363                 nodes.insert( node );
 364         // FIXME
 365         /*std::copy( _nodes.begin( ), _nodes.end( ),
 366                            std::insert_iterator< Node::Set >( nodes, nodes.begin( ) ) );*/
 367 }
 368
 369 /*! This method clear the nodes, the fast node search cache, the node object mapping
 370     system and the edge list. Registered nodes and edges are not only dereferenced, but
 371         destroyed with a call to delete.
 372  */
 373 template < class M, class O >
 374 void            GraphT< M, O >::clear( )
 375 {
 376         _objectNodeMap.clear( );
 377         _nodeObjectMap.clear( );
 378
 379         for ( Edge::List::iterator edgeIter = _edges.begin( ); edgeIter != _edges.end( ); edgeIter++ )
 380                 delete *edgeIter;
 381         _edges.clear( );
 382
 383         _nodesSet.clear( );
 384         for ( Node::List::iterator nodeIter = _nodes.begin( ); nodeIter != _nodes.end( ); nodeIter++ )
 385                 delete *nodeIter;
 386         _nodes.clear( );
 387
 388
 389     _rootNodes.clear( );
 390     _rootNodesSet.clear( );
 391 }
 392 //-----------------------------------------------------------------------------
 393
 394
 395 /* Root Node Management *///---------------------------------------------------
 396 /*!
 397         Root nodes manually inserted via addRoot() are cleared from the root nodes (and eventually
 398         automatically re-added if needed).
 399  */
 400 template < class M, class O >
 401 void    GraphT< M, O >::generateRootNodes( )
 402 {
 403         _rootNodes.clear( );
 404         for ( Node::List::iterator nodeIter = _nodes.begin( ); nodeIter != _nodes.end( ); nodeIter++ )
 405         {
 406                 if ( ( *nodeIter )->getInDegree( ) == 0 )
 407                         addRootNode( **nodeIter );
 408         }
 409 }
 410
 411 /*!
 412         \param  node    node that must be tested against the root nodes set (must be a graph node).
 413         \return                 true if the node is a graph root node, false otherwise.
 414  */
 415 template < class M, class O >
 416 bool    GraphT< M, O >::isRootNode( const Node& node ) const
 417 {
 418         return ( _rootNodesSet.find( const_cast< Node* >( &node ) ) != _rootNodesSet.end( ) );
 419 }
 420 //-----------------------------------------------------------------------------
 421
 422
 423 } // ::qan
 424