source/graphtypes.cc

   1 /* This file is part of Shapes.
   2  *
   3  * Shapes is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * any later version.
   7  *
   8  * Shapes is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with Shapes.  If not, see <http://www.gnu.org/licenses/>.
  15  *
  16  * Copyright 2013, 2014 Henrik Tidefelt
  17  */
  18
  19 #include "shapestypes.h"
  20 #include "shapesexceptions.h"
  21 #include "globals.h"
  22 #include "methodbase.h"
  23 #include "ast.h"
  24 #include "graphtypes_impl.h"
  25 #include "shapescore.h"
  26 #include "continuations.h"
  27 #include "warn.h"
  28
  29 using namespace Shapes;
  30
  31
  32 Kernel::Edge::Edge( Kernel::Node * source, Kernel::Node * target, size_t index, bool directed )
  33         : source_( source ), target_( target ), index_( index )
  34 {
  35         if( ! directed && source_->index( ) > target_->index( ) ){
  36                 Kernel::Node * tmp = target_;
  37                 target_ = source_;
  38                 source_ = tmp;
  39         }
  40 }
  41
  42
  43 Kernel::EdgePredicate::EdgePredicate( )
  44         : always_false_( false ), always_true_( false )
  45 { }
  46
  47 Kernel::EdgePredicate::~EdgePredicate( )
  48 { }
  49
  50
  51 void
  52 Kernel::Node::show( std::ostream & os ) const
  53 {
  54         os << "< node with key " ;
  55         key_->show( os );
  56         os << " >" ;
  57 }
  58
  59 Kernel::Node::ListRef
  60 Kernel::Node::prepend_uedges( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
  61 {
  62         Kernel::Node::ListRef lst = prepend_edges( uedgesLow_, false, rest, graph, filter );
  63         return prepend_edges( uedgesHigh_, false, lst, graph, filter );
  64 }
  65
  66 Kernel::Node::ListRef
  67 Kernel::Node::prepend_dedgesIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
  68 {
  69         return prepend_edges( dedgesIn_, true, rest, graph, filter );
  70 }
  71
  72 Kernel::Node::ListRef
  73 Kernel::Node::prepend_dedgesOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
  74 {
  75         return prepend_edges( dedgesOut_, true, rest, graph, filter );
  76 }
  77
  78 Kernel::Node::ListRef
  79 Kernel::Node::prepend_uloops( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
  80 {
  81         return prepend_edges( uloops_, false, rest, graph, filter );
  82 }
  83
  84 Kernel::Node::ListRef
  85 Kernel::Node::prepend_dloops( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
  86 {
  87         return prepend_edges( dloops_, true, rest, graph, filter );
  88 }
  89
  90 Kernel::Node::ListRef
  91 Kernel::Node::prepend_uedges_to( Kernel::Node * neighbor, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
  92 {
  93         if( neighbor->index( ) < index_ )
  94                 return prepend_edges_neighbor( neighbor, uedgesLow_, false, rest, graph, filter );
  95         else
  96                 return prepend_edges_neighbor( neighbor, uedgesHigh_, false, rest, graph, filter );
  97 }
  98
  99 Kernel::Node::ListRef
 100 Kernel::Node::prepend_dedges_from( Kernel::Node * source, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
 101 {
 102         return prepend_edges_neighbor( source, dedgesIn_, true, rest, graph, filter );
 103 }
 104
 105 Kernel::Node::ListRef
 106 Kernel::Node::prepend_dedges_to( Kernel::Node * target, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter ) const
 107 {
 108         return prepend_edges_neighbor( target, dedgesOut_, true, rest, graph, filter );
 109 }
 110
 111 Kernel::Node::ListRef
 112 Kernel::Node::prepend_uedgeNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 113 {
 114         Kernel::Node::ListRef result = rest;
 115         for( EdgeSetSource::const_iterator e = uedgesLow_.begin( ); e != uedgesLow_.end( ); ++e ){
 116                 result = Helpers::SingleList_cons( new Lang::Node( graph, (*e)->source( ) ), result );
 117         }
 118         for( EdgeSetTarget::const_iterator e = uedgesHigh_.begin( ); e != uedgesHigh_.end( ); ++e ){
 119                 result = Helpers::SingleList_cons( new Lang::Node( graph, (*e)->target( ) ), result );
 120         }
 121         return result;
 122 }
 123
 124 Kernel::Node::ListRef
 125 Kernel::Node::prepend_dedgeNeighborsIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 126 {
 127         Kernel::Node::ListRef result = rest;
 128         for( EdgeSetSource::const_iterator e = dedgesIn_.begin( ); e != dedgesIn_.end( ); ++e ){
 129                 result = Helpers::SingleList_cons( new Lang::Node( graph, (*e)->source( ) ), result );
 130         }
 131         return result;
 132 }
 133
 134 Kernel::Node::ListRef
 135 Kernel::Node::prepend_dedgeNeighborsOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 136 {
 137         Kernel::Node::ListRef result = rest;
 138         for( EdgeSetTarget::const_iterator e = dedgesOut_.begin( ); e != dedgesOut_.end( ); ++e ){
 139                 result = Helpers::SingleList_cons( new Lang::Node( graph, (*e)->target( ) ), result );
 140         }
 141         return result;
 142 }
 143
 144 Kernel::Node::ListRef
 145 Kernel::Node::prepend_uloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 146 {
 147         Kernel::Node::ListRef result = rest;
 148         for( EdgeSetSource::const_iterator e = uloops_.begin( ); e != uloops_.end( ); ++e ){
 149                 result = Helpers::SingleList_cons( new Lang::Node( graph, this ), result );
 150                 result = Helpers::SingleList_cons( new Lang::Node( graph, this ), result );
 151         }
 152         return result;
 153 }
 154
 155 Kernel::Node::ListRef
 156 Kernel::Node::prepend_dloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 157 {
 158         Kernel::Node::ListRef result = rest;
 159         for( EdgeSetSource::const_iterator e = dloops_.begin( ); e != dloops_.end( ); ++e ){
 160                 result = Helpers::SingleList_cons( new Lang::Node( graph, this ), result );
 161         }
 162         return result;
 163 }
 164
 165 Kernel::Node::ListRef
 166 Kernel::Node::prepend_unique_uedgeNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const
 167 {
 168         Kernel::Node::ListRef result = rest;
 169         for( EdgeSetSource::const_iterator e = uedgesLow_.begin( ); e != uedgesLow_.end( ); ++e ){
 170                 const Kernel::Node * neighbor = (*e)->source( );
 171                 size_t index = neighbor->index( );
 172                 if( added->find( index ) != added->end( ) )
 173                         continue;
 174                 added->insert( added->begin( ), index );
 175                 result = Helpers::SingleList_cons( new Lang::Node( graph, neighbor ), result );
 176         }
 177         for( EdgeSetTarget::const_iterator e = uedgesHigh_.begin( ); e != uedgesHigh_.end( ); ++e ){
 178                 const Kernel::Node * neighbor = (*e)->target( );
 179                 size_t index = neighbor->index( );
 180                 if( added->find( index ) != added->end( ) )
 181                         continue;
 182                 added->insert( added->begin( ), index );
 183                 result = Helpers::SingleList_cons( new Lang::Node( graph, neighbor ), result );
 184         }
 185         return result;
 186 }
 187
 188 Kernel::Node::ListRef
 189 Kernel::Node::prepend_unique_dedgeNeighborsIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const
 190 {
 191         Kernel::Node::ListRef result = rest;
 192         for( EdgeSetSource::const_iterator e = dedgesIn_.begin( ); e != dedgesIn_.end( ); ++e ){
 193                 const Kernel::Node * neighbor = (*e)->source( );
 194                 size_t index = neighbor->index( );
 195                 if( added->find( index ) != added->end( ) )
 196                         continue;
 197                 added->insert( added->begin( ), index );
 198                 result = Helpers::SingleList_cons( new Lang::Node( graph, neighbor ), result );
 199         }
 200         return result;
 201 }
 202
 203 Kernel::Node::ListRef
 204 Kernel::Node::prepend_unique_dedgeNeighborsOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const
 205 {
 206         Kernel::Node::ListRef result = rest;
 207         for( EdgeSetTarget::const_iterator e = dedgesOut_.begin( ); e != dedgesOut_.end( ); ++e ){
 208                 const Kernel::Node * neighbor = (*e)->target( );
 209                 size_t index = neighbor->index( );
 210                 if( added->find( index ) != added->end( ) )
 211                         continue;
 212                 added->insert( added->begin( ), index );
 213                 result = Helpers::SingleList_cons( new Lang::Node( graph, neighbor ), result );
 214         }
 215         return result;
 216 }
 217
 218 Kernel::Node::ListRef
 219 Kernel::Node::prepend_unique_uloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const
 220 {
 221         Kernel::Node::ListRef result = rest;
 222         if( not uloops_.empty( ) && added->find( index_ ) == added->end( ) ) {
 223                 added->insert( added->begin( ), index_ );
 224                 result = Helpers::SingleList_cons( new Lang::Node( graph, this ), result );
 225         }
 226         return result;
 227 }
 228
 229 Kernel::Node::ListRef
 230 Kernel::Node::prepend_unique_dloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const
 231 {
 232         Kernel::Node::ListRef result = rest;
 233         if( not dloops_.empty( ) && added->find( index_ ) == added->end( ) ) {
 234                 added->insert( added->begin( ), index_ );
 235                 result = Helpers::SingleList_cons( new Lang::Node( graph, this ), result );
 236         }
 237         return result;
 238 }
 239
 240 Kernel::Node::ListRef
 241 Kernel::Node::prepend_u_multiedges( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 242 {
 243         Kernel::Node::ListRef edges = rest;
 244         edges = prepend_u_multiedgesHigh( edges, graph );
 245         edges = prepend_u_multiedgesLow( edges, graph );
 246         return edges;
 247 }
 248
 249 Kernel::Node::ListRef
 250 Kernel::Node::prepend_d_multiedgesIn( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 251 {
 252         if( dedgesIn_.empty( ) )
 253                 return rest;
 254
 255         Kernel::Node::ListRef edges = rest;
 256
 257         EdgeSetSource::const_iterator iBegin = dedgesIn_.begin( );
 258         EdgeSetSource::const_iterator theEnd = dedgesIn_.end( );
 259         while( iBegin != theEnd ){
 260                 EdgeSetSource::const_iterator iEnd = iBegin;
 261                 ++iEnd;
 262                 size_t count = 1;
 263                 const Kernel::Node * source = (*iBegin)->source( );
 264                 for( ; iEnd != theEnd && (*iEnd)->source( ) == source; ++iEnd, ++count )
 265                         ;
 266                 edges = Helpers::SingleList_cons( new Lang::MultiEdge( graph, true, source, this, count, iBegin, iEnd ), edges );
 267                 iBegin = iEnd;
 268         }
 269
 270         return edges;
 271 }
 272
 273 Kernel::Node::ListRef
 274 Kernel::Node::prepend_d_multiedgeInFrom( const Kernel::Node * source, const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 275 {
 276         if( dedgesIn_.empty( ) )
 277                 return rest;
 278
 279         /* Construct minimum and maximum edges defining the range in the set.
 280          * The const_cast(s) are safe; the values pointed to will not be modified.
 281          */
 282         Kernel::Edge edgeLow( const_cast< Kernel::Node * >( source ), const_cast< Kernel::Node * >( this ), 0, true );
 283         Kernel::Edge edgeHigh( const_cast< Kernel::Node * >( source ), const_cast< Kernel::Node * >( this ), std::numeric_limits< size_t >::max( ), true );
 284         EdgeSetSource::const_iterator iBegin = dedgesIn_.lower_bound( & edgeLow );
 285         EdgeSetSource::const_iterator iEnd = dedgesIn_.upper_bound( & edgeHigh );
 286
 287         size_t count = 0;
 288         for( EdgeSetSource::const_iterator i = iBegin; i != iEnd; ++i, ++count )
 289                 ;
 290
 291         if( count == 0 )
 292                 return rest;
 293
 294         return Helpers::SingleList_cons( new Lang::MultiEdge( graph, true, source, this, count, iBegin, iEnd ), rest );
 295 }
 296
 297 Kernel::Node::ListRef
 298 Kernel::Node::prepend_d_multiedgesOut( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 299 {
 300         if( dedgesOut_.empty( ) )
 301                 return rest;
 302
 303         Kernel::Node::ListRef edges = rest;
 304
 305         EdgeSetTarget::const_iterator i = dedgesOut_.begin( );
 306         EdgeSetTarget::const_iterator theEnd = dedgesOut_.end( );
 307         while( i != theEnd ){
 308                 const Kernel::Node * target = (*i)->target( );
 309                 ++i;
 310                 for( ; i != theEnd && (*i)->target( ) == target; ++i )
 311                         ;
 312                 edges = prepend_d_multiedgeInFrom( this, rest, graph );
 313         }
 314
 315         return edges;
 316 }
 317
 318 Kernel::Node::ListRef
 319 Kernel::Node::prepend_u_multiloops( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 320 {
 321         if( uloops_.empty( ) )
 322                 return rest;
 323
 324         return Helpers::SingleList_cons( new Lang::MultiEdge( graph, false, this, this, uloops_.size( ), uloops_.begin( ), uloops_.end( ) ), rest );
 325 }
 326
 327 Kernel::Node::ListRef
 328 Kernel::Node::prepend_d_multiloops( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 329 {
 330         if( dloops_.empty( ) )
 331                 return rest;
 332
 333         return Helpers::SingleList_cons( new Lang::MultiEdge( graph, true, this, this, dloops_.size( ), dloops_.begin( ), dloops_.end( ) ), rest );
 334 }
 335
 336 Kernel::Node::ListRef
 337 Kernel::Node::prepend_u_multiedgesLow( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 338 {
 339         if( uedgesLow_.empty( ) )
 340                 return rest;
 341
 342         Kernel::Node::ListRef edges = rest;
 343
 344         EdgeSetSource::const_iterator iBegin = uedgesLow_.begin( );
 345         EdgeSetSource::const_iterator theEnd = uedgesLow_.end( );
 346         while( iBegin != theEnd ){
 347                 EdgeSetSource::const_iterator iEnd = iBegin;
 348                 ++iEnd;
 349                 size_t count = 1;
 350                 const Kernel::Node * source = (*iBegin)->source( );
 351                 for( ; iEnd != theEnd && (*iEnd)->source( ) == source; ++iEnd, ++count )
 352                         ;
 353                 edges = Helpers::SingleList_cons( new Lang::MultiEdge( graph, false, source, this, count, iBegin, iEnd ), edges );
 354                 iBegin = iEnd;
 355         }
 356
 357         return edges;
 358 }
 359
 360 Kernel::Node::ListRef
 361 Kernel::Node::prepend_u_multiedgeLowFrom( const Kernel::Node * source, const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 362 {
 363         if( uedgesLow_.empty( ) )
 364                 return rest;
 365
 366         /* Construct minimum and maximum edges defining the range in the set.
 367          * The const_cast(s) are safe; the values pointed to will not be modified.
 368          */
 369         Kernel::Edge edgeLow( const_cast< Kernel::Node * >( source ), const_cast< Kernel::Node * >( this ), 0, false );
 370         Kernel::Edge edgeHigh( const_cast< Kernel::Node * >( source ), const_cast< Kernel::Node * >( this ), std::numeric_limits< size_t >::max( ), false );
 371         EdgeSetSource::const_iterator iBegin = uedgesLow_.lower_bound( & edgeLow );
 372         EdgeSetSource::const_iterator iEnd = uedgesLow_.upper_bound( & edgeHigh );
 373
 374         size_t count = 0;
 375         for( EdgeSetSource::const_iterator i = iBegin; i != iEnd; ++i, ++count )
 376                 ;
 377
 378         if( count == 0 )
 379                 return rest;
 380
 381         return Helpers::SingleList_cons( new Lang::MultiEdge( graph, false, source, this, count, iBegin, iEnd ), rest );
 382 }
 383
 384 Kernel::Node::ListRef
 385 Kernel::Node::prepend_u_multiedgesHigh( const Kernel::Node::ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const
 386 {
 387         if( uedgesHigh_.empty( ) )
 388                 return rest;
 389
 390         Kernel::Node::ListRef edges = rest;
 391
 392         EdgeSetTarget::const_iterator i = uedgesHigh_.begin( );
 393         EdgeSetTarget::const_iterator theEnd = uedgesHigh_.end( );
 394         while( i != theEnd ){
 395                 const Kernel::Node * target = (*i)->target( );
 396                 ++i;
 397                 for( ; i != theEnd && (*i)->target( ) == target; ++i )
 398                         ;
 399                 edges = prepend_u_multiedgeLowFrom( this, rest, graph );
 400         }
 401
 402         return edges;
 403 }
 404
 405
 406 namespace Shapes
 407 {
 408         namespace Lang
 409         {
 410
 411                 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
 412                 class NodeMethod_edges : public Lang::MethodBase< Lang::Node >
 413                 {
 414                 public:
 415                         NodeMethod_edges( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID );
 416                         virtual ~NodeMethod_edges( );
 417                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 418                         static const char * staticFieldID( ) { return fieldID; }
 419                 };
 420
 421                 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
 422                 class NodeMethod_multiedges : public Lang::MethodBase< Lang::Node >
 423                 {
 424                 public:
 425                         NodeMethod_multiedges( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID );
 426                         virtual ~NodeMethod_multiedges( );
 427                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 428                         static const char * staticFieldID( ) { return fieldID; }
 429                 };
 430
 431                 template< bool directed, bool undirected, const char * fieldID >
 432                 class NodeMethod_loops : public Lang::MethodBase< Lang::Node >
 433                 {
 434                 public:
 435                         NodeMethod_loops( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID );
 436                         virtual ~NodeMethod_loops( );
 437                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 438                         static const char * staticFieldID( ) { return fieldID; }
 439                 };
 440
 441                 template< bool directed, bool undirected, const char * fieldID >
 442                 class NodeMethod_multiloops : public Lang::MethodBase< Lang::Node >
 443                 {
 444                 public:
 445                         NodeMethod_multiloops( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID );
 446                         virtual ~NodeMethod_multiloops( );
 447                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 448                         static const char * staticFieldID( ) { return fieldID; }
 449                 };
 450
 451                 template< bool reverse, const char * fieldID >
 452                 class NodeMethod_trace : public Lang::MethodBase< Lang::Node >
 453                 {
 454                 public:
 455                         NodeMethod_trace( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID );
 456                         virtual ~NodeMethod_trace( );
 457                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 458                         static const char * staticFieldID( ) { return fieldID; }
 459                 };
 460
 461                 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
 462                 class NodeMethod_neighbors : public Lang::MethodBase< Lang::Node >
 463                 {
 464                 public:
 465                         NodeMethod_neighbors( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID );
 466                         virtual ~NodeMethod_neighbors( );
 467                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 468                         static const char * staticFieldID( ) { return fieldID; }
 469                 };
 470
 471                 template< class T >
 472                 class Method_get_graph : public Lang::MethodBase< T >
 473                 {
 474                 public:
 475                         Method_get_graph( RefCountPtr< const T > self, const Ast::FileID * fullMethodID );
 476                         virtual ~Method_get_graph( );
 477                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 478                         static const char * staticFieldID( ) { return "get_graph"; }
 479                 };
 480
 481         }
 482
 483         namespace Kernel
 484         {
 485                 char FIELD_ID_u_edges[]     = "u_edges";
 486                 char FIELD_ID_d_edges_in[]  = "d_edges_in";
 487                 char FIELD_ID_d_edges_out[] = "d_edges_out";
 488                 char FIELD_ID_edges_in[]    =   "edges_in";
 489                 char FIELD_ID_edges_out[]   =   "edges_out";
 490                 char FIELD_ID_edges[]       =   "edges";
 491
 492                 char FIELD_ID_u_loops[] = "u_loops";
 493                 char FIELD_ID_d_loops[] = "d_loops";
 494                 char FIELD_ID_loops[]   =   "loops";
 495
 496                 char FIELD_ID_u_multiedges[]     = "u_multiedges";
 497                 char FIELD_ID_d_multiedges_in[]  = "d_multiedges_in";
 498                 char FIELD_ID_d_multiedges_out[] = "d_multiedges_out";
 499                 char FIELD_ID_multiedges_in[]    =   "multiedges_in";
 500                 char FIELD_ID_multiedges_out[]   =   "multiedges_out";
 501                 char FIELD_ID_multiedges[]       =   "multiedges";
 502
 503                 char FIELD_ID_u_multiloops[] = "u_multiloops";
 504                 char FIELD_ID_d_multiloops[] = "d_multiloops";
 505                 char FIELD_ID_multiloops[]   =   "multiloops";
 506
 507                 char FIELD_ID_trace[]     = "trace";
 508                 char FIELD_ID_backtrace[] = "backtrace";
 509
 510                 char FIELD_ID_u_neighbors[]     = "u_neighbors";
 511                 char FIELD_ID_d_neighbors_in[]  = "d_neighbors_in";
 512                 char FIELD_ID_d_neighbors_out[] = "d_neighbors_out";
 513                 char FIELD_ID_neighbors_in[]    =   "neighbors_in";
 514                 char FIELD_ID_neighbors_out[]   =   "neighbors_out";
 515                 char FIELD_ID_neighbors[]       =   "neighbors";
 516         }
 517 }
 518
 519 Lang::Node::Node( const RefCountPtr< const Lang::Graph > & graph, const Kernel::Node * node )
 520         : graph_( graph ), node_( node )
 521 { }
 522
 523 Lang::Node::~Node( )
 524 { }
 525
 526 void
 527 Node_register_methods( Lang::SystemFinalClass * dstClass )
 528 {
 529         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_edges< false, true, true, true, Kernel::FIELD_ID_u_edges > >( ) );
 530         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_edges< true, false, true, false, Kernel::FIELD_ID_d_edges_in > >( ) );
 531         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_edges< true, false, false, true, Kernel::FIELD_ID_d_edges_out > >( ) );
 532         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_edges< true, true, true, false, Kernel::FIELD_ID_edges_in > >( ) );
 533         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_edges< true, true, false, true, Kernel::FIELD_ID_edges_out > >( ) );
 534         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_edges< true, true, true, true, Kernel::FIELD_ID_edges > >( ) );
 535
 536         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_loops< false, true, Kernel::FIELD_ID_u_loops > >( ) );
 537         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_loops< true, false, Kernel::FIELD_ID_d_loops > >( ) );
 538         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_loops< true, true, Kernel::FIELD_ID_loops > >( ) );
 539
 540         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiedges< false, true, true, true, Kernel::FIELD_ID_u_multiedges > >( ) );
 541         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiedges< true, false, true, false, Kernel::FIELD_ID_d_multiedges_in > >( ) );
 542         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiedges< true, false, false, true, Kernel::FIELD_ID_d_multiedges_out > >( ) );
 543         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiedges< true, true, true, false, Kernel::FIELD_ID_multiedges_in > >( ) );
 544         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiedges< true, true, false, true, Kernel::FIELD_ID_multiedges_out > >( ) );
 545         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiedges< true, true, true, true, Kernel::FIELD_ID_multiedges > >( ) );
 546
 547         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiloops< false, true, Kernel::FIELD_ID_u_multiloops > >( ) );
 548         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiloops< true, false, Kernel::FIELD_ID_d_multiloops > >( ) );
 549         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_multiloops< true, true, Kernel::FIELD_ID_multiloops > >( ) );
 550
 551         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_trace< false, Kernel::FIELD_ID_trace > >( ) );
 552         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_trace< true, Kernel::FIELD_ID_backtrace > >( ) );
 553
 554         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_neighbors< false, true, true, true, Kernel::FIELD_ID_u_neighbors > >( ) );
 555         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_neighbors< true, false, true, false, Kernel::FIELD_ID_d_neighbors_in > >( ) );
 556         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_neighbors< true, false, false, true, Kernel::FIELD_ID_d_neighbors_out > >( ) );
 557         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_neighbors< true, true, true, false, Kernel::FIELD_ID_neighbors_in > >( ) );
 558         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_neighbors< true, true, false, true, Kernel::FIELD_ID_neighbors_out > >( ) );
 559         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::NodeMethod_neighbors< true, true, true, true, Kernel::FIELD_ID_neighbors > >( ) );
 560
 561         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Node, Lang::Method_get_graph< Lang::Node > >( ) );
 562 }
 563
 564 RefCountPtr< const Lang::Class > Lang::Node::TypeID( new Lang::SystemFinalClass( strrefdup( "Node" ), Node_register_methods ) );
 565 TYPEINFOIMPL( Node );
 566
 567 void
 568 Lang::Node::show( std::ostream & os ) const
 569 {
 570         node_->show( os );
 571 }
 572
 573 Kernel::VariableHandle
 574 Lang::Node::getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const
 575 {
 576         if( strcmp( fieldID, "value" ) == 0 )
 577                 {
 578                         return graph_->nodeValue( node_ );
 579                 }
 580         if( strcmp( fieldID, "key" ) == 0 )
 581                 {
 582                         return Kernel::VariableHandle( new Kernel::Variable( node_->key( ) ) );
 583                 }
 584         if( strcmp( fieldID, "index" ) == 0 )
 585                 {
 586                         return Helpers::newValHandle( new Lang::Integer( node_->index( ) ) );
 587                 }
 588         if( strcmp( fieldID, "partition" ) == 0 )
 589                 {
 590                         return graph_->nodePartition( node_ );
 591                 }
 592         if( strcmp( fieldID, "u_degree" ) == 0 )
 593                 {
 594                         return Helpers::newValHandle( new Lang::Integer( node_->u_degree( ) ) );
 595                 }
 596         if( strcmp( fieldID, "d_degree_in" ) == 0 )
 597                 {
 598                         return Helpers::newValHandle( new Lang::Integer( node_->d_degree_in( ) ) );
 599                 }
 600         if( strcmp( fieldID, "d_degree_out" ) == 0 )
 601                 {
 602                         return Helpers::newValHandle( new Lang::Integer( node_->d_degree_out( ) ) );
 603                 }
 604         if( strcmp( fieldID, "d_degree" ) == 0 )
 605                 {
 606                         return Helpers::newValHandle( new Lang::Integer( node_->d_degree( ) ) );
 607                 }
 608         if( strcmp( fieldID, "degree" ) == 0 )
 609                 {
 610                         return Helpers::newValHandle( new Lang::Integer( node_->degree( ) ) );
 611                 }
 612         if( strcmp( fieldID, "u_loop_count" ) == 0 )
 613                 {
 614                         return Helpers::newValHandle( new Lang::Integer( node_->u_loop_count( ) ) );
 615                 }
 616         if( strcmp( fieldID, "d_loop_count" ) == 0 )
 617                 {
 618                         return Helpers::newValHandle( new Lang::Integer( node_->d_loop_count( ) ) );
 619                 }
 620         if( strcmp( fieldID, "loop_count" ) == 0 )
 621                 {
 622                         return Helpers::newValHandle( new Lang::Integer( node_->loop_count( ) ) );
 623                 }
 624
 625         return TypeID->getMethod( selfRef, fieldID ); /* This will throw if there is no such method. */
 626 }
 627
 628 void
 629 Lang::Node::gcMark( Kernel::GCMarkedSet & marked )
 630 {
 631         const_cast< Lang::Graph * >( graph_.getPtr( ) )->gcMark( marked );
 632 }
 633
 634
 635 Lang::Edge::Edge( const RefCountPtr< const Lang::Graph > & graph, const Kernel::Edge * edge, bool directed )
 636         : graph_( graph ), edge_( edge ), directed_( directed )
 637 { }
 638
 639 Lang::Edge::~Edge( )
 640 { }
 641
 642 void
 643 Edge_register_methods( Lang::SystemFinalClass * dstClass )
 644 {
 645         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Edge, Lang::Method_get_graph< Lang::Edge > >( ) );
 646 }
 647
 648 RefCountPtr< const Lang::Class > Lang::Edge::TypeID( new Lang::SystemFinalClass( strrefdup( "Edge" ), Edge_register_methods ) );
 649 TYPEINFOIMPL( Edge );
 650
 651 const Kernel::Node *
 652 Lang::Edge::trace( const Kernel::Node * sourceArg, bool nullOnError ) const
 653 {
 654         const Kernel::Node * source = edge_->source( );
 655         const Kernel::Node * target = edge_->target( );
 656
 657         if( directed_ ) {
 658                 if( sourceArg == source )
 659                         return target;
 660                 else if( nullOnError )
 661                         return NULL;
 662                 else
 663                         throw Exceptions::InternalError( "Edge trace error." );
 664         } else {
 665                 if( sourceArg == source )
 666                         return target;
 667                 if( sourceArg == target )
 668                         return source;
 669                 else if( nullOnError )
 670                         return NULL;
 671                 else
 672                         throw Exceptions::InternalError( "Edge trace error." );
 673         }
 674 }
 675
 676 const Kernel::Node *
 677 Lang::Edge::trace( const Kernel::Node * sourceArg, const Ast::SourceLocation & callLoc ) const
 678 {
 679         const Kernel::Node * res = trace( sourceArg, true );
 680         if( res != 0 )
 681                 return res;
 682         throw Exceptions::EdgeTraceError( directed_ ? Exceptions::EdgeTraceError::TRACE : Exceptions::EdgeTraceError::UNDIRECTED,
 683                                                                                                                                                 edge_->source( )->key( ), edge_->target( )->key( ),
 684                                                                                                                                                 sourceArg->key( ),
 685                                                                                                                                                 callLoc );
 686 }
 687
 688 const Kernel::Node *
 689 Lang::Edge::backtrace( const Kernel::Node * targetArg, bool nullOnError ) const
 690 {
 691         const Kernel::Node * source = edge_->source( );
 692         const Kernel::Node * target = edge_->target( );
 693
 694         if( directed_ ) {
 695                 if( targetArg == target )
 696                         return source;
 697                 else if( nullOnError )
 698                         return NULL;
 699                 else
 700                         throw Exceptions::InternalError( "Edge trace error." );
 701         } else {
 702                 if( targetArg == source )
 703                         return target;
 704                 if( targetArg == target )
 705                         return source;
 706                 else if( nullOnError )
 707                         return NULL;
 708                 else
 709                         throw Exceptions::InternalError( "Edge trace error." );
 710         }
 711 }
 712
 713 const Kernel::Node *
 714 Lang::Edge::backtrace( const Kernel::Node * targetArg, const Ast::SourceLocation & callLoc ) const
 715 {
 716         const Kernel::Node * res = backtrace( targetArg, true );
 717         if( res != 0 )
 718                 return res;
 719         throw Exceptions::EdgeTraceError( directed_ ? Exceptions::EdgeTraceError::BACKTRACE : Exceptions::EdgeTraceError::UNDIRECTED,
 720                                                                                                                                                 edge_->source( )->key( ), edge_->target( )->key( ),
 721                                                                                                                                                 targetArg->key( ),
 722                                                                                                                                                 callLoc );
 723 }
 724
 725 void
 726 Lang::Edge::show( std::ostream & os ) const
 727 {
 728         if( directed_ ){
 729                 os << "< directed edge ( " ;
 730                 edge_->source( )->key( )->show( os );
 731                 os << ", " ;
 732                 edge_->target( )->key( )->show( os );
 733                 os << " ) >" ;
 734         }else{
 735                 os << "< undirected edge ( " ;
 736                 edge_->source( )->key( )->show( os );
 737                 os << ", " ;
 738                 edge_->target( )->key( )->show( os );
 739                 os << " ) >" ;
 740         }
 741 }
 742
 743 Kernel::VariableHandle
 744 Lang::Edge::getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const
 745 {
 746         if( strcmp( fieldID, "directed?" ) == 0 )
 747                 {
 748                         return directed_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
 749                 }
 750         if( strcmp( fieldID, "source" ) == 0 )
 751                 {
 752                         return Helpers::newValHandle( new Lang::Node( graph_, edge_->source( ) ) );
 753                 }
 754         if( strcmp( fieldID, "target" ) == 0 )
 755                 {
 756                         return Helpers::newValHandle( new Lang::Node( graph_, edge_->target( ) ) );
 757                 }
 758         if( strcmp( fieldID, "value" ) == 0 )
 759                 {
 760                         return graph_->edgeValue( edge_ );
 761                 }
 762         if( strcmp( fieldID, "label" ) == 0 )
 763                 {
 764                         return graph_->edgeLabel( edge_ );
 765                 }
 766         if( strcmp( fieldID, "index" ) == 0 )
 767                 {
 768                         return Helpers::newValHandle( new Lang::Integer( edge_->index( ) ) );
 769                 }
 770         return TypeID->getMethod( selfRef, fieldID ); /* This will throw if there is no such method. */
 771 }
 772
 773 void
 774 Lang::Edge::gcMark( Kernel::GCMarkedSet & marked )
 775 {
 776         const_cast< Lang::Graph * >( graph_.getPtr( ) )->gcMark( marked );
 777 }
 778
 779
 780 Lang::MultiEdge::MultiEdge( const RefCountPtr< const Lang::Graph > & graph, bool directed, const Kernel::Node * source, const Kernel::Node * target, size_t count, const SetType::const_iterator & begin, const SetType::const_iterator & end )
 781         : graph_( graph ), directed_( directed ), source_( source ), target_( target ), count_( count ), begin_( begin ), end_( end )
 782 {
 783         if( count_ == 0 ){
 784                 throw Exceptions::InternalError( "Lang::MultiEdge::MultiEdge: The multiplicity of a multiedge must not be zero." );
 785         }
 786         if( ! directed && source_->index( ) > target_->index( ) ){
 787                 const Kernel::Node * tmp = target_;
 788                 target_ = source_;
 789                 source_ = tmp;
 790         }
 791 }
 792
 793 Lang::MultiEdge::~MultiEdge( )
 794 { }
 795
 796 void
 797 MultiEdge_register_methods( Lang::SystemFinalClass * dstClass )
 798 {
 799         dstClass->registerMethod( new Kernel::MethodFactory< Lang::MultiEdge, Lang::Method_get_graph< Lang::MultiEdge > >( ) );
 800 }
 801
 802 RefCountPtr< const Lang::Class > Lang::MultiEdge::TypeID( new Lang::SystemFinalClass( strrefdup( "MultiEdge" ), MultiEdge_register_methods ) );
 803 TYPEINFOIMPL( MultiEdge );
 804
 805 const Kernel::Node *
 806 Lang::MultiEdge::trace( const Kernel::Node * sourceArg, bool nullOnError ) const
 807 {
 808         if( directed_ ) {
 809                 if( sourceArg == source_ )
 810                         return target_;
 811                 else if( nullOnError )
 812                         return NULL;
 813                 else
 814                         throw Exceptions::InternalError( "Edge trace error." );
 815         } else {
 816                 if( sourceArg == source_ )
 817                         return target_;
 818                 if( sourceArg == target_ )
 819                         return source_;
 820                 else if( nullOnError )
 821                         return NULL;
 822                 else
 823                         throw Exceptions::InternalError( "Edge trace error." );
 824         }
 825 }
 826
 827 const Kernel::Node *
 828 Lang::MultiEdge::trace( const Kernel::Node * sourceArg, const Ast::SourceLocation & callLoc ) const
 829 {
 830         const Kernel::Node * res = trace( sourceArg, true );
 831         if( res != 0 )
 832                 return res;
 833         throw Exceptions::EdgeTraceError( directed_ ? Exceptions::EdgeTraceError::TRACE : Exceptions::EdgeTraceError::UNDIRECTED,
 834                                                                                                                                                 source_->key( ), target_->key( ),
 835                                                                                                                                                 sourceArg->key( ),
 836                                                                                                                                                 callLoc );
 837 }
 838
 839 const Kernel::Node *
 840 Lang::MultiEdge::backtrace( const Kernel::Node * targetArg, bool nullOnError ) const
 841 {
 842         if( directed_ ) {
 843                 if( targetArg == target_ )
 844                         return source_;
 845                 else if( nullOnError )
 846                         return NULL;
 847                 else
 848                         throw Exceptions::InternalError( "Edge trace error." );
 849         } else {
 850                 if( targetArg == source_ )
 851                         return target_;
 852                 if( targetArg == target_ )
 853                         return source_;
 854                 else if( nullOnError )
 855                         return NULL;
 856                 else
 857                         throw Exceptions::InternalError( "Edge trace error." );
 858         }
 859 }
 860
 861 const Kernel::Node *
 862 Lang::MultiEdge::backtrace( const Kernel::Node * targetArg, const Ast::SourceLocation & callLoc ) const
 863 {
 864         const Kernel::Node * res = backtrace( targetArg, true );
 865         if( res != 0 )
 866                 return res;
 867         throw Exceptions::EdgeTraceError( directed_ ? Exceptions::EdgeTraceError::BACKTRACE : Exceptions::EdgeTraceError::UNDIRECTED,
 868                                                                                                                                                 source_->key( ), target_->key( ),
 869                                                                                                                                                 targetArg->key( ),
 870                                                                                                                                                 callLoc );
 871 }
 872
 873 RefCountPtr< const Lang::SingleList >
 874 Lang::MultiEdge::edges( ) const
 875 {
 876         /* Unfortunately, we can only access the edges in order of increasing node indices, and we want
 877          * to return the edges in the same order.  This requires a temporary storage since the result
 878          * must be built in reverse order.
 879          */
 880         std::stack< const Kernel::Edge * > revStack;
 881         for( SetType::const_iterator i = begin_; i != end_; ++i ){
 882                 revStack.push( *i );
 883         }
 884         RefCountPtr< const Lang::SingleList > res = Lang::THE_CONS_NULL;
 885         while( ! revStack.empty( ) ){
 886                 res = Helpers::SingleList_cons( new Lang::Edge( graph_, revStack.top( ), directed_ ), res );
 887                 revStack.pop( );
 888         }
 889         return res;
 890 }
 891
 892 void
 893 Lang::MultiEdge::show( std::ostream & os ) const
 894 {
 895         if( directed_ ){
 896                 os << "< directed multiedge ( " ;
 897                 source_->key( )->show( os );
 898                 os << ", " ;
 899                 target_->key( )->show( os );
 900                 os << " ) of multiplicity " << count_ << " >" ;
 901         }else{
 902                 os << "< undirected multiedge ( " ;
 903                 source_->key( )->show( os );
 904                 os << ", " ;
 905                 target_->key( )->show( os );
 906                 os << " ) of multiplicity " << count_ << " >" ;
 907         }
 908 }
 909
 910 Kernel::VariableHandle
 911 Lang::MultiEdge::getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const
 912 {
 913         if( strcmp( fieldID, "directed?" ) == 0 )
 914                 {
 915                         return directed_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
 916                 }
 917         if( strcmp( fieldID, "source" ) == 0 )
 918                 {
 919                         return Helpers::newValHandle( new Lang::Node( graph_, source_ ) );
 920                 }
 921         if( strcmp( fieldID, "target" ) == 0 )
 922                 {
 923                         return Helpers::newValHandle( new Lang::Node( graph_, target_ ) );
 924                 }
 925         if( strcmp( fieldID, "count" ) == 0 )
 926                 {
 927                         return Helpers::newValHandle( new Lang::Integer( count_ ) );
 928                 }
 929         if( strcmp( fieldID, "edges" ) == 0 )
 930                 {
 931                         return Kernel::VariableHandle( new Kernel::Variable( edges( ) ) );
 932                 }
 933         if( strcmp( fieldID, "u_edges" ) == 0 )
 934                 {
 935                         if( directed_ )
 936                                 throw Exceptions::MiscellaneousRequirement( "Illegal to access the u_edges field of a directed multiedge." );
 937                         return Kernel::VariableHandle( new Kernel::Variable( edges( ) ) );
 938                 }
 939         if( strcmp( fieldID, "d_edges" ) == 0 )
 940                 {
 941                         if( ! directed_ )
 942                                 throw Exceptions::MiscellaneousRequirement( "Illegal to access the d_edges field of an undirected multiedge." );
 943                         return Kernel::VariableHandle( new Kernel::Variable( edges( ) ) );
 944                 }
 945         return TypeID->getMethod( selfRef, fieldID ); /* This will throw if there is no such method. */
 946 }
 947
 948 void
 949 Lang::MultiEdge::gcMark( Kernel::GCMarkedSet & marked )
 950 {
 951         const_cast< Lang::Graph * >( graph_.getPtr( ) )->gcMark( marked );
 952 }
 953
 954
 955 namespace Shapes
 956 {
 957         namespace Lang
 958         {
 959
 960                 template< bool onlyCount, const char * fieldID >
 961                 class GraphMethod_partition : public Lang::MethodBase< Lang::Graph >
 962                 {
 963                 public:
 964                         GraphMethod_partition( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
 965                         virtual ~GraphMethod_partition( );
 966                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 967                         static const char * staticFieldID( ) { return fieldID; }
 968                 };
 969
 970                 class GraphMethod_isNode : public Lang::MethodBase< Lang::Graph >
 971                 {
 972                 public:
 973                         GraphMethod_isNode( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
 974                         virtual ~GraphMethod_isNode( );
 975                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 976                         static const char * staticFieldID( ) { return "node?"; }
 977                 };
 978
 979                 class GraphMethod_isEdge : public Lang::MethodBase< Lang::Graph >
 980                 {
 981                 public:
 982                         GraphMethod_isEdge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
 983                         virtual ~GraphMethod_isEdge( );
 984                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 985                         static const char * staticFieldID( ) { return "edge?"; }
 986                 };
 987
 988                 class GraphMethod_isKey : public Lang::MethodBase< Lang::Graph >
 989                 {
 990                 public:
 991                         GraphMethod_isKey( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
 992                         virtual ~GraphMethod_isKey( );
 993                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
 994                         static const char * staticFieldID( ) { return "key?"; }
 995                 };
 996
 997                 class GraphMethod_indexNode : public Lang::MethodBase< Lang::Graph >
 998                 {
 999                 public:
1000                         GraphMethod_indexNode( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1001                         virtual ~GraphMethod_indexNode( );
1002                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1003                         static const char * staticFieldID( ) { return "index_node"; }
1004                 };
1005
1006                 class GraphMethod_indexEdge : public Lang::MethodBase< Lang::Graph >
1007                 {
1008                 public:
1009                         GraphMethod_indexEdge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1010                         virtual ~GraphMethod_indexEdge( );
1011                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1012                         static const char * staticFieldID( ) { return "index_edge"; }
1013                 };
1014
1015                 class GraphMethod_find_node : public Lang::MethodBase< Lang::Graph >
1016                 {
1017                 public:
1018                         GraphMethod_find_node( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1019                         virtual ~GraphMethod_find_node( );
1020                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1021                         static const char * staticFieldID( ) { return "find_node"; }
1022                 };
1023
1024                 template< bool directed, bool undirected, const char * fieldID >
1025                 class GraphMethod_find_edges : public Lang::MethodBase< Lang::Graph >
1026                 {
1027                 public:
1028                         GraphMethod_find_edges( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1029                         virtual ~GraphMethod_find_edges( );
1030                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1031                         static const char * staticFieldID( ) { return fieldID; }
1032                 };
1033
1034                 template< bool directed, bool undirected, const char * fieldID >
1035                 class GraphMethod_find_multiedges : public Lang::MethodBase< Lang::Graph >
1036                 {
1037                 public:
1038                         GraphMethod_find_multiedges( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1039                         virtual ~GraphMethod_find_multiedges( );
1040                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1041                         static const char * staticFieldID( ) { return fieldID; }
1042                 };
1043
1044                 template< bool directed, bool undirected, const char * fieldID >
1045                 class GraphMethod_the_edge : public Lang::MethodBase< Lang::Graph >
1046                 {
1047                 public:
1048                         GraphMethod_the_edge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1049                         virtual ~GraphMethod_the_edge( );
1050                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1051                         static const char * staticFieldID( ) { return fieldID; }
1052                 };
1053
1054                 template< bool directed, bool undirected, const char * fieldID >
1055                 class GraphMethod_the_multiedge : public Lang::MethodBase< Lang::Graph >
1056                 {
1057                 public:
1058                         GraphMethod_the_multiedge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1059                         virtual ~GraphMethod_the_multiedge( );
1060                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1061                         static const char * staticFieldID( ) { return fieldID; }
1062                 };
1063
1064                 template< Kernel::Graph::ItemType item, const char * fieldID >
1065                 class GraphMethod_with_values : public Lang::MethodBase< Lang::Graph >
1066                 {
1067                 public:
1068                         GraphMethod_with_values( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1069                         virtual ~GraphMethod_with_values( );
1070                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1071                         static const char * staticFieldID( ) { return fieldID; }
1072                 };
1073
1074                 class GraphMethod_rekey_with_index : public Lang::MethodBase< Lang::Graph >
1075                 {
1076                 public:
1077                         GraphMethod_rekey_with_index( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1078                         virtual ~GraphMethod_rekey_with_index( );
1079                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1080                         static const char * staticFieldID( ) { return "rekey_with_index"; }
1081                 };
1082
1083                 template< Kernel::Graph::SubgraphKind kind, const char * fieldID >
1084                 class GraphMethod_subgraph : public Lang::MethodBase< Lang::Graph >
1085                 {
1086                 public:
1087                         GraphMethod_subgraph( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID );
1088                         virtual ~GraphMethod_subgraph( );
1089                         virtual void call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const;
1090                         static const char * staticFieldID( ) { return fieldID; }
1091                 };
1092
1093         }
1094
1095         namespace Kernel
1096         {
1097                 char FIELD_ID_partition[]         = "partition";
1098                 char FIELD_ID_partition_node_count[] = "partition_node_count";
1099                 char FIELD_ID_find_u_edges[]      = "find_u_edges";
1100                 char FIELD_ID_find_d_edges[]      = "find_d_edges";
1101                 char FIELD_ID_the_u_edge[]        = "the_u_edge";
1102                 char FIELD_ID_the_d_edge[]        = "the_d_edge";
1103                 char FIELD_ID_find_u_multiedges[] = "find_u_multiedges";
1104                 char FIELD_ID_find_d_multiedges[] = "find_d_multiedges";
1105                 char FIELD_ID_the_u_multiedge[]   = "the_u_multiedge";
1106                 char FIELD_ID_the_d_multiedge[]   = "the_d_multiedge";
1107                 char FIELD_ID_with_node_values[]  = "with_node_values";
1108                 char FIELD_ID_with_edge_values[]  = "with_edge_values";
1109                 char FIELD_ID_induced_subgraph[]  = "induced_subgraph";
1110                 char FIELD_ID_spanning_subgraph[] = "spanning_subgraph";
1111         }
1112 }
1113
1114 Kernel::Graph::Graph( const Kernel::GraphDomain & domain, const ListRef & partitionKeys, const std::list< Kernel::NodeData > & nodeData, bool hasEdgeLabels, const std::list< Kernel::EdgeDataIndexed > & uedgeData, const std::list< Kernel::EdgeDataIndexed > & dedgeData, const std::list< Kernel::LoopDataIndexed > & uloopData, const std::list< Kernel::LoopDataIndexed > & dloopData, RefCountPtr< const ValueVector > * nodeValues, RefCountPtr< const ValueVector > * edgeValues, const Ast::SourceLocation & callLoc )
1115         : domain_( domain ), partitionKeys_( partitionKeys ), keyIsRange_( true ), keyOffset_( 0 ),
1116           edgeLabels_( NullPtr< std::vector< Kernel::ValueRef > >( ) ), nodePartitions_( NullPtr< std::vector< Kernel::ValueRef > >( ) )
1117 {
1118         size_t nCount = nodeData.size( );
1119         size_t eCount = uedgeData.size( ) + dedgeData.size( ) + uloopData.size( ) + dloopData.size( );
1120
1121         bool partitionedCache = partitioned( ); /* For fast access. */
1122
1123         nodes_.reserve( nCount );
1124         uedges_.reserve( uedgeData.size( ) );
1125         dedges_.reserve( dedgeData.size( ) );
1126         uloops_.reserve( uloopData.size( ) );
1127         dloops_.reserve( dloopData.size( ) );
1128
1129         RefCountPtr< ValueVector > nValues = RefCountPtr< ValueVector >( NullPtr< ValueVector >( ) );
1130         RefCountPtr< ValueVector > eValues = RefCountPtr< ValueVector >( NullPtr< ValueVector >( ) );
1131
1132         if( hasEdgeLabels ){
1133                 edgeLabels_ = RefCountPtr< std::vector< Kernel::ValueRef > >( new std::vector< Kernel::ValueRef >( ) );
1134                 edgeLabels_->reserve( eCount );
1135         }
1136
1137         if( partitionedCache ){
1138                 nodePartitions_ = RefCountPtr< ValueVector >( new ValueVector( nCount, NullPtr< const Lang::Value >( ) ) );
1139         }
1140
1141         {
1142                 typedef typeof nodeData ListType;
1143                 size_t ni = 0;
1144                 for( ListType::const_iterator n = nodeData.begin( ); n != nodeData.end( ); ++n, ++ni ){
1145                         nodes_.push_back( new Kernel::Node( ni, n->key_ ) );
1146                         if( n->value_ != NullPtr< const Lang::Value >( ) ){
1147                                 if( nValues == NullPtr< ValueVector >( ) ){
1148                                         nValues = RefCountPtr< ValueVector >( new ValueVector( nCount, NullPtr< const Lang::Value >( ) ) );
1149                                 }
1150                                 (*nValues)[ ni ] = n->value_;
1151                         }
1152                         if( partitionedCache ){
1153                                 /* The caller of this constructor is responsible for the content of the partition_ member
1154                                  * to be correct if the graph is partitioned.
1155                                  */
1156                                 (*nodePartitions_)[ ni ] = n->partition_;
1157                         }
1158                 }
1159         }
1160
1161         /* The edge indices are determined by the order in which the various kinds of edges are processed here.
1162          * Note that this order must be reflected correctly in the indexEdge method, and must match the order
1163          * used in other graph constructors.
1164          */
1165         size_t ei = 0;
1166         {
1167                 typedef typeof uedgeData ListType;
1168                 for( ListType::const_iterator e = uedgeData.begin( ); e != uedgeData.end( ); ++e, ++ei ){
1169                         if( e->source_ >= nCount || e->target_ >= nCount )
1170                                 throw Exceptions::InternalError( "Lang::Graph::Graph: Node index in undirected edge is out of range." );
1171                         uedges_.push_back( new Kernel::Edge( nodes_[e->source_], nodes_[e->target_], ei, false ) );
1172                         if( e->value_ != NullPtr< const Lang::Value >( ) ){
1173                                 if( eValues == NullPtr< ValueVector >( ) ){
1174                                         eValues = RefCountPtr< ValueVector >( new ValueVector( eCount, NullPtr< const Lang::Value >( ) ) );
1175                                 }
1176                                 (*eValues)[ ei ] = e->value_;
1177                         }
1178                         if( hasEdgeLabels ){
1179                                 edgeLabels_->push_back( e->label_ );
1180                         }
1181                 }
1182         }
1183         {
1184                 typedef typeof dedgeData ListType;
1185                 for( ListType::const_iterator e = dedgeData.begin( ); e != dedgeData.end( ); ++e, ++ei ){
1186                         if( e->source_ >= nCount || e->target_ >= nCount )
1187                                 throw Exceptions::InternalError( "Lang::Graph::Graph: Node index in directed edge is out of range." );
1188                         dedges_.push_back( new Kernel::Edge( nodes_[e->source_], nodes_[e->target_], ei, true) );
1189                         if( e->value_ != NullPtr< const Lang::Value >( ) ){
1190                                 if( eValues == NullPtr< ValueVector >( ) ){
1191                                         eValues = RefCountPtr< ValueVector >( new ValueVector( eCount, NullPtr< const Lang::Value >( ) ) );
1192                                 }
1193                                 (*eValues)[ ei ] = e->value_;
1194                         }
1195                         if( hasEdgeLabels ){
1196                                 edgeLabels_->push_back( e->label_ );
1197                         }
1198                 }
1199         }
1200         {
1201                 typedef typeof uloopData ListType;
1202                 for( ListType::const_iterator e = uloopData.begin( ); e != uloopData.end( ); ++e, ++ei ){
1203                         if( e->node_ >= nCount )
1204                                 throw Exceptions::InternalError( "Lang::Graph::Graph: Node index in undirected loop is out of range." );
1205                         uedges_.push_back( new Kernel::Edge( nodes_[e->node_], nodes_[e->node_], ei, false ) );
1206                         if( e->value_ != NullPtr< const Lang::Value >( ) ){
1207                                 if( eValues == NullPtr< ValueVector >( ) ){
1208                                         eValues = RefCountPtr< ValueVector >( new ValueVector( eCount, NullPtr< const Lang::Value >( ) ) );
1209                                 }
1210                                 (*eValues)[ ei ] = e->value_;
1211                         }
1212                         if( hasEdgeLabels ){
1213                                 edgeLabels_->push_back( e->label_ );
1214                         }
1215                 }
1216         }
1217         {
1218                 typedef typeof dloopData ListType;
1219                 for( ListType::const_iterator e = dloopData.begin( ); e != dloopData.end( ); ++e, ++ei ){
1220                         if( e->node_ >= nCount )
1221                                 throw Exceptions::InternalError( "Lang::Graph::Graph: Node index in directed loop is out of range." );
1222                         uedges_.push_back( new Kernel::Edge( nodes_[e->node_], nodes_[e->node_], ei, true ) );
1223                         if( e->value_ != NullPtr< const Lang::Value >( ) ){
1224                                 if( eValues == NullPtr< ValueVector >( ) ){
1225                                         eValues = RefCountPtr< ValueVector >( new ValueVector( eCount, NullPtr< const Lang::Value >( ) ) );
1226                                 }
1227                                 (*eValues)[ ei ] = e->value_;
1228                         }
1229                         if( hasEdgeLabels ){
1230                                 edgeLabels_->push_back( e->label_ );
1231                         }
1232                 }
1233         }
1234
1235         *nodeValues = nValues;
1236         *edgeValues = eValues;
1237
1238         initializeKeyRangeOffset( );
1239         initializeKeyMaps( );
1240         initializeAndCheckPartitions( callLoc );
1241         addEdgesToNodes( );
1242 }
1243
1244 Kernel::Graph::Graph( const Kernel::Graph & orig, const std::set< size_t > & subgraphIndices, SubgraphKind kind,
1245                                                                                         const RefCountPtr< const ValueVector > & origNodeValues, const RefCountPtr< const ValueVector > & origEdgeValues,
1246                                                                                         RefCountPtr< const ValueVector > * nodeValues, RefCountPtr< const ValueVector > * edgeValues )
1247         : domain_( orig.domain_ ), partitionKeys_( orig.partitionKeys_ ), keyIsRange_( true ), keyOffset_( 0 ),
1248           edgeLabels_( NullPtr< std::vector< Kernel::ValueRef > >( ) ), nodePartitions_( NullPtr< std::vector< Kernel::ValueRef > >( ) )
1249 {
1250         switch( kind )
1251                 {
1252                 case INDUCED:
1253                         initSubgraphInduced( orig, subgraphIndices, origNodeValues, origEdgeValues, nodeValues, edgeValues );
1254                         break;
1255                 case SPANNING:
1256                         initSubgraphSpanning( orig, subgraphIndices, origNodeValues, origEdgeValues, nodeValues, edgeValues );
1257                         break;
1258                 }
1259
1260         initializeKeyRangeOffset( );
1261         initializeKeyMaps( );
1262         initializeAndCheckPartitions( Ast::THE_UNKNOWN_LOCATION ); /* The call location should never be used here, since nothing can go wrong. */
1263         addEdgesToNodes( );
1264 }
1265
1266 void
1267 Kernel::Graph::initSubgraphInduced( const Kernel::Graph & orig, const std::set< size_t > & subgraphNodeIndices, const RefCountPtr< const ValueVector > & origNodeValues, const RefCountPtr< const ValueVector > & origEdgeValues, RefCountPtr< const ValueVector > * nodeValues, RefCountPtr< const ValueVector > * edgeValues )
1268 {
1269         size_t nCount = subgraphNodeIndices.size( );
1270
1271         typedef std::map< size_t, size_t > IndexMap;
1272         IndexMap indexMap;
1273
1274         bool hasNodeValues = origNodeValues != NullPtr< const ValueVector >( );
1275         bool hasNodePartitions = partitioned( );
1276         bool hasEdgeValues = origEdgeValues != NullPtr< const ValueVector >( );
1277         bool hasEdgeLabels = orig.edgeLabels_ != NullPtr< std::vector< Kernel::ValueRef > >( );
1278
1279         RefCountPtr< ValueVector > nValues = RefCountPtr< ValueVector >( NullPtr< ValueVector >( ) );
1280         RefCountPtr< ValueVector > eValues = RefCountPtr< ValueVector >( NullPtr< ValueVector >( ) );
1281
1282         if( hasNodeValues ){
1283                 nValues = RefCountPtr< ValueVector >( new ValueVector( nCount, NullPtr< const Lang::Value >( ) ) );
1284         }
1285         if( hasNodePartitions ){
1286                 nodePartitions_ = RefCountPtr< ValueVector >( new ValueVector( nCount, NullPtr< const Lang::Value >( ) ) );
1287         }
1288
1289         nodes_.reserve( nCount );
1290         {
1291                 typedef typeof subgraphNodeIndices SetType;
1292                 size_t ni = 0;
1293                 for( SetType::const_iterator i = subgraphNodeIndices.begin( ); i != subgraphNodeIndices.end( ); ++i, ++ni ){
1294                         const Kernel::Node * orign = orig.nodes_[ *i ];
1295                         nodes_.push_back( new Kernel::Node( ni, orign->key( ) ) );
1296                         indexMap[ *i ] = ni;
1297                         if( hasNodeValues ){
1298                                 (*nValues)[ ni ] = (*origNodeValues)[ *i ];
1299                         }
1300                         if( hasNodePartitions ){
1301                                 (*nodePartitions_)[ ni ] = (*orig.nodePartitions_)[ *i ];
1302                         }
1303                 }
1304         }
1305
1306         std::list< size_t > origEdgeIndices;
1307
1308         /* The edge indices are determined by the order in which the various kinds of edges are processed here.
1309          * Note that this order must be reflected correctly in the indexEdge method, and must match the order
1310          * used in other graph constructors.
1311          */
1312         size_t ei = 0;
1313         for( EdgeVector::const_iterator e = orig.uedges_.begin( ); e != orig.uedges_.end( ); ++e ){
1314                 IndexMap::const_iterator iSource = indexMap.find( (*e)->source( )->index( ) );
1315                 if( iSource == indexMap.end( ) )
1316                         continue;
1317                 IndexMap::const_iterator iTarget = indexMap.find( (*e)->target( )->index( ) );
1318                 if( iTarget == indexMap.end( ) )
1319                         continue;
1320                 uedges_.push_back( new Kernel::Edge( nodes_[ iSource->second ], nodes_[ iTarget->second ], ei, false ) );
1321                 if( hasEdgeValues ){
1322                         origEdgeIndices.push_back( (*e)->index( ) );
1323                 }
1324                 ++ei;
1325         }
1326         for( EdgeVector::const_iterator e = orig.dedges_.begin( ); e != orig.dedges_.end( ); ++e ){
1327                 IndexMap::const_iterator iSource = indexMap.find( (*e)->source( )->index( ) );
1328                 if( iSource == indexMap.end( ) )
1329                         continue;
1330                 IndexMap::const_iterator iTarget = indexMap.find( (*e)->target( )->index( ) );
1331                 if( iTarget == indexMap.end( ) )
1332                         continue;
1333                 dedges_.push_back( new Kernel::Edge( nodes_[ iSource->second ], nodes_[ iTarget->second ], ei, true ) );
1334                 if( hasEdgeValues ){
1335                         origEdgeIndices.push_back( (*e)->index( ) );
1336                 }
1337                 ++ei;
1338         }
1339         for( EdgeVector::const_iterator e = orig.uloops_.begin( ); e != orig.uloops_.end( ); ++e ){
1340                 IndexMap::const_iterator iSource = indexMap.find( (*e)->source( )->index( ) );
1341                 if( iSource == indexMap.end( ) )
1342                         continue;
1343                 uloops_.push_back( new Kernel::Edge( nodes_[ iSource->second ], nodes_[ iSource->second ], ei, false ) );
1344                 if( hasEdgeValues ){
1345                         origEdgeIndices.push_back( (*e)->index( ) );
1346                 }
1347                 ++ei;
1348         }
1349         for( EdgeVector::const_iterator e = orig.dloops_.begin( ); e != orig.dloops_.end( ); ++e ){
1350                 IndexMap::const_iterator iSource = indexMap.find( (*e)->source( )->index( ) );
1351                 if( iSource == indexMap.end( ) )
1352                         continue;
1353                 dloops_.push_back( new Kernel::Edge( nodes_[ iSource->second ], nodes_[ iSource->second ], ei, true ) );
1354                 if( hasEdgeValues ){
1355                         origEdgeIndices.push_back( (*e)->index( ) );
1356                 }
1357                 ++ei;
1358         }
1359
1360         if( hasEdgeValues ){
1361                 eValues = RefCountPtr< ValueVector >( new ValueVector( ei, NullPtr< const Lang::Value >( ) ) );
1362                 typedef typeof origEdgeIndices ListType;
1363                 ValueVector::iterator dst = eValues->begin( );
1364                 for( ListType::const_iterator i = origEdgeIndices.begin( ); i != origEdgeIndices.end( ); ++i, ++dst ){
1365                         *dst = (*origEdgeValues)[ *i ];
1366                 }
1367         }
1368         if( hasEdgeLabels ){
1369                 edgeLabels_ = RefCountPtr< std::vector< Kernel::ValueRef > >( new std::vector< Kernel::ValueRef >( ei, NullPtr< const Lang::Value >( ) ) );
1370                 const std::vector< Kernel::ValueRef > & origEdgeLabels = *(orig.edgeLabels_);
1371                 typedef typeof origEdgeIndices ListType;
1372                 std::vector< Kernel::ValueRef >::iterator dst = edgeLabels_->begin( );
1373                 for( ListType::const_iterator i = origEdgeIndices.begin( ); i != origEdgeIndices.end( ); ++i, ++dst ){
1374                         *dst = origEdgeLabels[ *i ];
1375                 }
1376         }
1377
1378         *nodeValues = nValues;
1379         *edgeValues = eValues;
1380 }
1381
1382 void
1383 Kernel::Graph::initSubgraphSpanning( const Kernel::Graph & orig, const std::set< size_t > & subgraphEdgeIndices, const RefCountPtr< const ValueVector > & origNodeValues, const RefCountPtr< const ValueVector > & origEdgeValues, RefCountPtr< const ValueVector > * nodeValues, RefCountPtr< const ValueVector > * edgeValues )
1384 {
1385         const std::vector< Kernel::ValueRef > * origEdgeLabels = orig.edgeLabels_.getPtr( );
1386
1387         bool hasEdgeValues = origEdgeValues != NullPtr< const ValueVector >( );
1388         bool hasEdgeLabels = origEdgeLabels != 0;
1389
1390         nodes_.reserve( orig.nodes_.size( ) );
1391         {
1392                 for( NodeVector::const_iterator n = orig.nodes_.begin( ); n != orig.nodes_.end( ); ++n ) {
1393                         nodes_.push_back( new Kernel::Node( (*n)->index( ), (*n)->key( ) ) );
1394                 }
1395         }
1396
1397         *nodeValues = origNodeValues;
1398         nodePartitions_ = orig.nodePartitions_;
1399
1400         RefCountPtr< ValueVector > eValues = RefCountPtr< ValueVector >( NullPtr< ValueVector >( ) );
1401         if( hasEdgeValues ){
1402                 eValues = RefCountPtr< ValueVector >( new ValueVector( subgraphEdgeIndices.size( ), NullPtr< const Lang::Value >( ) ) );
1403         }
1404         if( hasEdgeLabels ){
1405                 edgeLabels_ = RefCountPtr< std::vector< Kernel::ValueRef > >( new std::vector< Kernel::ValueRef >( subgraphEdgeIndices.size( ), NullPtr< const Lang::Value >( ) ) );
1406         }
1407
1408         typedef typeof subgraphEdgeIndices SetType;
1409         SetType::const_iterator i = subgraphEdgeIndices.begin( );
1410
1411         size_t ei = 0;
1412         size_t offset = 0;
1413         size_t iMax = orig.uedges_.size( );
1414         for( ; i != subgraphEdgeIndices.end( ) && *i < iMax; ++i, ++ei ){
1415                 const Kernel::Edge * orige = orig.uedges_[ *i - offset ];
1416                 uedges_.push_back( new Kernel::Edge( nodes_[ orige->source( )->index( ) ], nodes_[ orige->target( )->index( ) ], ei, false ) );
1417                 if( hasEdgeValues ){
1418                         (*eValues)[ ei ] = (*origEdgeValues)[ orige->index( ) ];
1419                 }
1420                 if( hasEdgeLabels ){
1421                         (*edgeLabels_)[ ei ] = (*origEdgeLabels)[ orige->index( ) ];
1422                 }
1423         }
1424
1425         offset = iMax;
1426         iMax += orig.dedges_.size( );
1427         for( ; i != subgraphEdgeIndices.end( ) && *i < iMax; ++i, ++ei ){
1428                 const Kernel::Edge * orige = orig.dedges_[ *i - offset ];
1429                 dedges_.push_back( new Kernel::Edge( nodes_[ orige->source( )->index( ) ], nodes_[ orige->target( )->index( ) ], ei, true ) );
1430                 if( hasEdgeValues ){
1431                         (*eValues)[ ei ] = (*origEdgeValues)[ orige->index( ) ];
1432                 }
1433                 if( hasEdgeLabels ){
1434                         (*edgeLabels_)[ ei ] = (*origEdgeLabels)[ orige->index( ) ];
1435                 }
1436         }
1437
1438         offset = iMax;
1439         iMax += orig.uloops_.size( );
1440         for( ; i != subgraphEdgeIndices.end( ) && *i < iMax; ++i, ++ei ){
1441                 const Kernel::Edge * orige = orig.uloops_[ *i - offset ];
1442                 uloops_.push_back( new Kernel::Edge( nodes_[ orige->source( )->index( ) ], nodes_[ orige->target( )->index( ) ], ei, false ) );
1443                 if( hasEdgeValues ){
1444                         (*eValues)[ ei ] = (*origEdgeValues)[ orige->index( ) ];
1445                 }
1446                 if( hasEdgeLabels ){
1447                         (*edgeLabels_)[ ei ] = (*origEdgeLabels)[ orige->index( ) ];
1448                 }
1449         }
1450
1451         offset = iMax;
1452         iMax += orig.dloops_.size( );
1453         for( ; i != subgraphEdgeIndices.end( ) && *i < iMax; ++i, ++ei ){
1454                 const Kernel::Edge * orige = orig.dloops_[ *i - offset ];
1455                 dloops_.push_back( new Kernel::Edge( nodes_[ orige->source( )->index( ) ], nodes_[ orige->target( )->index( ) ], ei, true ) );
1456                 if( hasEdgeValues ){
1457                         (*eValues)[ ei ] = (*origEdgeValues)[ orige->index( ) ];
1458                 }
1459                 if( hasEdgeLabels ){
1460                         (*edgeLabels_)[ ei ] = (*origEdgeLabels)[ orige->index( ) ];
1461                 }
1462         }
1463
1464         if( i != subgraphEdgeIndices.end( ) )
1465                 throw Exceptions::InternalError( "Lang::Graph::initSubgraphSpanning: subgraph edge indices out of range" );
1466
1467         *edgeValues = eValues;
1468 }
1469
1470 Kernel::Graph::Graph( const Kernel::Graph & orig, Lang::Integer::ValueType offset )
1471         : domain_( orig.domain_ ), partitionKeys_( orig.partitionKeys_ ), keyIsRange_( true ), keyOffset_( offset ),
1472           edgeLabels_( orig.edgeLabels_ ), nodePartitions_( orig.nodePartitions_ )
1473 {
1474         /* Rekey with index. */
1475
1476         nodes_.reserve( orig.nodes_.size( ) );
1477         uedges_.reserve( orig.uedges_.size( ) );
1478         dedges_.reserve( orig.dedges_.size( ) );
1479         uloops_.reserve( orig.uloops_.size( ) );
1480         dloops_.reserve( orig.dloops_.size( ) );
1481
1482         {
1483                 size_t ni = 0;
1484                 for( NodeVector::const_iterator n = orig.nodes_.begin( ); n != orig.nodes_.end( ); ++n, ++ni ) {
1485                         nodes_.push_back( new Kernel::Node( ni, Kernel::ValueRef( new Lang::Integer( ni + offset ) ) ) );
1486                 }
1487         }
1488
1489         /* The edge indices are determined by the order in which the various kinds of edges are processed here.
1490          * Note that this order must be reflected correctly in the indexEdge method, and must match the order
1491          * used in other graph constructors.
1492          */
1493         for( EdgeVector::const_iterator e = orig.uedges_.begin( ); e != orig.uedges_.end( ); ++e ){
1494                 uedges_.push_back( new Kernel::Edge( nodes_[ (*e)->source( )->index( ) ], nodes_[ (*e)->target( )->index( ) ], (*e)->index( ), false ) );
1495         }
1496         for( EdgeVector::const_iterator e = orig.dedges_.begin( ); e != orig.dedges_.end( ); ++e ){
1497                 dedges_.push_back( new Kernel::Edge( nodes_[ (*e)->source( )->index( ) ], nodes_[ (*e)->target( )->index( ) ], (*e)->index( ), true ) );
1498         }
1499         for( EdgeVector::const_iterator e = orig.uloops_.begin( ); e != orig.uloops_.end( ); ++e ){
1500                 uloops_.push_back( new Kernel::Edge( nodes_[ (*e)->source( )->index( ) ], nodes_[ (*e)->source( )->index( ) ], (*e)->index( ), false ) );
1501         }
1502         for( EdgeVector::const_iterator e = orig.dloops_.begin( ); e != orig.dloops_.end( ); ++e ){
1503                 dloops_.push_back( new Kernel::Edge( nodes_[ (*e)->source( )->index( ) ], nodes_[ (*e)->source( )->index( ) ], (*e)->index( ), true ) );
1504         }
1505
1506         initializeKeyMaps( );
1507         initializeAndCheckPartitions( Ast::THE_UNKNOWN_LOCATION ); /* The call location should never be used here, since nothing can go wrong. */
1508         addEdgesToNodes( );
1509 }
1510
1511 Kernel::Graph::~Graph( )
1512 {
1513         for( EdgeVector::iterator e = uedges_.begin( ); e != uedges_.end( ); ++e )
1514                 delete *e;
1515         for( EdgeVector::iterator e = uloops_.begin( ); e != uloops_.end( ); ++e )
1516                 delete *e;
1517         for( EdgeVector::iterator e = dedges_.begin( ); e != dedges_.end( ); ++e )
1518                 delete *e;
1519         for( EdgeVector::iterator e = dloops_.begin( ); e != dloops_.end( ); ++e )
1520                 delete *e;
1521         for( NodeVector::iterator n = nodes_.begin( ); n != nodes_.end( ); ++n )
1522                 delete *n;
1523 }
1524
1525 void
1526 Graph_register_methods( Lang::SystemFinalClass * dstClass )
1527 {
1528         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_partition< false, Kernel::FIELD_ID_partition > >( ) );
1529         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_partition< true, Kernel::FIELD_ID_partition_node_count > >( ) );
1530         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_isNode >( ) );
1531         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_isEdge >( ) );
1532         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_isKey >( ) );
1533         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_indexNode >( ) );
1534         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_indexEdge >( ) );
1535         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_find_node >( ) );
1536         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_find_edges< false, true, Kernel::FIELD_ID_find_u_edges > >( ) );
1537         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_find_edges< true, false, Kernel::FIELD_ID_find_d_edges > >( ) );
1538         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_the_edge< false, true, Kernel::FIELD_ID_the_u_edge > >( ) );
1539         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_the_edge< true, false, Kernel::FIELD_ID_the_d_edge > >( ) );
1540
1541         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_find_multiedges< false, true, Kernel::FIELD_ID_find_u_multiedges > >( ) );
1542         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_find_multiedges< true, false, Kernel::FIELD_ID_find_d_multiedges > >( ) );
1543         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_the_multiedge< false, true, Kernel::FIELD_ID_the_u_multiedge > >( ) );
1544         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_the_multiedge< true, false, Kernel::FIELD_ID_the_d_multiedge > >( ) );
1545
1546         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_with_values< Kernel::Graph::NODE, Kernel::FIELD_ID_with_node_values > >( ) );
1547         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_with_values< Kernel::Graph::EDGE, Kernel::FIELD_ID_with_edge_values > >( ) );
1548         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_rekey_with_index >( ) );
1549         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_subgraph< Kernel::Graph::INDUCED, Kernel::FIELD_ID_induced_subgraph > >( ) );
1550         dstClass->registerMethod( new Kernel::MethodFactory< Lang::Graph, Lang::GraphMethod_subgraph< Kernel::Graph::SPANNING, Kernel::FIELD_ID_spanning_subgraph > >( ) );
1551 }
1552
1553 RefCountPtr< const Lang::Class > Lang::Graph::TypeID( new Lang::SystemFinalClass( strrefdup( "Graph" ), Graph_register_methods ) );
1554 TYPEINFOIMPL( Graph );
1555
1556 Lang::Graph::Graph( const RefCountPtr< const Kernel::Graph > & graph )
1557   : graph_( graph ), nodeValues_( NullPtr< const ValueVector >( ) ), edgeValues_( NullPtr< const ValueVector >( ) )
1558 { }
1559
1560 Lang::Graph::Graph( const RefCountPtr< const Kernel::Graph > & graph, const RefCountPtr< const ValueVector > & nodeValues, const RefCountPtr< const ValueVector > & edgeValues )
1561   : graph_( graph ), nodeValues_( nodeValues ), edgeValues_( edgeValues )
1562 { }
1563
1564 Lang::Graph::Graph( const Lang::Graph & orig, const std::set< size_t > & subgraphIndices, Kernel::Graph::SubgraphKind kind )
1565         : graph_( NullPtr< const Kernel::Graph >( ) ), nodeValues_( NullPtr< const ValueVector >( ) ), edgeValues_( NullPtr< const ValueVector >( ) )
1566 {
1567         graph_ = RefCountPtr< const Kernel::Graph >( new Kernel::Graph( *orig.graph( ), subgraphIndices, kind, orig.nodeValues_, orig.edgeValues_, & nodeValues_, & edgeValues_ ) );
1568 }
1569
1570 Lang::Graph::Graph( const Lang::Graph & orig, Lang::Integer::ValueType offset )
1571         : graph_( new Kernel::Graph( *orig.graph( ), offset ) ), nodeValues_( orig.nodeValues_ ), edgeValues_( orig.edgeValues_ )
1572 { }
1573
1574 Lang::Graph::~Graph( )
1575 { }
1576
1577 void
1578 Lang::Graph::setNodeValues( const RefCountPtr< const ValueVector > nodeValues )
1579 {
1580         nodeValues_ = nodeValues;
1581 }
1582
1583 void
1584 Lang::Graph::setNodeValues( const std::list< Kernel::NodeData > & nodeData )
1585 {
1586         throw Exceptions::NotImplemented( "Lang::Graph::setNodeValues given NodeData" );
1587 }
1588
1589 void
1590 Lang::Graph::setEdgeValues( const RefCountPtr< const ValueVector > edgeValues )
1591 {
1592         edgeValues_ = edgeValues;
1593 }
1594
1595 void
1596 Lang::Graph::setEdgeValues( const std::list< Kernel::EdgeDataIndexed > & uedgeData, const std::list< Kernel::EdgeDataIndexed > & dedgeData, const std::list< Kernel::LoopDataIndexed > & uloopData, const std::list< Kernel::LoopDataIndexed > & dloopData )
1597 {
1598         throw Exceptions::NotImplemented( "Lang::Graph::setEdgeValues given EdgeData" );
1599 }
1600
1601 void
1602 Lang::Graph::show( std::ostream & os ) const
1603 {
1604         graph_->show( os );
1605 }
1606
1607 Kernel::VariableHandle
1608 Lang::Graph::getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const
1609 {
1610         if( strcmp( fieldID, "undirected?" ) == 0 )
1611                 {
1612                         return graph_->domain( ).directed( ) ? Kernel::THE_FALSE_VARIABLE : Kernel::THE_TRUE_VARIABLE;
1613                 }
1614         if( strcmp( fieldID, "directed?" ) == 0 )
1615                 {
1616                         return graph_->domain( ).undirected( ) ? Kernel::THE_FALSE_VARIABLE : Kernel::THE_TRUE_VARIABLE;
1617                 }
1618         if( strcmp( fieldID, "mixed?" ) == 0 )
1619                 {
1620                         return ( graph_->domain( ).undirected( ) && graph_->domain( ).directed( ) ) ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
1621                 }
1622         if( strcmp( fieldID, "loops?" ) == 0 )
1623                 {
1624                         return graph_->domain( ).loops( ) ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
1625                 }
1626         if( strcmp( fieldID, "parallel?" ) == 0 )
1627                 {
1628                         return graph_->domain( ).parallel( ) ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
1629                 }
1630         if( strcmp( fieldID, "partitioned?" ) == 0 )
1631                 {
1632                         return graph_->partitioned( ) ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
1633                 }
1634         if( strcmp( fieldID, "key_is_index?" ) == 0 )
1635                 {
1636                         return ( graph_->keyIsRange( ) && graph_->keyOffset( ) == 0 ) ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
1637                 }
1638
1639         if( strcmp( fieldID, "node_count" ) == 0 )
1640                 {
1641                         return Helpers::newValHandle( new Lang::Integer( graph_->nodes( ).size( ) ) );
1642                 }
1643         if( strcmp( fieldID, "u_edge_count" ) == 0 )
1644                 {
1645                         return Helpers::newValHandle( new Lang::Integer( graph_->uedges( ).size( ) + graph_->uloops( ).size( ) ) );
1646                 }
1647         if( strcmp( fieldID, "d_edge_count" ) == 0 )
1648                 {
1649                         return Helpers::newValHandle( new Lang::Integer( graph_->dedges( ).size( ) + graph_->dloops( ).size( ) ) );
1650                 }
1651         if( strcmp( fieldID, "edge_count" ) == 0 )
1652                 {
1653                         return Helpers::newValHandle( new Lang::Integer( graph_->uedges( ).size( ) + graph_->uloops( ).size( ) + graph_->dedges( ).size( ) + graph_->dloops( ).size( ) ) );
1654                 }
1655         if( strcmp( fieldID, "u_loop_count" ) == 0 )
1656                 {
1657                         return Helpers::newValHandle( new Lang::Integer( graph_->uloops( ).size( ) ) );
1658                 }
1659         if( strcmp( fieldID, "d_loop_count" ) == 0 )
1660                 {
1661                         return Helpers::newValHandle( new Lang::Integer( graph_->dloops( ).size( ) ) );
1662                 }
1663         if( strcmp( fieldID, "loop_count" ) == 0 )
1664                 {
1665                         return Helpers::newValHandle( new Lang::Integer( graph_->uloops( ).size( ) + graph_->dloops( ).size( ) ) );
1666                 }
1667
1668         if( strcmp( fieldID, "partition_count" ) == 0 )
1669                 {
1670                         return Helpers::newValHandle( new Lang::Integer( graph_->partitioned( ) ? graph_->partitionCount( ) : 0 ) );
1671                 }
1672         if( strcmp( fieldID, "partitions" ) == 0 )
1673                 {
1674                         if( ! graph_->partitioned( ) )
1675                                 return Kernel::THE_NIL_VARIABLE;
1676                         return Kernel::VariableHandle( new Kernel::Variable( graph_->partitionKeys( ) ) );
1677                 }
1678         if( strcmp( fieldID, "nodes" ) == 0 )
1679                 {
1680                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1681                         Kernel::Node::ListRef nodes = Lang::THE_CONS_NULL;
1682                         nodes = prepend_nodes( graph_->nodes( ), nodes, selfRefTyped );
1683                         return Kernel::VariableHandle( new Kernel::Variable( nodes ) );
1684                 }
1685         if( strcmp( fieldID, "u_edges" ) == 0 )
1686                 {
1687                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1688                         ListRef edges = Lang::THE_CONS_NULL;
1689                         edges = prepend_edges( graph_->uloops( ), false, edges, selfRefTyped );
1690                         edges = prepend_edges( graph_->uedges( ), false, edges, selfRefTyped );
1691                         return Kernel::VariableHandle( new Kernel::Variable( edges ) );
1692                 }
1693         if( strcmp( fieldID, "u_multiedges" ) == 0 )
1694                 {
1695                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1696                         ListRef edges = Lang::THE_CONS_NULL;
1697                         const Kernel::Graph::NodeVector & nodes = graph_->nodes( );
1698                         Kernel::Graph::NodeVector::const_iterator i = nodes.begin( );
1699                         Kernel::Graph::NodeVector::const_iterator theEnd = nodes.end( );
1700                         for( ; i != theEnd; ++i ){
1701                                 edges = (*i)->prepend_u_multiloops( edges, selfRefTyped );
1702                                 edges = (*i)->prepend_u_multiedgesLow( edges, selfRefTyped );
1703                         }
1704                         return Kernel::VariableHandle( new Kernel::Variable( edges ) );
1705                 }
1706         if( strcmp( fieldID, "d_edges" ) == 0 )
1707                 {
1708                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1709                         ListRef edges = Lang::THE_CONS_NULL;
1710                         edges = prepend_edges( graph_->dloops( ), true, edges, selfRefTyped );
1711                         edges = prepend_edges( graph_->dedges( ), true, edges, selfRefTyped );
1712                         return Kernel::VariableHandle( new Kernel::Variable( edges ) );
1713                 }
1714         if( strcmp( fieldID, "d_multiedges" ) == 0 )
1715                 {
1716                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1717                         ListRef edges = Lang::THE_CONS_NULL;
1718                         const Kernel::Graph::NodeVector & nodes = graph_->nodes( );
1719                         Kernel::Graph::NodeVector::const_iterator i = nodes.begin( );
1720                         Kernel::Graph::NodeVector::const_iterator theEnd = nodes.end( );
1721                         for( ; i != theEnd; ++i ){
1722                                 edges = (*i)->prepend_d_multiloops( edges, selfRefTyped );
1723                                 edges = (*i)->prepend_d_multiedgesIn( edges, selfRefTyped );
1724                         }
1725                         return Kernel::VariableHandle( new Kernel::Variable( edges ) );
1726                 }
1727         if( strcmp( fieldID, "edges" ) == 0 )
1728                 {
1729                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1730                         ListRef edges = Lang::THE_CONS_NULL;
1731                         edges = prepend_edges( graph_->dloops( ), true, edges, selfRefTyped );
1732                         edges = prepend_edges( graph_->uloops( ), false, edges, selfRefTyped );
1733                         edges = prepend_edges( graph_->dedges( ), true, edges, selfRefTyped );
1734                         edges = prepend_edges( graph_->uedges( ), false, edges, selfRefTyped );
1735                         return Kernel::VariableHandle( new Kernel::Variable( edges ) );
1736                 }
1737         if( strcmp( fieldID, "multiedges" ) == 0 )
1738                 {
1739                         RefCountPtr< const Lang::Graph > selfRefTyped = Helpers::down_cast_internal< const Lang::Graph >( selfRef );
1740                         ListRef edges = Lang::THE_CONS_NULL;
1741                         const Kernel::Graph::NodeVector & nodes = graph_->nodes( );
1742                         Kernel::Graph::NodeVector::const_iterator i = nodes.begin( );
1743                         Kernel::Graph::NodeVector::const_iterator theEnd = nodes.end( );
1744                         for( ; i != theEnd; ++i ){
1745                                 edges = (*i)->prepend_u_multiloops( edges, selfRefTyped );
1746                                 edges = (*i)->prepend_d_multiloops( edges, selfRefTyped );
1747                                 edges = (*i)->prepend_u_multiedgesLow( edges, selfRefTyped );
1748                                 edges = (*i)->prepend_d_multiedgesIn( edges, selfRefTyped );
1749                         }
1750                         return Kernel::VariableHandle( new Kernel::Variable( edges ) );
1751                 }
1752
1753         return TypeID->getMethod( selfRef, fieldID ); /* This will throw if there is no such method. */
1754 }
1755
1756 Kernel::State *
1757 Lang::Graph::newState( ) const
1758 {
1759         return graph_->newState( nodeValues_, edgeValues_ );
1760 }
1761
1762 Kernel::State *
1763 Kernel::Graph::newState( const RefCountPtr< const ValueVector > & nodeValues, const RefCountPtr< const ValueVector > & edgeValues ) const
1764 {
1765         RefCountPtr< std::list< Kernel::NodeData > > nodeDataMem;
1766         RefCountPtr< std::list< Kernel::EdgeData > > edgeDataMem;
1767
1768         std::list< Kernel::NodeData > * nodeDataPtr = nodeDataMem.getPtr( );
1769         std::list< Kernel::EdgeData > * edgeDataPtr = edgeDataMem.getPtr( );
1770
1771         if( nodeValues == NullPtr< const ValueVector >( ) ){
1772                 if( nodePartitions_ == NullPtr< ValueVector >( ) ){
1773                         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n ) {
1774                                 nodeDataPtr->push_back( Kernel::NodeData( (*n)->key( ), Lang::THE_VOID, Lang::THE_VOID ) );
1775                         }
1776                 }else{
1777                         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n ) {
1778                                 nodeDataPtr->push_back( Kernel::NodeData( (*n)->key( ), Lang::THE_VOID, (*nodePartitions_)[ (*n)->index( ) ] ) );
1779                         }
1780                 }
1781         }else{
1782                 if( nodePartitions_ == NullPtr< ValueVector >( ) ){
1783                         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n ) {
1784                                 nodeDataPtr->push_back( Kernel::NodeData( (*n)->key( ), (*nodeValues)[ (*n)->index( ) ], Lang::THE_VOID ) );
1785                         }
1786                 }else{
1787                         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n ) {
1788                                 nodeDataPtr->push_back( Kernel::NodeData( (*n)->key( ), (*nodeValues)[ (*n)->index( ) ], (*nodePartitions_)[ (*n)->index( ) ] ) );
1789                         }
1790                 }
1791         }
1792
1793         if( edgeValues == NullPtr< const ValueVector >( ) ){
1794                 if( edgeLabels_ == NullPtr< ValueVector >( ) ){
1795                         for( EdgeVector::const_iterator e = uedges_.begin( ); e != uedges_.end( ); ++e ) {
1796                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, Lang::THE_VOID ) );
1797                         }
1798                         for( EdgeVector::const_iterator e = dedges_.begin( ); e != dedges_.end( ); ++e ) {
1799                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, Lang::THE_VOID ) );
1800                         }
1801                         for( EdgeVector::const_iterator e = uloops_.begin( ); e != uloops_.end( ); ++e ) {
1802                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, Lang::THE_VOID ) );
1803                         }
1804                         for( EdgeVector::const_iterator e = dloops_.begin( ); e != dloops_.end( ); ++e ) {
1805                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, Lang::THE_VOID ) );
1806                         }
1807                 }else{
1808                         for( EdgeVector::const_iterator e = uedges_.begin( ); e != uedges_.end( ); ++e ) {
1809                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, (*edgeLabels_)[ (*e)->index( ) ] ) );
1810                         }
1811                         for( EdgeVector::const_iterator e = dedges_.begin( ); e != dedges_.end( ); ++e ) {
1812                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, (*edgeLabels_)[ (*e)->index( ) ] ) );
1813                         }
1814                         for( EdgeVector::const_iterator e = uloops_.begin( ); e != uloops_.end( ); ++e ) {
1815                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, (*edgeLabels_)[ (*e)->index( ) ] ) );
1816                         }
1817                         for( EdgeVector::const_iterator e = dloops_.begin( ); e != dloops_.end( ); ++e ) {
1818                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), Lang::THE_VOID, (*edgeLabels_)[ (*e)->index( ) ] ) );
1819                         }
1820                 }
1821         }else{
1822                 if( edgeLabels_ == NullPtr< ValueVector >( ) ){
1823                         for( EdgeVector::const_iterator e = uedges_.begin( ); e != uedges_.end( ); ++e ) {
1824                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], Lang::THE_VOID ) );
1825                         }
1826                         for( EdgeVector::const_iterator e = dedges_.begin( ); e != dedges_.end( ); ++e ) {
1827                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], Lang::THE_VOID ) );
1828                         }
1829                         for( EdgeVector::const_iterator e = uloops_.begin( ); e != uloops_.end( ); ++e ) {
1830                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], Lang::THE_VOID ) );
1831                         }
1832                         for( EdgeVector::const_iterator e = dloops_.begin( ); e != dloops_.end( ); ++e ) {
1833                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], Lang::THE_VOID ) );
1834                         }
1835                 }else{
1836                         for( EdgeVector::const_iterator e = uedges_.begin( ); e != uedges_.end( ); ++e ) {
1837                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], (*edgeLabels_)[ (*e)->index( ) ] ) );
1838                         }
1839                         for( EdgeVector::const_iterator e = dedges_.begin( ); e != dedges_.end( ); ++e ) {
1840                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], (*edgeLabels_)[ (*e)->index( ) ] ) );
1841                         }
1842                         for( EdgeVector::const_iterator e = uloops_.begin( ); e != uloops_.end( ); ++e ) {
1843                                 edgeDataPtr->push_back( Kernel::EdgeData( false, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], (*edgeLabels_)[ (*e)->index( ) ] ) );
1844                         }
1845                         for( EdgeVector::const_iterator e = dloops_.begin( ); e != dloops_.end( ); ++e ) {
1846                                 edgeDataPtr->push_back( Kernel::EdgeData( true, (*e)->source( )->key( ), (*e)->target( )->key( ), (*edgeValues)[ (*e)->index( ) ], (*edgeLabels_)[ (*e)->index( ) ] ) );
1847                         }
1848                 }
1849         }
1850
1851         return new Kernel::WarmGraph( domain_, partitionKeys_, nodeDataMem, edgeDataMem );
1852 }
1853
1854 void
1855 Lang::Graph::gcMark( Kernel::GCMarkedSet & marked )
1856 {
1857         if( nodeValues_ != NullPtr< const ValueVector >( ) )
1858                 {
1859                         for( ValueVector::const_iterator n = nodeValues_->begin( ); n != nodeValues_->end( ); ++n ) {
1860                                 const_cast< Lang::Value * >( n->getPtr( ) )->gcMark( marked );
1861                         }
1862                 }
1863         if( edgeValues_ != NullPtr< const ValueVector >( ) )
1864                 {
1865                         for( ValueVector::const_iterator e = nodeValues_->begin( ); e != nodeValues_->end( ); ++e ) {
1866                                 const_cast< Lang::Value * >( e->getPtr( ) )->gcMark( marked );
1867                         }
1868                 }
1869 }
1870
1871 Kernel::VariableHandle
1872 Lang::Graph::nodeValue( const Kernel::Node * node ) const
1873 {
1874         if( nodeValues_ == NullPtr< const ValueVector >( ) )
1875                 {
1876                         return Kernel::THE_VOID_VARIABLE;
1877                 }
1878
1879         return Kernel::VariableHandle( new Kernel::Variable( (*nodeValues_)[ node->index( ) ] ) );
1880 }
1881
1882 Kernel::VariableHandle
1883 Lang::Graph::edgeValue( const Kernel::Edge * edge ) const
1884 {
1885         if( edgeValues_ == NullPtr< const ValueVector >( ) )
1886                 {
1887                         return Kernel::THE_VOID_VARIABLE;
1888                 }
1889
1890         return Kernel::VariableHandle( new Kernel::Variable( (*edgeValues_)[ edge->index( ) ] ) );
1891 }
1892
1893 Kernel::VariableHandle
1894 Lang::Graph::nodePartition( const Kernel::Node * node ) const
1895 {
1896         return graph_->nodePartition( node );
1897 }
1898
1899 Kernel::VariableHandle
1900 Kernel::Graph::nodePartition( const Kernel::Node * node ) const
1901 {
1902         if( nodePartitions_ == NullPtr< ValueVector >( ) )
1903                 {
1904                         return Kernel::THE_VOID_VARIABLE;
1905                 }
1906
1907         return Kernel::VariableHandle( new Kernel::Variable( (*nodePartitions_)[ node->index( ) ] ) );
1908 }
1909
1910
1911 Kernel::VariableHandle
1912 Lang::Graph::edgeLabel( const Kernel::Edge * edge ) const
1913 {
1914         return graph_->edgeLabel( edge );
1915 }
1916
1917 Kernel::VariableHandle
1918 Kernel::Graph::edgeLabel( const Kernel::Edge * edge ) const
1919 {
1920         if( edgeLabels_ == NullPtr< ValueVector >( ) )
1921                 {
1922                         return Kernel::THE_VOID_VARIABLE;
1923                 }
1924
1925         return Kernel::VariableHandle( new Kernel::Variable( (*edgeLabels_)[ edge->index( ) ] ) );
1926 }
1927
1928
1929 const Kernel::Graph::NodeVector *
1930 Kernel::Graph::getPartition( const Kernel::ValueRef & key ) const
1931 {
1932         if( ! partitioned( ) ){
1933                 throw Exceptions::InternalError( "Kernel::Graph::getPartition invoked on non-partitioned graph." );
1934         }
1935
1936         if( const Lang::Symbol * ptr = dynamic_cast< const Lang::Symbol * >( key.getPtr( ) ) ){
1937                 Lang::Symbol::KeyType key = ptr->getKey( );
1938                 typedef typeof symbolKeyPartitionMap_ MapType;
1939                 MapType::const_iterator i = symbolKeyPartitionMap_.find( key );
1940                 if( i == symbolKeyPartitionMap_.end( ) ){
1941                         throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::PARTITION );
1942                 }
1943                 return i->second;
1944         }
1945
1946         if( const Lang::Integer * ptr = dynamic_cast< const Lang::Integer * >( key.getPtr( ) ) ){
1947                 Lang::Integer::ValueType key = ptr->val_;
1948                 typedef typeof integerKeyPartitionMap_ MapType;
1949                 MapType::const_iterator i = integerKeyPartitionMap_.find( key );
1950                 if( i == integerKeyPartitionMap_.end( ) ){
1951                         throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::PARTITION );
1952                 }
1953                 return i->second;
1954         }
1955
1956         throw Exceptions::InvalidGraphKeyType( );
1957 }
1958
1959 RefCountPtr< const Lang::SingleList >
1960 Lang::Graph::getPartition( const Kernel::ValueRef & key, const RefCountPtr< const Lang::Graph > & selfRef ) const
1961 {
1962         const Kernel::Graph::NodeVector * partition = graph_->getPartition( key );
1963         Kernel::Node::ListRef nodes = Lang::THE_CONS_NULL;
1964         nodes = prepend_nodes( *partition, nodes, selfRef );
1965         return nodes;
1966 }
1967
1968 size_t
1969 Lang::Graph::getPartitionSize( const Kernel::ValueRef & key ) const
1970 {
1971         const Kernel::Graph::NodeVector * partition = graph_->getPartition( key );
1972         return partition->size( );
1973 }
1974
1975
1976
1977
1978 void
1979 Kernel::Graph::show( std::ostream & os ) const
1980 {
1981         os << "<graph {" ;
1982
1983         if( ! domain_.directed( ) && ! domain_.undirected( ) )
1984                 os << "empty" ;
1985         else if( ! domain_.directed( ) )
1986                 os << "undirected" ;
1987         else if( ! domain_.undirected( ) )
1988                 os << "directed" ;
1989         else
1990                 os << "mixed" ;
1991
1992         if( domain_.loops( ) )
1993                 os << ", loops" ;
1994
1995         if( domain_.parallel( ) )
1996                 os << ", parallel" ;
1997
1998         os << "}, " ;
1999
2000         os << nodeCount( ) << " nodes and " << edgeCount( ) << " edges" ;
2001
2002         os << ">" ;
2003 }
2004
2005 size_t
2006 Kernel::Graph::edgeCount( ) const
2007 {
2008         return uedges_.size( ) + dedges_.size( ) + uloops_.size( ) + dloops_.size( );
2009 }
2010
2011 bool
2012 Kernel::Graph::isKey( const RefCountPtr< const Lang::Value > & key ) const
2013 {
2014         try
2015                 {
2016                         typedef const Lang::Symbol ArgType;
2017                         RefCountPtr< ArgType > symKey = Helpers::try_cast_CoreArgument< ArgType >( key );
2018                         return symbolKeyMap_.find( symKey->getKey( ) ) != symbolKeyMap_.end( );
2019                 }
2020         catch( const NonLocalExit::NotThisType & ball )
2021                 {
2022                         /* Never mind, try next type. */
2023                 }
2024
2025         try
2026                 {
2027                         typedef const Lang::Integer ArgType;
2028                         RefCountPtr< ArgType > intKey = Helpers::try_cast_CoreArgument< ArgType >( key );
2029                         return integerKeyMap_.find( intKey->val_ ) != integerKeyMap_.end( );
2030                 }
2031         catch( const NonLocalExit::NotThisType & ball )
2032                 {
2033                         /* Never mind, try next type. */
2034                 }
2035
2036         throw Exceptions::InvalidGraphKeyType( );
2037 }
2038
2039 RefCountPtr< const Lang::Node >
2040 Kernel::Graph::indexNode( const RefCountPtr< const Lang::Graph > & selfRef, size_t index ) const
2041 {
2042         return RefCountPtr< const Lang::Node >( new Lang::Node( selfRef, nodes_[ index ] ) );
2043 }
2044
2045 RefCountPtr< const Lang::Edge >
2046 Kernel::Graph::indexEdge( const RefCountPtr< const Lang::Graph > & selfRef, size_t index ) const
2047 {
2048         size_t iMax = uedges_.size( );
2049         if( index < iMax )
2050                 return RefCountPtr< const Lang::Edge >( new Lang::Edge( selfRef, uedges_[ index ], false ) );
2051         index -= iMax;
2052
2053         iMax = dedges_.size( );
2054         if( index < iMax )
2055                 return RefCountPtr< const Lang::Edge >( new Lang::Edge( selfRef, dedges_[ index ], true ) );
2056         index -= iMax;
2057
2058         iMax = uloops_.size( );
2059         if( index < iMax )
2060                 return RefCountPtr< const Lang::Edge >( new Lang::Edge( selfRef, uloops_[ index ], false ) );
2061         index -= iMax;
2062
2063         iMax = dloops_.size( );
2064         if( index < iMax )
2065                 return RefCountPtr< const Lang::Edge >( new Lang::Edge( selfRef, dloops_[ index ], true ) );
2066
2067         throw Exceptions::InternalError( "Lang::Graph::indexEdge: index is out of range." );
2068 }
2069
2070 RefCountPtr< const Lang::Node >
2071 Kernel::Graph::findNode( const RefCountPtr< const Lang::Graph > & selfRef, const RefCountPtr< const Lang::Value > & key ) const
2072 {
2073         if( ! keyIsRange_ ){
2074                 try
2075                         {
2076                                 typedef const Lang::Symbol ArgType;
2077                                 RefCountPtr< ArgType > symKey = Helpers::try_cast_CoreArgument< ArgType >( key );
2078                                 SymbolKeyMap::const_iterator i = symbolKeyMap_.find( symKey->getKey( ) );
2079                                 if( i == symbolKeyMap_.end( ) )
2080                                         throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::NODE );
2081                                 return RefCountPtr< const Lang::Node >( new Lang::Node( selfRef, i->second ) );
2082                         }
2083                 catch( const NonLocalExit::NotThisType & ball )
2084                         {
2085                                 /* Never mind, try next type. */
2086                         }
2087         }
2088
2089         try
2090                 {
2091                         typedef const Lang::Integer ArgType;
2092                         ArgType::ValueType intKey = Helpers::try_cast_CoreArgument< ArgType >( key )->val_;
2093                         if( keyIsRange_ ){
2094                                 if( intKey < keyOffset_ )
2095                                         throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::NODE );
2096                                 size_t i = intKey - keyOffset_;
2097                                 if( i >= nodes_.size( ) )
2098                                         throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::NODE );
2099                                 return RefCountPtr< const Lang::Node >( new Lang::Node( selfRef, nodes_[ i ] ) );
2100                         }else{
2101                                 SymbolKeyMap::const_iterator i = integerKeyMap_.find( intKey );
2102                                 if( i == integerKeyMap_.end( ) )
2103                                         throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::NODE );
2104                                 return RefCountPtr< const Lang::Node >( new Lang::Node( selfRef, i->second ) );
2105                         }
2106                 }
2107         catch( const NonLocalExit::NotThisType & ball )
2108                 {
2109                         /* Never mind, try next type. */
2110                 }
2111
2112         throw Exceptions::InvalidGraphKeyType( );
2113 }
2114
2115 size_t
2116 Kernel::Graph::findIndex( const RefCountPtr< const Lang::Value > & key ) const
2117 {
2118         try
2119                 {
2120                         typedef const Lang::Symbol ArgType;
2121                         RefCountPtr< ArgType > symKey = Helpers::try_cast_CoreArgument< ArgType >( key );
2122                         SymbolKeyMap::const_iterator i = symbolKeyMap_.find( symKey->getKey( ) );
2123                         if( i == symbolKeyMap_.end( ) )
2124                                 throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::NODE );
2125                         return i->second->index( );
2126                 }
2127         catch( const NonLocalExit::NotThisType & ball )
2128                 {
2129                         /* Never mind, try next type. */
2130                 }
2131
2132         try
2133                 {
2134                         typedef const Lang::Integer ArgType;
2135                         RefCountPtr< ArgType > intKey = Helpers::try_cast_CoreArgument< ArgType >( key );
2136                         SymbolKeyMap::const_iterator i = integerKeyMap_.find( intKey->val_ );
2137                         if( i == integerKeyMap_.end( ) )
2138                                 throw Exceptions::InvalidGraphKey( Exceptions::InvalidGraphKey::NODE );
2139                         return i->second->index( );
2140                 }
2141         catch( const NonLocalExit::NotThisType & ball )
2142                 {
2143                         /* Never mind, try next type. */
2144                 }
2145
2146         throw Exceptions::InvalidGraphKeyType( );
2147 }
2148
2149 Kernel::Graph::ListRef
2150 Kernel::Graph::findEdges( const RefCountPtr< const Lang::Graph > & selfRef, Kernel::Node * source, Kernel::Node * target, bool directed, bool undirected, bool loops, const Kernel::ValueRef & label ) const
2151 {
2152         Kernel::Node::ListRef edges = Lang::THE_CONS_NULL;
2153
2154         RefCountPtr< const Kernel::EdgePredicate > filter = RefCountPtr< const Kernel::EdgePredicate >( NullPtr< const Kernel::EdgePredicate >( ) );
2155         if( const Lang::Symbol * ptr = dynamic_cast< const Lang::Symbol * >( label.getPtr( ) ) ){
2156                 filter = RefCountPtr< const Kernel::EdgePredicate >( new Kernel::EdgeLabelPredicate< Lang::Symbol >( edgeLabels_, *ptr ) );
2157         }else if( const Lang::Integer * ptr = dynamic_cast< const Lang::Integer * >( label.getPtr( ) ) ){
2158                 filter = RefCountPtr< const Kernel::EdgePredicate >( new Kernel::EdgeLabelPredicate< Lang::Integer >( edgeLabels_, *ptr ) );
2159         }
2160
2161         if( filter != NullPtr< const Kernel::EdgePredicate >( ) && filter->always_false( ) ){
2162                 return edges;
2163         }
2164
2165         if( source != 0 && target != 0 ){
2166
2167                 if( source == target ){
2168                         if( loops ){
2169                                 if( undirected )
2170                                         edges = source->prepend_uloops( edges, selfRef, filter.getPtr( ) );
2171                                 if( directed )
2172                                         edges = source->prepend_dloops( edges, selfRef, filter.getPtr( ) );
2173                         }
2174                 }else{
2175                         if( undirected )
2176                                 edges = source->prepend_uedges_to( target, edges, selfRef, filter.getPtr( ) );
2177                         if( directed )
2178                                 edges = source->prepend_dedges_to( target, edges, selfRef, filter.getPtr( ) );
2179                 }
2180
2181         }else if( source != 0 ){
2182
2183                 if( loops ){
2184                         if( undirected )
2185                                 edges = source->prepend_uloops( edges, selfRef, filter.getPtr( ) );
2186                         if( directed )
2187                                 edges = source->prepend_dloops( edges, selfRef, filter.getPtr( ) );
2188                 }
2189                 if( undirected )
2190                         edges = source->prepend_uedges( edges, selfRef, filter.getPtr( ) );
2191                 if( directed )
2192                         edges = source->prepend_dedgesOut( edges, selfRef, filter.getPtr( ) );
2193
2194         }else if( target != 0 ){
2195
2196                 if( loops ){
2197                         if( undirected )
2198                                 edges = target->prepend_uloops( edges, selfRef, filter.getPtr( ) );
2199                         if( directed )
2200                                 edges = target->prepend_dloops( edges, selfRef, filter.getPtr( ) );
2201                 }
2202                 if( undirected )
2203                         edges = target->prepend_uedges( edges, selfRef, filter.getPtr( ) );
2204                 if( directed )
2205                         edges = target->prepend_dedgesIn( edges, selfRef, filter.getPtr( ) );
2206
2207         }else{
2208
2209                 if( loops ){
2210                         if( undirected )
2211                                 edges = Lang::Graph::prepend_edges( uloops_, false, edges, selfRef, filter.getPtr( ) );
2212                         if( directed )
2213                                 edges = Lang::Graph::prepend_edges( dloops_, true, edges, selfRef, filter.getPtr( ) );
2214                 }
2215                 if( undirected )
2216                         edges = Lang::Graph::prepend_edges( uedges_, false, edges, selfRef, filter.getPtr( ) );
2217                 if( directed )
2218                         edges = Lang::Graph::prepend_edges( dedges_, true, edges, selfRef, filter.getPtr( ) );
2219
2220         }
2221
2222         return edges;
2223 }
2224
2225 Kernel::Graph::ListRef
2226 Kernel::Graph::findMultiEdges( const RefCountPtr< const Lang::Graph > & selfRef, const Kernel::Node * source, const Kernel::Node * target, bool directed, bool undirected, bool loops ) const
2227 {
2228         Kernel::Node::ListRef edges = Lang::THE_CONS_NULL;
2229
2230         if( ! directed && source->index( ) > target->index( ) ){
2231                 const Kernel::Node * tmp = target;
2232                 target = source;
2233                 source = tmp;
2234         }
2235
2236         if( source != 0 && target != 0 ){
2237
2238                 if( source == target ){
2239                         if( loops ){
2240                                 if( undirected )
2241                                         edges = source->prepend_u_multiloops( edges, selfRef );
2242                                 if( directed )
2243                                         edges = source->prepend_d_multiloops( edges, selfRef );
2244                         }
2245                 }else{
2246                         if( undirected )
2247                                 edges = target->prepend_u_multiedgeLowFrom( source, edges, selfRef );
2248                         if( directed )
2249                                 edges = target->prepend_d_multiedgeInFrom( source, edges, selfRef );
2250                 }
2251
2252         }else if( source != 0 ){
2253
2254                 if( loops ){
2255                         if( undirected )
2256                                 edges = source->prepend_u_multiloops( edges, selfRef );
2257                         if( directed )
2258                                 edges = source->prepend_d_multiloops( edges, selfRef );
2259                 }
2260                 if( undirected )
2261                         edges = source->prepend_u_multiedges( edges, selfRef );
2262                 if( directed )
2263                         edges = source->prepend_d_multiedgesOut( edges, selfRef );
2264
2265         }else if( target != 0 ){
2266
2267                 if( loops ){
2268                         if( undirected )
2269                                 edges = source->prepend_u_multiloops( edges, selfRef );
2270                         if( directed )
2271                                 edges = source->prepend_d_multiloops( edges, selfRef );
2272                 }
2273                 if( undirected )
2274                         edges = source->prepend_u_multiedges( edges, selfRef );
2275                 if( directed )
2276                         edges = source->prepend_d_multiedgesIn( edges, selfRef );
2277
2278         }else{
2279
2280                 Kernel::Graph::NodeVector::const_iterator i = nodes_.begin( );
2281                 Kernel::Graph::NodeVector::const_iterator theEnd = nodes_.end( );
2282                 for( ; i != theEnd; ++i ){
2283                         if( loops ){
2284                                 if( undirected )
2285                                         edges = (*i)->prepend_u_multiloops( edges, selfRef );
2286                                 if( directed )
2287                                         edges = (*i)->prepend_d_multiloops( edges, selfRef );
2288                         }
2289                         if( undirected )
2290                                 edges = (*i)->prepend_u_multiedgesLow( edges, selfRef );
2291                         if( directed )
2292                                 edges = (*i)->prepend_d_multiedgesIn( edges, selfRef );
2293                 }
2294
2295         }
2296
2297         return edges;
2298 }
2299
2300 Kernel::Node *
2301 Lang::Graph::kernelNodeByValue( Kernel::Arguments & args, size_t argsi, bool voidIsNull, const RefCountPtr< const Interaction::CoreLocation > & coreLoc, const Ast::SourceLocation & callLoc ) const
2302 {
2303         RefCountPtr< const Lang::Value > arg = args.getValue( argsi );
2304
2305         if( arg == Lang::THE_VOID ){
2306                 if( voidIsNull )
2307                         return 0;
2308                 throw Exceptions::CoreTypeMismatch( callLoc, coreLoc, args, argsi, Exceptions::GraphKeyTypeMismatch::expectedTypeOrNode );
2309         }
2310
2311         RefCountPtr< const Lang::Node > node = arg.down_cast< const Lang::Node >( );
2312         if( node != NullPtr< const Lang::Node >( ) ){
2313                 if( node->graph( ).getPtr( ) != this ){
2314                         throw Exceptions::InvalidGraphElement( Exceptions::InvalidGraphElement::NODE, args.getLoc( argsi ) );
2315                 }
2316                 /* The const_cast below is really just a shortcut for:
2317                  *   nodes_[ node->index( ) ]
2318                  */
2319                 return const_cast< Kernel::Node * >( node->node( ) );
2320         }
2321
2322         try
2323                 {
2324                         return graph_->nodes( )[ graph_->findIndex( arg ) ];
2325                 }
2326         catch( const Exceptions::InvalidGraphKeyType & ball )
2327                 {
2328                         throw Exceptions::CoreTypeMismatch( callLoc, coreLoc, args, argsi, Exceptions::GraphKeyTypeMismatch::expectedTypeOrNode );
2329                 }
2330         catch( const Exceptions::InvalidGraphKey & ball )
2331                 {
2332                         throw Exceptions::GraphKeyOutOfRange( Exceptions::GraphKeyOutOfRange::NODE, callLoc, coreLoc, args, argsi );
2333                 }
2334 }
2335
2336
2337 void
2338 Kernel::Graph::initializeKeyRangeOffset( )
2339 {
2340         keyIsRange_ = true;
2341         keyOffset_ = 0;
2342
2343         Lang::Integer::ValueType ni = 0;
2344         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n, ++ni ) {
2345                 try
2346                         {
2347                                 Lang::Integer::ValueType i = Helpers::try_cast_CoreArgument< const Lang::Integer >( (*n)->key( ) )->val_;
2348                                 if( i != ni + keyOffset_ ) {
2349                                         if( ni == 0 ){
2350                                                 keyOffset_ = i;
2351                                         }else{
2352                                                 keyIsRange_ = false;
2353                                                 break;
2354                                         }
2355                                 }
2356                         }
2357                 catch( const NonLocalExit::NotThisType & ball )
2358                         {
2359                                 keyIsRange_ = false;
2360                                 break;
2361                         }
2362         }
2363 }
2364
2365 void
2366 Kernel::Graph::initializeKeyMaps( )
2367 {
2368         if( keyIsRange_ )
2369                 return;
2370         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n ){
2371                 const Lang::Value * key = (*n)->key( ).getPtr( );
2372                 {
2373                         const Lang::Symbol * symKey = dynamic_cast< const Lang::Symbol * >( key );
2374                         if( symKey != NullPtr< const Lang::Symbol >( ) ) {
2375                                 symbolKeyMap_[ symKey->getKey( ) ] = *n;
2376                                 continue;
2377                         }
2378                 }
2379                 {
2380                         const Lang::Integer * intKey = dynamic_cast< const Lang::Integer * >( key );
2381                         if( intKey != NullPtr< const Lang::Integer >( ) ) {
2382                                 integerKeyMap_[ intKey->val_ ] = *n;
2383                                 continue;
2384                         }
2385                 }
2386                 throw Exceptions::InternalError( "Lang::Graph initialized with key of bad type." );
2387         }
2388 }
2389
2390 void
2391 Kernel::Graph::initializeAndCheckPartitions( const Ast::SourceLocation & callLoc )
2392 {
2393         if( partitionKeys_ == NullPtr< const Lang::SingleList >( ) )
2394                 return;
2395
2396         {
2397                 RefCountPtr< const Lang::SingleListPair > p = partitionKeys_.down_cast< const Lang::SingleListPair >( );
2398                 while( p != NullPtr< const Lang::SingleListPair >( ) ){
2399                         RefCountPtr< const Lang::Value > val = p->car_->getUntyped( );
2400
2401                         do{
2402
2403                                 if( const Lang::Symbol * ptr = dynamic_cast< const Lang::Symbol * >( val.getPtr( ) ) ){
2404                                         Lang::Symbol::KeyType key = ptr->getKey( );
2405                                         NodeVector * newPartition = new NodeVector( );
2406                                         partitions_.push_back( newPartition );
2407                                         symbolKeyPartitionMap_[ key ] = newPartition;
2408                                         break;
2409                                 }
2410
2411                                 if( const Lang::Integer * ptr = dynamic_cast< const Lang::Integer * >( val.getPtr( ) ) ){
2412                                         Lang::Integer::ValueType key = ptr->val_;
2413                                         NodeVector * newPartition = new NodeVector( );
2414                                         partitions_.push_back( newPartition );
2415                                         integerKeyPartitionMap_[ key ] = newPartition;
2416                                         break;
2417                                 }
2418
2419                                 throw Exceptions::InternalError( "Kernel::Graph::initializeAndCheckPartitions: Unexcpected partition key type." );
2420
2421                         }while( false );
2422
2423                         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
2424                 }
2425         }
2426
2427         ValueVector::const_iterator p = nodePartitions_->begin( );
2428         for( NodeVector::const_iterator n = nodes_.begin( ); n != nodes_.end( ); ++n, ++p ){
2429
2430                 do{
2431
2432                         if( const Lang::Symbol * ptr = dynamic_cast< const Lang::Symbol * >( p->getPtr( ) ) ){
2433                                 Lang::Symbol::KeyType key = ptr->getKey( );
2434                                 symbolKeyPartitionMap_[ key ]->push_back( *n );
2435                                 break;
2436                         }
2437
2438                         if( const Lang::Integer * ptr = dynamic_cast< const Lang::Integer * >( p->getPtr( ) ) ){
2439                                 Lang::Integer::ValueType key = ptr->val_;
2440                                 integerKeyPartitionMap_[ key ]->push_back( *n );
2441                                 break;
2442                         }
2443
2444                         throw Exceptions::InternalError( "Kernel::Graph::initializeAndCheckPartitions: Unexcpected node partition type." );
2445
2446                 }while( false );
2447
2448         }
2449
2450         for( EdgeVector::iterator e = uedges_.begin( ); e != uedges_.end( ); ++e ){
2451                 /* By using getPartition to map a partition key to a pointer to the vector of nodes in that partiion
2452                  * we obtain a canonicalization.  (Note that a pointer comparison of the partiion keys themselves does
2453                  * not work since there may be more than one Lang::Value with the same content.)
2454                  */
2455                 const NodeVector * sourcePartition = getPartition( (*nodePartitions_)[ (*e)->source( )->index( ) ] );
2456                 const NodeVector * targetPartition = getPartition( (*nodePartitions_)[ (*e)->target( )->index( ) ] );
2457                 if( sourcePartition == targetPartition ){
2458                         throw Exceptions::GraphPartitionViolation( (*e)->source( )->key( ), (*e)->target( )->key( ), (*nodePartitions_)[ (*e)->source( )->index( ) ], callLoc );
2459                 }
2460         }
2461         for( EdgeVector::iterator e = dedges_.begin( ); e != dedges_.end( ); ++e ){
2462                 const NodeVector * sourcePartition = getPartition( (*nodePartitions_)[ (*e)->source( )->index( ) ] );
2463                 const NodeVector * targetPartition = getPartition( (*nodePartitions_)[ (*e)->target( )->index( ) ] );
2464                 if( sourcePartition == targetPartition ){
2465                         throw Exceptions::GraphPartitionViolation( (*e)->source( )->key( ), (*e)->target( )->key( ), (*nodePartitions_)[ (*e)->source( )->index( ) ], callLoc );
2466                 }
2467         }
2468
2469 }
2470
2471 void
2472 Kernel::Graph::addEdgesToNodes( )
2473 {
2474         for( EdgeVector::iterator e = uedges_.begin( ); e != uedges_.end( ); ++e ){
2475                 (*e)->source( )->add_uedgeHigh( *e );
2476                 (*e)->target( )->add_uedgeLow( *e );
2477         }
2478         for( EdgeVector::iterator e = uloops_.begin( ); e != uloops_.end( ); ++e ){
2479                 (*e)->source( )->add_uloop( *e );
2480         }
2481         for( EdgeVector::iterator e = dedges_.begin( ); e != dedges_.end( ); ++e ){
2482                 (*e)->source( )->add_dedgeOut( *e );
2483                 (*e)->target( )->add_dedgeIn( *e );
2484         }
2485         for( EdgeVector::iterator e = dloops_.begin( ); e != dloops_.end( ); ++e ){
2486                 (*e)->source( )->add_dloop( *e );
2487         }
2488 }
2489
2490 Lang::Graph::ListRef
2491 Lang::Graph::prepend_nodes( const Kernel::Graph::NodeVector & nodes, const ListRef & rest, const RefCountPtr< const Lang::Graph > & selfRef )
2492 {
2493         Lang::Graph::ListRef result = rest;
2494         for( Kernel::Graph::NodeVector::const_reverse_iterator n = nodes.rbegin( ); n != nodes.rend( ); ++n ){
2495                 result = Helpers::SingleList_cons( new Lang::Node( selfRef, *n ), result );
2496         }
2497         return result;
2498 }
2499
2500 Lang::Graph::ListRef
2501 Lang::Graph::prepend_edges( const Kernel::Graph::EdgeVector & edges, bool directed, const ListRef & rest, const RefCountPtr< const Lang::Graph > & selfRef, const Kernel::EdgePredicate * filter )
2502 {
2503         Lang::Graph::ListRef result = rest;
2504         if( filter == 0 ){
2505                 for( Kernel::Graph::EdgeVector::const_reverse_iterator e = edges.rbegin( ); e != edges.rend( ); ++e ){
2506                         result = Helpers::SingleList_cons( new Lang::Edge( selfRef, *e, directed ), result );
2507                 }
2508         }else{
2509                 for( Kernel::Graph::EdgeVector::const_reverse_iterator e = edges.rbegin( ); e != edges.rend( ); ++e ){
2510                         if( (*filter)( **e ) ){
2511                                 result = Helpers::SingleList_cons( new Lang::Edge( selfRef, *e, directed ), result );
2512                         }
2513                 }
2514         }
2515         return result;
2516 }
2517
2518
2519 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2520 Lang::NodeMethod_edges< directed, undirected, in, out, fieldID >::NodeMethod_edges( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID )
2521         : Lang::MethodBase< Lang::Node >( self, fullMethodID, false, true )
2522 {
2523         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
2524 }
2525
2526 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2527 Lang::NodeMethod_edges< directed, undirected, in, out, fieldID >::~NodeMethod_edges( )
2528 { }
2529
2530 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2531 void
2532 Lang::NodeMethod_edges< directed, undirected, in, out, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2533 {
2534         args.applyDefaults( callLoc );
2535
2536         typedef const Lang::Boolean ArgType;
2537         bool loops = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 0, callLoc )->val_;
2538
2539         Kernel::Node::ListRef edges = Lang::THE_CONS_NULL;
2540         if( loops ){
2541                 if( undirected )
2542                         edges = self_->node( )->prepend_uloops( edges, self_->graph( ) );
2543                 if( directed )
2544                         edges = self_->node( )->prepend_dloops( edges, self_->graph( ) );
2545         }
2546         if( undirected )
2547                 edges = self_->node( )->prepend_uedges( edges, self_->graph( ) );
2548         if( directed ){
2549                 if( out )
2550                         edges = self_->node( )->prepend_dedgesOut( edges, self_->graph( ) );
2551                 if( in )
2552                         edges = self_->node( )->prepend_dedgesIn( edges, self_->graph( ) );
2553         }
2554
2555         Kernel::ContRef cont = evalState->cont_;
2556         cont->takeValue( edges,
2557                                                                          evalState );
2558 }
2559
2560
2561 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2562 Lang::NodeMethod_multiedges< directed, undirected, in, out, fieldID >::NodeMethod_multiedges( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID )
2563         : Lang::MethodBase< Lang::Node >( self, fullMethodID, false, true )
2564 {
2565         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
2566 }
2567
2568 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2569 Lang::NodeMethod_multiedges< directed, undirected, in, out, fieldID >::~NodeMethod_multiedges( )
2570 { }
2571
2572 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2573 void
2574 Lang::NodeMethod_multiedges< directed, undirected, in, out, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2575 {
2576         args.applyDefaults( callLoc );
2577
2578         typedef const Lang::Boolean ArgType;
2579         bool loops = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 0, callLoc )->val_;
2580
2581         Kernel::Node::ListRef edges = Lang::THE_CONS_NULL;
2582         if( loops ){
2583                 if( undirected )
2584                         edges = self_->node( )->prepend_u_multiloops( edges, self_->graph( ) );
2585                 if( directed )
2586                         edges = self_->node( )->prepend_d_multiloops( edges, self_->graph( ) );
2587         }
2588         if( undirected ){
2589                 edges = self_->node( )->prepend_u_multiedges( edges, self_->graph( ) );
2590         }
2591         if( directed ){
2592                 if( out )
2593                         edges = self_->node( )->prepend_d_multiedgesOut( edges, self_->graph( ) );
2594                 if( in )
2595                         edges = self_->node( )->prepend_d_multiedgesIn( edges, self_->graph( ) );
2596         }
2597
2598         Kernel::ContRef cont = evalState->cont_;
2599         cont->takeValue( edges,
2600                                                                          evalState );
2601 }
2602
2603
2604 template< bool directed, bool undirected, const char * fieldID >
2605 Lang::NodeMethod_loops< directed, undirected, fieldID >::NodeMethod_loops( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID )
2606         : Lang::MethodBase< Lang::Node >( self, fullMethodID, false, true )
2607 {
2608         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
2609 }
2610
2611 template< bool directed, bool undirected, const char * fieldID >
2612 Lang::NodeMethod_loops< directed, undirected, fieldID >::~NodeMethod_loops( )
2613 { }
2614
2615 template< bool directed, bool undirected, const char * fieldID >
2616 void
2617 Lang::NodeMethod_loops< directed, undirected, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2618 {
2619         Kernel::Node::ListRef edges = Lang::THE_CONS_NULL;
2620         if( undirected )
2621                 edges = self_->node( )->prepend_uloops( edges, self_->graph( ) );
2622         if( directed )
2623                 edges = self_->node( )->prepend_dloops( edges, self_->graph( ) );
2624
2625         Kernel::ContRef cont = evalState->cont_;
2626         cont->takeValue( edges,
2627                                                                          evalState );
2628 }
2629
2630
2631 template< bool directed, bool undirected, const char * fieldID >
2632 Lang::NodeMethod_multiloops< directed, undirected, fieldID >::NodeMethod_multiloops( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID )
2633         : Lang::MethodBase< Lang::Node >( self, fullMethodID, false, true )
2634 {
2635         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
2636 }
2637
2638 template< bool directed, bool undirected, const char * fieldID >
2639 Lang::NodeMethod_multiloops< directed, undirected, fieldID >::~NodeMethod_multiloops( )
2640 { }
2641
2642 template< bool directed, bool undirected, const char * fieldID >
2643 void
2644 Lang::NodeMethod_multiloops< directed, undirected, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2645 {
2646         Kernel::Node::ListRef edges = Lang::THE_CONS_NULL;
2647         if( undirected )
2648                 edges = self_->node( )->prepend_u_multiloops( edges, self_->graph( ) );
2649         if( directed )
2650                 edges = self_->node( )->prepend_d_multiloops( edges, self_->graph( ) );
2651
2652         Kernel::ContRef cont = evalState->cont_;
2653         cont->takeValue( edges,
2654                                                                          evalState );
2655 }
2656
2657
2658 template< bool reverse, const char * fieldID >
2659 Lang::NodeMethod_trace< reverse, fieldID >::NodeMethod_trace( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID )
2660         : Lang::MethodBase< Lang::Node >( self, fullMethodID, false, true )
2661 {
2662         formals_->appendEvaluatedCoreFormal( "edge", Kernel::THE_SLOT_VARIABLE );
2663 }
2664
2665 template< bool reverse, const char * fieldID >
2666 Lang::NodeMethod_trace< reverse, fieldID >::~NodeMethod_trace( )
2667 { }
2668
2669 template< bool reverse, const char * fieldID >
2670 void
2671 Lang::NodeMethod_trace< reverse, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2672 {
2673         args.applyDefaults( callLoc );
2674
2675         const Kernel::Node * other;
2676
2677         size_t argsi = 0;
2678         do{
2679                 try{
2680                         typedef const Lang::Edge ArgType;
2681                         RefCountPtr< ArgType > edge = Helpers::try_cast_CoreArgument< ArgType >( args.getValue( argsi ) );
2682                         other = reverse ? edge->backtrace( self_->node( ), callLoc ) : edge->trace( self_->node( ), callLoc );
2683                         break;
2684                 }catch( const NonLocalExit::NotThisType & ball ){
2685                         /* Never mind, try next type. */
2686                 }
2687                 try{
2688                         typedef const Lang::MultiEdge ArgType;
2689                         RefCountPtr< ArgType > edge = Helpers::try_cast_CoreArgument< ArgType >( args.getValue( argsi ) );
2690                         other = reverse ? edge->backtrace( self_->node( ), callLoc ) : edge->trace( self_->node( ), callLoc );
2691                         break;
2692                 }catch( const NonLocalExit::NotThisType & ball ){
2693                         /* Never mind, try next type. */
2694                 }
2695                 throw Exceptions::CoreTypeMismatch( callLoc, coreLoc_, args, argsi, Helpers::typeSetString( Lang::Edge::staticTypeName( ), Lang::MultiEdge::staticTypeName( ) ) );
2696         }while( false );
2697
2698         Kernel::ContRef cont = evalState->cont_;
2699         cont->takeValue( Kernel::ValueRef( new Lang::Node( self_->graph( ), other ) ),
2700                                                                          evalState );
2701 }
2702
2703
2704 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2705 Lang::NodeMethod_neighbors< directed, undirected, in, out, fieldID >::NodeMethod_neighbors( RefCountPtr< const Lang::Node > self, const Ast::FileID * fullMethodID )
2706         : Lang::MethodBase< Lang::Node >( self, fullMethodID, false, true )
2707 {
2708         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
2709         formals_->appendEvaluatedCoreFormal( "parallel", Kernel::THE_TRUE_VARIABLE );
2710 }
2711
2712 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2713 Lang::NodeMethod_neighbors< directed, undirected, in, out, fieldID >::~NodeMethod_neighbors( )
2714 { }
2715
2716 template< bool directed, bool undirected, bool in, bool out, const char * fieldID >
2717 void
2718 Lang::NodeMethod_neighbors< directed, undirected, in, out, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2719 {
2720         args.applyDefaults( callLoc );
2721
2722         typedef const Lang::Boolean ArgType;
2723         bool loops = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 0, callLoc )->val_;
2724         bool parallel = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 1, callLoc )->val_;
2725
2726         Kernel::Node::ListRef neighbors = Lang::THE_CONS_NULL;
2727         if( parallel ){
2728                 if( loops ){
2729                         if( undirected )
2730                                 neighbors = self_->node( )->prepend_uloopNeighbors( neighbors, self_->graph( ) );
2731                         if( directed )
2732                                 neighbors = self_->node( )->prepend_dloopNeighbors( neighbors, self_->graph( ) );
2733                 }
2734                 if( undirected )
2735                         neighbors = self_->node( )->prepend_uedgeNeighbors( neighbors, self_->graph( ) );
2736                 if( directed ){
2737                         if( out )
2738                                 neighbors = self_->node( )->prepend_dedgeNeighborsOut( neighbors, self_->graph( ) );
2739                         if( in )
2740                         neighbors = self_->node( )->prepend_dedgeNeighborsIn( neighbors, self_->graph( ) );
2741                 }
2742         }else{
2743                 std::set< size_t > added;
2744                 if( loops ) {
2745                         if( undirected )
2746                                 neighbors = self_->node( )->prepend_unique_uloopNeighbors( neighbors, self_->graph( ), & added );
2747                         if( directed )
2748                                 neighbors = self_->node( )->prepend_unique_dloopNeighbors( neighbors, self_->graph( ), & added );
2749                 }
2750                 if( undirected )
2751                         neighbors = self_->node( )->prepend_unique_uedgeNeighbors( neighbors, self_->graph( ), & added );
2752                 if( directed ){
2753                         if( out )
2754                                 neighbors = self_->node( )->prepend_unique_dedgeNeighborsOut( neighbors, self_->graph( ), & added );
2755                         if( in )
2756                                 neighbors = self_->node( )->prepend_unique_dedgeNeighborsIn( neighbors, self_->graph( ), & added );
2757                 }
2758         }
2759
2760         Kernel::ContRef cont = evalState->cont_;
2761         cont->takeValue( neighbors,
2762                                                                          evalState );
2763 }
2764
2765
2766 template< class T >
2767 Lang::Method_get_graph< T >::Method_get_graph( RefCountPtr< const T > self, const Ast::FileID * fullMethodID )
2768         : Lang::MethodBase< T >( self, fullMethodID, false, true )
2769 { }
2770
2771 template< class T >
2772 Lang::Method_get_graph< T >::~Method_get_graph( )
2773 { }
2774
2775 template< class T >
2776 void
2777 Lang::Method_get_graph< T >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2778 {
2779         Kernel::ContRef cont = evalState->cont_;
2780         cont->takeValue( Lang::MethodBase< T >::self_->graph( ),
2781                                                                          evalState );
2782 }
2783
2784
2785 template< bool onlyCount, const char * fieldID >
2786 Lang::GraphMethod_partition< onlyCount, fieldID >::GraphMethod_partition( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2787         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2788 {
2789         formals_->appendEvaluatedCoreFormal( "key", Kernel::THE_SLOT_VARIABLE );
2790 }
2791
2792 template< bool onlyCount, const char * fieldID >
2793 Lang::GraphMethod_partition< onlyCount, fieldID >::~GraphMethod_partition( )
2794 { }
2795
2796 template< bool onlyCount, const char * fieldID >
2797 void
2798 Lang::GraphMethod_partition< onlyCount, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2799 {
2800         args.applyDefaults( callLoc );
2801
2802         if( ! self_->graph( )->partitioned( ) ){
2803                 throw Exceptions::CoreRequirement( "Requesting partiion in a graph which is not partitioned.", coreLoc_, callLoc );
2804         }
2805
2806         try
2807                 {
2808                         Kernel::ContRef cont = evalState->cont_;
2809                         if( onlyCount )
2810                                 cont->takeValue( Kernel::ValueRef( new Lang::Integer( static_cast< Lang::Integer::ValueType >( self_->getPartitionSize( args.getValue( 0 ) ) ) ) ),
2811                                                                                                  evalState );
2812                         else
2813                                 cont->takeValue( self_->getPartition( args.getValue( 0 ), self_ ),
2814                                                                                                  evalState );
2815                 }
2816         catch( const Exceptions::InvalidGraphKeyType & ball )
2817                 {
2818                         throw Exceptions::CoreTypeMismatch( callLoc, coreLoc_, args, 0, Exceptions::GraphKeyTypeMismatch::expectedType );
2819                 }
2820         catch( const Exceptions::InvalidGraphKey & ball )
2821                 {
2822                         throw Exceptions::GraphKeyOutOfRange( Exceptions::GraphKeyOutOfRange::PARTITION, callLoc, coreLoc_, args, 0 );
2823                 }
2824 }
2825
2826
2827 Lang::GraphMethod_isNode::GraphMethod_isNode( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2828         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2829 {
2830         formals_->appendEvaluatedCoreFormal( "node", Kernel::THE_SLOT_VARIABLE );
2831 }
2832
2833 Lang::GraphMethod_isNode::~GraphMethod_isNode( )
2834 { }
2835
2836 void
2837 Lang::GraphMethod_isNode::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2838 {
2839         args.applyDefaults( callLoc );
2840
2841         typedef const Lang::Node ArgType;
2842         RefCountPtr< ArgType > node = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 0, callLoc );
2843
2844         Kernel::ContRef cont = evalState->cont_;
2845         cont->takeValue( Kernel::ValueRef( new Lang::Boolean( self_ == node->graph( ) ) ),
2846                                                                          evalState );
2847 }
2848
2849 Lang::GraphMethod_isEdge::GraphMethod_isEdge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2850         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2851 {
2852         formals_->appendEvaluatedCoreFormal( "edge", Kernel::THE_SLOT_VARIABLE );
2853 }
2854
2855 Lang::GraphMethod_isEdge::~GraphMethod_isEdge( )
2856 { }
2857
2858 void
2859 Lang::GraphMethod_isEdge::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2860 {
2861         args.applyDefaults( callLoc );
2862
2863         typedef const Lang::Edge ArgType;
2864         RefCountPtr< ArgType > edge = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 0, callLoc );
2865
2866         Kernel::ContRef cont = evalState->cont_;
2867         cont->takeValue( Kernel::ValueRef( new Lang::Boolean( self_ == edge->graph( ) ) ),
2868                                                                          evalState );
2869 }
2870
2871 Lang::GraphMethod_isKey::GraphMethod_isKey( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2872         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2873 {
2874         formals_->appendEvaluatedCoreFormal( "key", Kernel::THE_SLOT_VARIABLE );
2875 }
2876
2877 Lang::GraphMethod_isKey::~GraphMethod_isKey( )
2878 { }
2879
2880 void
2881 Lang::GraphMethod_isKey::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2882 {
2883         args.applyDefaults( callLoc );
2884
2885         try
2886                 {
2887                         Kernel::ContRef cont = evalState->cont_;
2888                         cont->takeValue( Kernel::ValueRef( new Lang::Boolean( self_->graph( )->isKey( args.getValue( 0 ) ) ) ),
2889                                                                                          evalState );
2890
2891                 }
2892         catch( const Exceptions::InvalidGraphKeyType & ball )
2893                 {
2894                         throw Exceptions::CoreTypeMismatch( callLoc, coreLoc_, args, 0, Exceptions::GraphKeyTypeMismatch::expectedType );
2895                 }
2896 }
2897
2898 Lang::GraphMethod_indexNode::GraphMethod_indexNode( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2899         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2900 {
2901         formals_->appendEvaluatedCoreFormal( "index", Kernel::THE_SLOT_VARIABLE );
2902 }
2903
2904 Lang::GraphMethod_indexNode::~GraphMethod_indexNode( )
2905 { }
2906
2907 void
2908 Lang::GraphMethod_indexNode::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2909 {
2910         args.applyDefaults( callLoc );
2911
2912         size_t argsi = 0;
2913         typedef const Lang::Integer ArgType;
2914         ArgType::ValueType indexSigned = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, argsi, callLoc )->val_;
2915
2916         if( indexSigned < 0 )
2917                 throw Exceptions::CoreOutOfRange( callLoc, coreLoc_, args, argsi, "The node index cannot be negative." );
2918         size_t index = static_cast< size_t >( indexSigned );
2919         if( self_->graph( )->nodeCount( ) <= index )
2920                 throw Exceptions::CoreOutOfRange( callLoc, coreLoc_, args, argsi, "The node index must be less than the number of nodes in the graph." );
2921
2922         RefCountPtr< const Lang::Node > node = self_->graph( )->indexNode( self_, index );
2923         Kernel::ContRef cont = evalState->cont_;
2924         cont->takeValue( node, evalState );
2925 }
2926
2927 Lang::GraphMethod_indexEdge::GraphMethod_indexEdge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2928         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2929 {
2930         formals_->appendEvaluatedCoreFormal( "index", Kernel::THE_SLOT_VARIABLE );
2931 }
2932
2933 Lang::GraphMethod_indexEdge::~GraphMethod_indexEdge( )
2934 { }
2935
2936 void
2937 Lang::GraphMethod_indexEdge::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2938 {
2939         args.applyDefaults( callLoc );
2940
2941         size_t argsi = 0;
2942         typedef const Lang::Integer ArgType;
2943         ArgType::ValueType indexSigned = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, argsi, callLoc )->val_;
2944
2945         if( indexSigned < 0 )
2946                 throw Exceptions::CoreOutOfRange( callLoc, coreLoc_, args, argsi, "The edge index cannot be negative." );
2947         size_t index = static_cast< size_t >( indexSigned );
2948         if( self_->graph( )->edgeCount( ) <= index )
2949                 throw Exceptions::CoreOutOfRange( callLoc, coreLoc_, args, argsi, "The edge index must be less than the number of edges in the graph." );
2950
2951         RefCountPtr< const Lang::Edge > edge = self_->graph( )->indexEdge( self_, index );
2952         Kernel::ContRef cont = evalState->cont_;
2953         cont->takeValue( edge, evalState );
2954 }
2955
2956 Lang::GraphMethod_find_node::GraphMethod_find_node( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2957         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2958 {
2959         formals_->appendEvaluatedCoreFormal( "key", Kernel::THE_SLOT_VARIABLE );
2960 }
2961
2962 Lang::GraphMethod_find_node::~GraphMethod_find_node( )
2963 { }
2964
2965 void
2966 Lang::GraphMethod_find_node::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
2967 {
2968         args.applyDefaults( callLoc );
2969
2970         try
2971                 {
2972                         RefCountPtr< const Lang::Node > node = self_->graph( )->findNode( self_, args.getValue( 0 ) );
2973                         Kernel::ContRef cont = evalState->cont_;
2974                         cont->takeValue( node, evalState );
2975                 }
2976         catch( const Exceptions::InvalidGraphKeyType & ball )
2977                 {
2978                         throw Exceptions::CoreTypeMismatch( callLoc, coreLoc_, args, 0, Exceptions::GraphKeyTypeMismatch::expectedType );
2979                 }
2980         catch( const Exceptions::InvalidGraphKey & ball )
2981                 {
2982                         throw Exceptions::GraphKeyOutOfRange( Exceptions::GraphKeyOutOfRange::NODE, callLoc, coreLoc_, args, 0 );
2983                 }
2984 }
2985
2986
2987 template< bool directed, bool undirected, const char * fieldID >
2988 Lang::GraphMethod_find_edges< directed, undirected, fieldID >::GraphMethod_find_edges( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
2989         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
2990 {
2991         formals_->appendEvaluatedCoreFormal( "source", Kernel::THE_VOID_VARIABLE );
2992         formals_->appendEvaluatedCoreFormal( "target", Kernel::THE_VOID_VARIABLE );
2993         formals_->appendEvaluatedCoreFormal( "label", Kernel::THE_VOID_VARIABLE );
2994         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
2995 }
2996
2997 template< bool directed, bool undirected, const char * fieldID >
2998 Lang::GraphMethod_find_edges< directed, undirected, fieldID >::~GraphMethod_find_edges( )
2999 { }
3000
3001 template< bool directed, bool undirected, const char * fieldID >
3002 void
3003 Lang::GraphMethod_find_edges< directed, undirected, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3004 {
3005         args.applyDefaults( callLoc );
3006
3007         if( ! ( ( directed && self_->graph( )->domain( ).directed( ) ) || ( undirected && self_->graph( )->domain( ).undirected( ) ) ) ){
3008                 if( directed && undirected )
3009                         WARN_OR_THROW( Exceptions::CoreRequirement( "The graph domain does not permit neither directed nor undirected edges.", coreLoc_, callLoc ) );
3010                 if( directed )
3011                         WARN_OR_THROW( Exceptions::CoreRequirement( "The graph domain does not permit directed edges.", coreLoc_, callLoc ) );
3012                 if( undirected )
3013                         WARN_OR_THROW( Exceptions::CoreRequirement( "The graph domain does not permit undirected edges.", coreLoc_, callLoc ) );
3014                 Kernel::ContRef cont = evalState->cont_;
3015                 cont->takeValue( Lang::THE_CONS_NULL,
3016                                                                                  evalState );
3017                 return;
3018         }
3019
3020         size_t argsi = 0;
3021         Kernel::Node * source = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3022
3023         ++argsi;
3024         Kernel::Node * target = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3025
3026         ++argsi;
3027         Kernel::ValueRef label = args.getValue( argsi );
3028         if( ! ( label == Lang::THE_VOID
3029                                         || dynamic_cast< const Lang::Symbol * >( label.getPtr( ) ) != 0
3030                                         || dynamic_cast< const Lang::Integer * >( label.getPtr( ) ) != 0 ) ){
3031                 throw Exceptions::CoreTypeMismatch( callLoc, coreLoc_, args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
3032         }
3033
3034         ++argsi;
3035         typedef const Lang::Boolean ArgType;
3036         bool loops = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, argsi, callLoc )->val_;
3037
3038         Lang::Graph::ListRef res = self_->graph( )->findEdges( self_, source, target, directed, undirected, loops, label );
3039
3040         Kernel::ContRef cont = evalState->cont_;
3041         cont->takeValue( res,
3042                                                                          evalState );
3043 }
3044
3045
3046 template< bool directed, bool undirected, const char * fieldID >
3047 Lang::GraphMethod_find_multiedges< directed, undirected, fieldID >::GraphMethod_find_multiedges( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
3048         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
3049 {
3050         formals_->appendEvaluatedCoreFormal( "source", Kernel::THE_VOID_VARIABLE );
3051         formals_->appendEvaluatedCoreFormal( "target", Kernel::THE_VOID_VARIABLE );
3052         formals_->appendEvaluatedCoreFormal( "loops", Kernel::THE_TRUE_VARIABLE );
3053 }
3054
3055 template< bool directed, bool undirected, const char * fieldID >
3056 Lang::GraphMethod_find_multiedges< directed, undirected, fieldID >::~GraphMethod_find_multiedges( )
3057 { }
3058
3059 template< bool directed, bool undirected, const char * fieldID >
3060 void
3061 Lang::GraphMethod_find_multiedges< directed, undirected, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3062 {
3063         args.applyDefaults( callLoc );
3064
3065         if( ! ( ( directed && self_->graph( )->domain( ).directed( ) ) || ( undirected && self_->graph( )->domain( ).undirected( ) ) ) ){
3066                 if( directed && undirected )
3067                         WARN_OR_THROW( Exceptions::CoreRequirement( "The graph domain does not permit neither directed nor undirected edges.", coreLoc_, callLoc ) );
3068                 if( directed )
3069                         WARN_OR_THROW( Exceptions::CoreRequirement( "The graph domain does not permit directed edges.", coreLoc_, callLoc ) );
3070                 if( undirected )
3071                         WARN_OR_THROW( Exceptions::CoreRequirement( "The graph domain does not permit undirected edges.", coreLoc_, callLoc ) );
3072                 Kernel::ContRef cont = evalState->cont_;
3073                 cont->takeValue( Lang::THE_CONS_NULL,
3074                                                                                  evalState );
3075                 return;
3076         }
3077
3078         size_t argsi = 0;
3079         Kernel::Node * source = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3080
3081         ++argsi;
3082         Kernel::Node * target = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3083
3084         ++argsi;
3085         typedef const Lang::Boolean ArgType;
3086         bool loops = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, argsi, callLoc )->val_;
3087
3088         Lang::Graph::ListRef res = self_->graph( )->findMultiEdges( self_, source, target, directed, undirected, loops );
3089
3090         Kernel::ContRef cont = evalState->cont_;
3091         cont->takeValue( res,
3092                                                                          evalState );
3093 }
3094
3095
3096 template< bool directed, bool undirected, const char * fieldID >
3097 Lang::GraphMethod_the_edge< directed, undirected, fieldID >::GraphMethod_the_edge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
3098         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
3099 {
3100         formals_->appendEvaluatedCoreFormal( "source", Kernel::THE_SLOT_VARIABLE );
3101         formals_->appendEvaluatedCoreFormal( "target", Kernel::THE_SLOT_VARIABLE );
3102         formals_->appendEvaluatedCoreFormal( "label", Kernel::THE_VOID_VARIABLE );
3103 }
3104
3105 template< bool directed, bool undirected, const char * fieldID >
3106 Lang::GraphMethod_the_edge< directed, undirected, fieldID >::~GraphMethod_the_edge( )
3107 { }
3108
3109 template< bool directed, bool undirected, const char * fieldID >
3110 void
3111 Lang::GraphMethod_the_edge< directed, undirected, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3112 {
3113         args.applyDefaults( callLoc );
3114
3115         if( ! ( ( directed && self_->graph( )->domain( ).directed( ) ) || ( undirected && self_->graph( )->domain( ).undirected( ) ) ) ){
3116                 if( directed && undirected )
3117                         throw Exceptions::CoreRequirement( "The graph domain does not permit neither directed nor undirected edges.", coreLoc_, callLoc );
3118                 if( directed )
3119                         throw Exceptions::CoreRequirement( "The graph domain does not permit directed edges.", coreLoc_, callLoc );
3120                 if( undirected )
3121                         throw Exceptions::CoreRequirement( "The graph domain does not permit undirected edges.", coreLoc_, callLoc );
3122         }
3123
3124         size_t argsi = 0;
3125         Kernel::Node * source = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3126
3127         ++argsi;
3128         Kernel::Node * target = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3129
3130         ++argsi;
3131         Kernel::ValueRef label = args.getValue( argsi );
3132         if( ! ( label == Lang::THE_VOID
3133                                         || dynamic_cast< const Lang::Symbol * >( label.getPtr( ) ) != 0
3134                                         || dynamic_cast< const Lang::Integer * >( label.getPtr( ) ) != 0 ) ){
3135                 throw Exceptions::CoreTypeMismatch( callLoc, coreLoc_, args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
3136         }
3137
3138         Lang::Graph::ListRef edges = self_->graph( )->findEdges( self_, source, target, directed, undirected, true, label );
3139         RefCountPtr< const Lang::SingleListPair > p = edges.down_cast< const Lang::SingleListPair >( );
3140         if( p == NullPtr< const Lang::SingleListPair >( ) ){
3141                 throw Exceptions::CoreRequirement( "Illegal reference to \"the edge\" since there is no matching edge.", coreLoc_, callLoc );
3142         }
3143         RefCountPtr< const Lang::Value > res = p->car_->getUntyped( );
3144         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
3145         if( p != NullPtr< const Lang::SingleListPair >( ) ){
3146                 throw Exceptions::CoreRequirement( "Illegal reference to \"the edge\" since there is more than one matching edge.", coreLoc_, callLoc );
3147         }
3148
3149         Kernel::ContRef cont = evalState->cont_;
3150         cont->takeValue( res,
3151                                                                          evalState );
3152 }
3153
3154
3155 template< bool directed, bool undirected, const char * fieldID >
3156 Lang::GraphMethod_the_multiedge< directed, undirected, fieldID >::GraphMethod_the_multiedge( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
3157         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
3158 {
3159         formals_->appendEvaluatedCoreFormal( "source", Kernel::THE_SLOT_VARIABLE );
3160         formals_->appendEvaluatedCoreFormal( "target", Kernel::THE_SLOT_VARIABLE );
3161 }
3162
3163 template< bool directed, bool undirected, const char * fieldID >
3164 Lang::GraphMethod_the_multiedge< directed, undirected, fieldID >::~GraphMethod_the_multiedge( )
3165 { }
3166
3167 template< bool directed, bool undirected, const char * fieldID >
3168 void
3169 Lang::GraphMethod_the_multiedge< directed, undirected, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3170 {
3171         args.applyDefaults( callLoc );
3172
3173         if( ! ( ( directed && self_->graph( )->domain( ).directed( ) ) || ( undirected && self_->graph( )->domain( ).undirected( ) ) ) ){
3174                 if( directed && undirected )
3175                         throw Exceptions::CoreRequirement( "The graph domain does not permit neither directed nor undirected edges.", coreLoc_, callLoc );
3176                 if( directed )
3177                         throw Exceptions::CoreRequirement( "The graph domain does not permit directed edges.", coreLoc_, callLoc );
3178                 if( undirected )
3179                         throw Exceptions::CoreRequirement( "The graph domain does not permit undirected edges.", coreLoc_, callLoc );
3180         }
3181
3182         size_t argsi = 0;
3183         Kernel::Node * source = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3184
3185         ++argsi;
3186         Kernel::Node * target = self_->kernelNodeByValue( args, argsi, true, coreLoc_, callLoc );
3187
3188         Lang::Graph::ListRef edges = self_->graph( )->findMultiEdges( self_, source, target, directed, undirected, true );
3189         RefCountPtr< const Lang::SingleListPair > p = edges.down_cast< const Lang::SingleListPair >( );
3190         if( p == NullPtr< const Lang::SingleListPair >( ) ){
3191                 throw Exceptions::CoreRequirement( "Illegal reference to \"the multiedge\" since there is no matching multiedge.", coreLoc_, callLoc );
3192         }
3193         RefCountPtr< const Lang::Value > res = p->car_->getUntyped( );
3194         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
3195         if( p != NullPtr< const Lang::SingleListPair >( ) ){
3196                 throw Exceptions::CoreRequirement( "Illegal reference to \"the multiedge\" since there is more than one matching multiedge.", coreLoc_, callLoc );
3197         }
3198
3199         Kernel::ContRef cont = evalState->cont_;
3200         cont->takeValue( res,
3201                                                                          evalState );
3202 }
3203
3204
3205 Lang::GraphMethod_rekey_with_index::GraphMethod_rekey_with_index( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
3206         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
3207 {
3208         formals_->appendEvaluatedCoreFormal( "offset", Helpers::newValHandle( new Lang::Integer( 0 ) ) );
3209 }
3210
3211 Lang::GraphMethod_rekey_with_index::~GraphMethod_rekey_with_index( )
3212 { }
3213
3214 void
3215 Lang::GraphMethod_rekey_with_index::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3216 {
3217         args.applyDefaults( callLoc );
3218
3219         typedef const Lang::Integer ArgType;
3220         ArgType::ValueType offset = Helpers::down_cast_CoreArgument< ArgType >( coreLoc_, args, 0, callLoc )->val_;
3221
3222         Kernel::ContRef cont = evalState->cont_;
3223         cont->takeValue( Kernel::ValueRef( new Lang::Graph( *self_, offset ) ),
3224                                                                          evalState );
3225 }
3226
3227 namespace Shapes
3228 {
3229         namespace Kernel
3230         {
3231
3232                 class GraphMethod_with_values_cont : public Kernel::Continuation
3233                 {
3234                         RefCountPtr< const Lang::Graph > self_;
3235                         Kernel::Graph::ItemType item_;
3236                         Kernel::ContRef cont_;
3237                         RefCountPtr< const Interaction::CoreLocation > coreLoc_;
3238                 public:
3239                         GraphMethod_with_values_cont( const RefCountPtr< const Lang::Graph > & self, Kernel::Graph::ItemType item, const Kernel::ContRef & cont, const RefCountPtr< const Interaction::CoreLocation > & coreLoc, const Ast::SourceLocation & callLoc );
3240                         virtual ~GraphMethod_with_values_cont( );
3241                         virtual void takeValue( const RefCountPtr< const Lang::Value > & val, Kernel::EvalState * evalState, bool dummy ) const;
3242                         virtual Kernel::ContRef up( ) const;
3243                         virtual RefCountPtr< const char > description( ) const;
3244                         virtual void gcMark( Kernel::GCMarkedSet & marked );
3245                 };
3246
3247                 class GraphMethod_subgraph_cont : public Kernel::Continuation
3248                 {
3249                         RefCountPtr< const Lang::Graph > self_;
3250                         Kernel::Graph::SubgraphKind kind_;
3251                         Kernel::ContRef cont_;
3252                 public:
3253                         GraphMethod_subgraph_cont( const RefCountPtr< const Lang::Graph > & self, Kernel::Graph::SubgraphKind kind, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc );
3254                         virtual ~GraphMethod_subgraph_cont( );
3255                         virtual void takeValue( const RefCountPtr< const Lang::Value > & val, Kernel::EvalState * evalState, bool dummy ) const;
3256                         virtual Kernel::ContRef up( ) const;
3257                         virtual RefCountPtr< const char > description( ) const;
3258                         virtual void gcMark( Kernel::GCMarkedSet & marked );
3259                 };
3260
3261         }
3262 }
3263
3264 template< Kernel::Graph::ItemType item, const char * fieldID >
3265 Lang::GraphMethod_with_values< item, fieldID >::GraphMethod_with_values( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
3266         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
3267 {
3268         formals_->appendEvaluatedCoreFormal( "values", Kernel::THE_SLOT_VARIABLE );
3269 }
3270
3271 template< Kernel::Graph::ItemType item, const char * fieldID >
3272 Lang::GraphMethod_with_values< item, fieldID >::~GraphMethod_with_values( )
3273 { }
3274
3275 template< Kernel::Graph::ItemType item, const char * fieldID >
3276 void
3277 Lang::GraphMethod_with_values< item, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3278 {
3279         args.applyDefaults( callLoc );
3280
3281         size_t argsi = 0;
3282         RefCountPtr< const Lang::Value > nodes = args.getValue( argsi );
3283         Kernel::ContRef cont = Kernel::ContRef( new Kernel::ForcingListContinuation
3284                                                                                                                                                                         ( Kernel::ContRef( new Kernel::GraphMethod_with_values_cont( self_, item, evalState->cont_, coreLoc_, callLoc ) ),
3285                                                                                                                                                                                 args.getLoc( argsi ),
3286                                                                                                                                                                                 false ) );
3287         evalState->cont_ = cont;
3288         cont->takeValue( nodes, evalState );
3289 }
3290
3291 Kernel::GraphMethod_with_values_cont::GraphMethod_with_values_cont( const RefCountPtr< const Lang::Graph > & self, Kernel::Graph::ItemType item, const Kernel::ContRef & cont, const RefCountPtr< const Interaction::CoreLocation > & coreLoc, const Ast::SourceLocation & callLoc )
3292         : Kernel::Continuation( callLoc ), self_( self ), item_( item ), cont_( cont ), coreLoc_( coreLoc )
3293 { }
3294
3295 Kernel::GraphMethod_with_values_cont::~GraphMethod_with_values_cont( )
3296 { }
3297
3298 void
3299 Kernel::GraphMethod_with_values_cont::takeValue( const RefCountPtr< const Lang::Value > & nodesUntyped, Kernel::EvalState * evalState, bool dummy ) const
3300 {
3301         typedef const Lang::SingleList ArgType;
3302         RefCountPtr< ArgType > values = Helpers::down_cast< ArgType >( nodesUntyped, "< Internal error situation in GraphMethod_with_values_cont >" );
3303
3304         RefCountPtr< Lang::Graph::ValueVector > valuesVec = RefCountPtr< Lang::Graph::ValueVector >( new Lang::Graph::ValueVector( ) );
3305         size_t valuesSize = 0; /* Initialize to quiet compiler warning. */
3306         switch( item_ )
3307                 {
3308                 case Kernel::Graph::NODE:
3309                         valuesSize = self_->graph( )->nodeCount( );
3310                         break;
3311                 case Kernel::Graph::EDGE:
3312                         valuesSize = self_->graph( )->edgeCount( );
3313                         break;
3314                 }
3315         valuesVec->reserve( valuesSize );
3316
3317         RefCountPtr< const Lang::SingleListPair > p = values.down_cast< const Lang::SingleListPair >( );
3318         for( size_t i = 0; i < valuesSize; ++i ){
3319                 if( p == NullPtr< const Lang::SingleListPair >( ) ){
3320                         switch( item_ )
3321                                 {
3322                                 case Kernel::Graph::NODE:
3323                                         throw Exceptions::CoreRequirement( "The number of values is less than the number of nodes.", coreLoc_, traceLoc_ );
3324                                 case Kernel::Graph::EDGE:
3325                                         throw Exceptions::CoreRequirement( "The number of values is less than the number of edges.", coreLoc_, traceLoc_ );
3326                                 }
3327                 }
3328                 valuesVec->push_back( p->car_->getUntyped( ) );
3329                 p = p->cdr_.down_cast< const Lang::SingleListPair >( );
3330         }
3331         if( p != NullPtr< const Lang::SingleListPair >( ) ){
3332                 switch( item_ )
3333                         {
3334                         case Kernel::Graph::NODE:
3335                                 throw Exceptions::CoreRequirement( "The number of values exceeds the number of nodes.", coreLoc_, traceLoc_ );
3336                         case Kernel::Graph::EDGE:
3337                                 throw Exceptions::CoreRequirement( "The number of values exceeds the number of edges.", coreLoc_, traceLoc_ );
3338                         }
3339         }
3340
3341         evalState->cont_ = cont_;
3342         switch( item_ )
3343                 {
3344                 case Kernel::Graph::NODE:
3345                         cont_->takeValue( Kernel::ValueRef( new Lang::Graph( self_->graph( ), valuesVec, self_->edgeValues( ) ) ),
3346                                                                                                 evalState );
3347                         break;
3348                 case Kernel::Graph::EDGE:
3349                         cont_->takeValue( Kernel::ValueRef( new Lang::Graph( self_->graph( ), self_->nodeValues( ), valuesVec ) ),
3350                                                                                                 evalState );
3351                         break;
3352                 }
3353 }
3354
3355 Kernel::ContRef
3356 Kernel::GraphMethod_with_values_cont::up( ) const
3357 {
3358         return cont_;
3359 }
3360
3361 RefCountPtr< const char >
3362 Kernel::GraphMethod_with_values_cont::description( ) const
3363 {
3364         switch( item_ )
3365                 {
3366                 case Kernel::Graph::NODE:
3367                         return strrefdup( "graph with new node values" );
3368                 case Kernel::Graph::EDGE:
3369                         return strrefdup( "graph with new edge values" );
3370                 }
3371         /* Not sure how to deal with compiler warnings here.
3372          * Seems hard to address with the following two possible warnings at the same time:
3373          *   1) Reaching end of non-void function.
3374          *   2) Dead code.
3375          */
3376         throw Exceptions::InternalError( "Kernel::GraphMethod_with_values_cont::description: Reached code that should be dead at end of non-void function." );
3377 }
3378
3379 void
3380 Kernel::GraphMethod_with_values_cont::gcMark( Kernel::GCMarkedSet & marked )
3381 {
3382         const_cast< Lang::Graph * >( self_.getPtr( ) )->gcMark( marked );
3383         cont_->gcMark( marked );
3384 }
3385
3386
3387 template< Kernel::Graph::SubgraphKind kind, const char * fieldID >
3388 Lang::GraphMethod_subgraph< kind, fieldID >::GraphMethod_subgraph( RefCountPtr< const Lang::Graph > self, const Ast::FileID * fullMethodID )
3389         : Lang::MethodBase< Lang::Graph >( self, fullMethodID, false, true )
3390 {
3391         switch( kind )
3392                 {
3393                 case Kernel::Graph::INDUCED:
3394                         formals_->appendEvaluatedCoreFormal( "nodes", Kernel::THE_SLOT_VARIABLE );
3395                         break;
3396                 case Kernel::Graph::SPANNING:
3397                         formals_->appendEvaluatedCoreFormal( "edges", Kernel::THE_SLOT_VARIABLE );
3398                         break;
3399                 }
3400 }
3401
3402 template< Kernel::Graph::SubgraphKind kind, const char * fieldID >
3403 Lang::GraphMethod_subgraph< kind, fieldID >::~GraphMethod_subgraph( )
3404 { }
3405
3406 template< Kernel::Graph::SubgraphKind kind, const char * fieldID >
3407 void
3408 Lang::GraphMethod_subgraph< kind, fieldID >::call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3409 {
3410         args.applyDefaults( callLoc );
3411
3412         size_t argsi = 0;
3413         RefCountPtr< const Lang::Value > nodes = args.getValue( argsi );
3414         Kernel::ContRef cont = Kernel::ContRef( new Kernel::ForcingListContinuation
3415                                                                                                                                                                         ( Kernel::ContRef( new Kernel::GraphMethod_subgraph_cont( self_, kind, evalState->cont_, callLoc ) ),
3416                                                                                                                                                                                 args.getLoc( argsi ),
3417                                                                                                                                                                                 false ) );
3418         evalState->cont_ = cont;
3419         cont->takeValue( nodes, evalState );
3420 }
3421
3422 Kernel::GraphMethod_subgraph_cont::GraphMethod_subgraph_cont( const RefCountPtr< const Lang::Graph > & self, Kernel::Graph::SubgraphKind kind, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc )
3423         : Kernel::Continuation( callLoc ), self_( self ), kind_( kind ), cont_( cont )
3424 { }
3425
3426 Kernel::GraphMethod_subgraph_cont::~GraphMethod_subgraph_cont( )
3427 { }
3428
3429 void
3430 Kernel::GraphMethod_subgraph_cont::takeValue( const RefCountPtr< const Lang::Value > & nodesUntyped, Kernel::EvalState * evalState, bool dummy ) const
3431 {
3432         typedef const Lang::SingleList ArgType;
3433         RefCountPtr< ArgType > nodes = Helpers::down_cast< ArgType >( nodesUntyped, "< Internal error situation in GraphMethod_subgraph_cont >" );
3434
3435         std::set< size_t > indices;
3436         RefCountPtr< const Lang::SingleListPair > p = nodes.down_cast< const Lang::SingleListPair >( );
3437         while( p != NullPtr< const Lang::SingleListPair >( ) ){
3438                 size_t index;
3439                 switch( kind_ )
3440                         {
3441                         case Kernel::Graph::INDUCED:
3442                                 {
3443                                         RefCountPtr< const Lang::Node > node = p->car_->getVal< const Lang::Node >( "Node to include in subgraph." );
3444                                         if( node->graph( ) != self_ )
3445                                                 throw Exceptions::InvalidGraphElement( Exceptions::InvalidGraphElement::NODE, traceLoc_ );
3446                                         index = node->node( )->index( );
3447                                 }
3448                                 break;
3449                         case Kernel::Graph::SPANNING:
3450                                 {
3451                                         RefCountPtr< const Lang::Edge > edge = p->car_->getVal< const Lang::Edge >( "Edge to include in subgraph." );
3452                                         if( edge->graph( ) != self_ )
3453                                                 throw Exceptions::InvalidGraphElement( Exceptions::InvalidGraphElement::EDGE, traceLoc_ );
3454                                         index = edge->edge( )->index( );
3455                                 }
3456                                 break;
3457                         }
3458                 indices.insert( indices.begin( ), index );
3459                 p = p->cdr_.down_cast< const Lang::SingleListPair >( );
3460         }
3461
3462         evalState->cont_ = cont_;
3463         cont_->takeValue( Kernel::ValueRef( new Lang::Graph( *self_, indices, kind_ ) ),
3464                                                                                 evalState );
3465 }
3466
3467 Kernel::ContRef
3468 Kernel::GraphMethod_subgraph_cont::up( ) const
3469 {
3470         return cont_;
3471 }
3472
3473 RefCountPtr< const char >
3474 Kernel::GraphMethod_subgraph_cont::description( ) const
3475 {
3476         switch( kind_ )
3477                 {
3478                 case Kernel::Graph::INDUCED:
3479                         return strrefdup( "construct induced subgraph" );
3480                 case Kernel::Graph::SPANNING:
3481                         return strrefdup( "construct spanning subgraph" );
3482                 }
3483         /* Not sure how to deal with compiler warnings here.
3484          * Seems hard to address with the following two possible warnings at the same time:
3485          *   1) Reaching end of non-void function.
3486          *   2) Dead code.
3487          */
3488         throw Exceptions::InternalError( "Kernel::GraphMethod_subgraph_cont::description: Reached code that should be dead at end of non-void function." );
3489 }
3490
3491 void
3492 Kernel::GraphMethod_subgraph_cont::gcMark( Kernel::GCMarkedSet & marked )
3493 {
3494         const_cast< Lang::Graph * >( self_.getPtr( ) )->gcMark( marked );
3495         cont_->gcMark( marked );
3496 }
3497
3498
3499 Lang::Walk::Walk( const RefCountPtr< const Lang::Graph > & graph, const RefCountPtr< const Lang::Node > & first, const RefCountPtr< const Lang::Node > & last, const RefCountPtr< const Lang::SingleList > & edges, const Ast::SourceLocation & edgesLoc, const Ast::SourceLocation & callLoc )
3500         : graph_( graph ), first_( first ), last_( last ), edges_( edges )
3501 {
3502         /* First check type of all edges and put in a std::list. */
3503         std::list< const Lang::Edge * > edgeList;
3504         typedef typeof edgeList EdgeListType;
3505         edgeCount_ = 0;
3506         {
3507                 RefCountPtr< const Lang::SingleListPair > p = edges_.down_cast< const Lang::SingleListPair >( );
3508                 while( p != NullPtr< const Lang::SingleListPair >( ) ){
3509                         ++edgeCount_;
3510                         RefCountPtr< const Lang::Value > val = p->car_->getUntyped( );
3511                         const Lang::Edge * e = dynamic_cast< const Lang::Edge * >( val.getPtr( ) );
3512                         if( e == NULL ){
3513                                 throw Exceptions::TypeMismatch( edgesLoc, "Element in list of walk edges", val->getTypeName( ), Lang::Edge::staticTypeName( ) );
3514                         }
3515                         edgeList.push_back( e );
3516                         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
3517                 }
3518         }
3519
3520         /* The given <first> and <last> nodes may be null pointers, in which case they have to be determined from the
3521          * other arguments.
3522          */
3523
3524         /* Make sure that first_ is defined. */
3525         if( first_ == NullPtr< const Lang::Node >( ) ){
3526                 if( edgeList.size( ) == 0 ){
3527                         if( last_ == NullPtr< const Lang::Node >( ) ){
3528                                 throw Exceptions::MiscellaneousRequirement( callLoc, "Either start or end node must be specified for an empty walk." );
3529                         }else{
3530                                 first_ = last_;
3531                         }
3532                 }else{
3533                         RefCountPtr< const Lang::SingleListPair > p = edges_.down_cast< const Lang::SingleListPair >( );
3534                         RefCountPtr< const Lang::Edge > firstEdge = p->car_->getVal< const Lang::Edge >( "(internal error)" );
3535                         bool firstEdgeDirected = firstEdge->directed( );
3536                         EdgeListType::const_iterator e = edgeList.begin( );
3537                         const Kernel::Edge * ke = (*e)->edge( );
3538                         const Kernel::Node * n11 = ke->source( );
3539                         const Kernel::Node * n12 = ke->target( );
3540                         if( firstEdgeDirected || n11 == n12 ){
3541                                 first_ = RefCountPtr< const Lang::Node >( new Lang::Node( graph_, n11 ) );
3542                         }else{
3543                                 if( edgeList.size( ) == 1 ){
3544                                         if( last_ == NullPtr< const Lang::Node >( ) ){
3545                                                 throw Exceptions::MiscellaneousRequirement( callLoc, "Either start or end node must be specified for a walk consisting of a single undirected edge." );
3546                                         }else{
3547                                                 first_ = RefCountPtr< const Lang::Node >( new Lang::Node( graph_, firstEdge->backtrace( last_->node( ), callLoc ) ) );
3548                                         }
3549                                 }else{
3550                                         /* There are at least two edges, and the first is undirected and not a loop. */
3551                                         ++e;
3552                                         ke = (*e)->edge( );
3553                                         const Kernel::Node * n21 = ke->source( );
3554                                         const Kernel::Node * n22 = ke->target( );
3555                                         if( n11 == n21 || n11 == n22){
3556                                                 first_ = RefCountPtr< const Lang::Node >( new Lang::Node( graph_, n12 ) );
3557                                         }else if( n12 == n21 || n12 == n22){
3558                                                 first_ = RefCountPtr< const Lang::Node >( new Lang::Node( graph_, n11 ) );
3559                                         }else{
3560                                                 throw Exceptions::MiscellaneousRequirement( callLoc, "The first two edges does not have a common node." );
3561                                         }
3562                                 }
3563                         }
3564                 }
3565         }
3566
3567         if( first_->graph( ) != graph_ ){
3568                 /* The caller is responsible for checking that the start and end nodes belong to the graph. */
3569                 throw Exceptions::InternalError( "Lang::Walk::Walk: The start node does not belong to the graph." );
3570         }
3571
3572
3573         const Kernel::Node * n = first_->node( );
3574
3575         simple_ = true; /* Initialize to true, set to false if detecting repeated node. */
3576         trail_ = true;  /* Initialize to true, set to false if detecting repeated edge. */
3577
3578         {
3579                 typedef std::set< const Kernel::Node * > NodeSet;
3580                 typedef std::set< const Kernel::Edge * > EdgeSet;
3581                 NodeSet coveredNodes;
3582                 EdgeSet coveredEdges;
3583
3584                 coveredNodes.insert( n );
3585
3586                 for( EdgeListType::const_iterator e = edgeList.begin( ); e != edgeList.end( ); ++e ){
3587                         {
3588                                 const Kernel::Edge * ke = (*e)->edge( );
3589                                 EdgeSet::const_iterator j = coveredEdges.find( ke );
3590                                 if( j == coveredEdges.end( ) ){
3591                                         coveredEdges.insert( coveredEdges.begin( ), ke );
3592                                 }else{
3593                                         trail_ = false;
3594                                 }
3595                         }
3596
3597                         n = (*e)->trace( n, edgesLoc );
3598
3599                         {
3600                                 NodeSet::const_iterator j = coveredNodes.find( n );
3601                                 if( j == coveredNodes.end( ) ){
3602                                         coveredNodes.insert( coveredNodes.begin( ), n );
3603                                 }else{
3604                                         simple_ = false;
3605                                 }
3606                         }
3607                 }
3608
3609                 nodeCover_ = coveredNodes.size( ) == graph_->graph( )->nodeCount( );
3610                 edgeCover_ = coveredEdges.size( ) == graph_->graph( )->edgeCount( );
3611         }
3612
3613         /* Make sure that last_ is defined. */
3614         if( last_ == NullPtr< const Lang::Node >( ) ){
3615                 last_ = RefCountPtr< const Lang::Node >( new Lang::Node( graph_, n ) );
3616         }else{
3617                 if( last_->graph( ) != graph_ ){
3618                         /* The caller is responsible for checking that the start and end nodes belong to the graph. */
3619                         throw Exceptions::InternalError( "Lang::Walk::Walk: The end node does not belong to the graph." );
3620                 }
3621                 if( n != last_->node( ) ){
3622                         throw Exceptions::MiscellaneousRequirement( callLoc, "The given end node is not at the end of the walk." );
3623                 }
3624         }
3625 }
3626
3627 Lang::Walk::~Walk( )
3628 { }
3629
3630 RefCountPtr< const Lang::Class > Lang::Walk::TypeID( new Lang::SystemFinalClass( strrefdup( "Walk" ) ) );
3631 TYPEINFOIMPL( Walk );
3632
3633 Kernel::VariableHandle
3634 Lang::Walk::getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const
3635 {
3636         if( strcmp( fieldID, "closed?" ) == 0 )
3637                 {
3638                         return closed_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
3639                 }
3640         else if( strcmp( fieldID, "open?" ) == 0 )
3641                 {
3642                         return closed_ ? Kernel::THE_FALSE_VARIABLE : Kernel::THE_TRUE_VARIABLE;
3643                 }
3644         else if( strcmp( fieldID, "simple?" ) == 0 )
3645                 {
3646                         return simple_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
3647                 }
3648         else if( strcmp( fieldID, "trail?" ) == 0 )
3649                 {
3650                         return trail_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
3651                 }
3652         else if( strcmp( fieldID, "node_cover?" ) == 0 )
3653                 {
3654                         return nodeCover_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
3655                 }
3656         else if( strcmp( fieldID, "edge_cover?" ) == 0 )
3657                 {
3658                         return edgeCover_ ? Kernel::THE_TRUE_VARIABLE : Kernel::THE_FALSE_VARIABLE;
3659                 }
3660         else if( strcmp( fieldID, "edge_count" ) == 0 )
3661                 {
3662                         return Helpers::newValHandle( new Lang::Integer( edgeCount_) );
3663                 }
3664         else if( strcmp( fieldID, "start" ) == 0 )
3665                 {
3666                         return Kernel::VariableHandle( new Kernel::Variable( first_ ) );
3667                 }
3668         else if( strcmp( fieldID, "end" ) == 0 )
3669                 {
3670                         return Kernel::VariableHandle( new Kernel::Variable( last_ ) );
3671                 }
3672         else if( strcmp( fieldID, "edges" ) == 0 )
3673                 {
3674                         return Kernel::VariableHandle( new Kernel::Variable( edges_ ) );
3675                 }
3676         else if( strcmp( fieldID, "graph" ) == 0 )
3677                 {
3678                         return Kernel::VariableHandle( new Kernel::Variable( graph_ ) );
3679                 }
3680         throw Exceptions::NonExistentMember( getTypeName( ), fieldID );
3681 }
3682
3683 void
3684 Lang::Walk::show( std::ostream & os ) const
3685 {
3686         os << "( graph walk of length " << edgeCount_ << " )" ;
3687 }
3688
3689 void
3690 Lang::Walk::gcMark( Kernel::GCMarkedSet & marked )
3691 {
3692         /* Optimizing by only calling gcMark on graph_, since the other variables
3693          * are of controlled types and are known not to link to anything which
3694          * is not already covered by graph_.
3695          */
3696         const_cast< Lang::Graph * >( graph_.getPtr( ) )->gcMark( marked );
3697 }
3698
3699
3700 RefCountPtr< const Lang::Graph >
3701 Helpers::graphFromNodeEdgeData( const Kernel::GraphDomain & domain, const RefCountPtr< const Lang::SingleList > & partitions, const std::list< Kernel::NodeData > & nodeData, const std::list< Kernel::EdgeData > & edgeData, const Ast::SourceLocation & partitionsLoc, const Ast::SourceLocation & callLoc )
3702 {
3703         std::list< Kernel::EdgeDataIndexed > uedgeDataIndexed;
3704         std::list< Kernel::EdgeDataIndexed > dedgeDataIndexed;
3705         std::list< Kernel::LoopDataIndexed > uloopDataIndexed;
3706         std::list< Kernel::LoopDataIndexed > dloopDataIndexed;
3707
3708         std::map< int, size_t > symbolKeyIndexMap;
3709         std::map< int, size_t > integerKeyIndexMap;
3710
3711         bool hasEdgeLabels = false;
3712         bool partitioned = ( partitions != NullPtr< const Lang::SingleList >( ) );
3713
3714         if( partitioned && domain.loops( ) ){
3715                 throw Exceptions::MiscellaneousRequirement( callLoc, "The domain of a partitioned graph must not allow loops." );
3716         }
3717
3718         /* Check type and uniqueness of partition keys. */
3719         std::set< Lang::Symbol::KeyType > symKeys;
3720         std::set< Lang::Integer::ValueType > intKeys;
3721         if( partitioned ){
3722                 RefCountPtr< const Lang::SingleListPair > p = partitions.down_cast< const Lang::SingleListPair >( );
3723                 while( p != NullPtr< const Lang::SingleListPair >( ) ){
3724                         RefCountPtr< const Lang::Value > val = p->car_->getUntyped( );
3725
3726                         do{
3727
3728                                 if( const Lang::Symbol * ptr = dynamic_cast< const Lang::Symbol * >( val.getPtr( ) ) ){
3729                                         Lang::Symbol::KeyType key = ptr->getKey( );
3730                                         if( symKeys.find( key ) != symKeys.end( ) ){
3731                                                 std::ostringstream oss;
3732                                                 oss << "The graph partition key " ;
3733                                                 val->show( oss );
3734                                                 oss << " is repeated." ;
3735                                                 throw Exceptions::MiscellaneousRequirement( partitionsLoc, strrefdup( oss ) );
3736                                         }
3737                                         symKeys.insert( key );
3738                                         break;
3739                                 }
3740
3741                                 if( const Lang::Integer * ptr = dynamic_cast< const Lang::Integer * >( val.getPtr( ) ) ){
3742                                         Lang::Integer::ValueType key = ptr->val_;
3743                                         if( intKeys.find( key ) != intKeys.end( ) ){
3744                                                 std::ostringstream oss;
3745                                                 oss << "The graph partition key " ;
3746                                                 val->show( oss );
3747                                                 oss << " is repeated." ;
3748                                                 throw Exceptions::MiscellaneousRequirement( partitionsLoc, strrefdup( oss ) );
3749                                         }
3750                                         intKeys.insert( key );
3751                                         break;
3752                                 }
3753
3754                                 throw Exceptions::TypeMismatch( partitionsLoc, "Graph partition key in graph construction", val->getTypeName( ), Exceptions::GraphKeyTypeMismatch::expectedType );
3755
3756                         }while( false );
3757
3758                         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
3759                 }
3760         }
3761
3762         {
3763                 typedef typeof nodeData ListType;
3764                 size_t i = 0;
3765                 for( ListType::const_iterator n = nodeData.begin( ); n != nodeData.end( ); ++n, ++i ){
3766                         RefCountPtr< const Lang::Value > key = n->key_;
3767                         if( const Lang::Symbol * keySym = dynamic_cast< const Lang::Symbol * >( key.getPtr( ) ) ){
3768                                 symbolKeyIndexMap[ keySym->getKey( ) ] = i;
3769                         } else if( const Lang::Integer * keyInt = dynamic_cast< const Lang::Integer * >( key.getPtr( ) ) ){
3770                                 integerKeyIndexMap[ keyInt->val_ ] = i;
3771                         } else {
3772                                 throw Exceptions::TypeMismatch( callLoc, "NodeData field 'key' in graph construction", key->getTypeName( ), Exceptions::GraphKeyTypeMismatch::expectedType );
3773                         }
3774
3775                         RefCountPtr< const Lang::Value > partition = n->partition_;
3776                         if( partitioned ){
3777                                 if( partition == Lang::THE_VOID ){
3778                                         throw Exceptions::MiscellaneousRequirement( callLoc, "NodeData field 'partition' cannot be void in a graph with partitions." );
3779                                 }
3780                                 if( const Lang::Symbol * keySym = dynamic_cast< const Lang::Symbol * >( partition.getPtr( ) ) ){
3781                                         if( symKeys.find( keySym->getKey( ) ) == symKeys.end( ) ){
3782                                                 throw Exceptions::InvalidGraphPartition( partition, partitions, callLoc );
3783                                         }
3784                                 } else if( const Lang::Integer * keyInt = dynamic_cast< const Lang::Integer * >( partition.getPtr( ) ) ){
3785                                         if( intKeys.find( keyInt->val_ ) == intKeys.end( ) ){
3786                                                 throw Exceptions::InvalidGraphPartition( partition, partitions, callLoc );
3787                                         }
3788                                 } else {
3789                                         throw Exceptions::TypeMismatch( callLoc, "NodeData field 'partition' in graph construction", partition->getTypeName( ), Exceptions::GraphKeyTypeMismatch::expectedType );
3790                                 }
3791                         }else{
3792                                 if( partition != Lang::THE_VOID ){
3793                                         throw Exceptions::MiscellaneousRequirement( callLoc, "NodeData field 'partition' must be void in a graph without partitions." );
3794                                 }
3795                         }
3796                 }
3797         }
3798
3799         {
3800                 std::set< std::pair< size_t, size_t > > directedSet; /* For detection of parallel edges. */
3801                 std::set< std::pair< size_t, size_t > > undirectedSet; /* For detection of parallel edges. */
3802
3803                 typedef typeof edgeData ListType;
3804                 for( ListType::const_iterator e = edgeData.begin( ); e != edgeData.end( ); ++e ){
3805                         RefCountPtr< const Lang::Value > sourceKey = e->sourceKey_;
3806                         RefCountPtr< const Lang::Value > targetKey = e->targetKey_;
3807                         const Lang::Symbol * keySym;
3808                         const Lang::Integer * keyInt;
3809
3810                         size_t source;
3811                         if( ( keySym = dynamic_cast< const Lang::Symbol * >( sourceKey.getPtr( ) ) ) != 0 ){
3812                                 source = symbolKeyIndexMap[ keySym->getKey( ) ];
3813                         } else if( ( keyInt = dynamic_cast< const Lang::Integer * >( sourceKey.getPtr( ) ) ) != 0 ){
3814                                 source = integerKeyIndexMap[ keyInt->val_ ];
3815                         } else {
3816                                 throw Exceptions::TypeMismatch( callLoc, "EdgeData field 'source' in graph construction", sourceKey->getTypeName( ), Exceptions::GraphKeyTypeMismatch::expectedType );
3817                         }
3818
3819                         size_t target;
3820                         if( ( keySym = dynamic_cast< const Lang::Symbol * >( targetKey.getPtr( ) ) ) != 0 ){
3821                                 target = symbolKeyIndexMap[ keySym->getKey( ) ];
3822                         }else if( ( keyInt = dynamic_cast< const Lang::Integer * >( targetKey.getPtr( ) ) ) != 0 ){
3823                                 target = integerKeyIndexMap[ keyInt->val_ ];
3824                         }else{
3825                                 throw Exceptions::TypeMismatch( callLoc, "EdgeData field 'target' in graph construction", targetKey->getTypeName( ), Exceptions::GraphKeyTypeMismatch::expectedType );
3826                         }
3827
3828                         {
3829                                 Kernel::ValueRef label = e->label_;
3830                                 if( dynamic_cast< const Lang::Void * >( label.getPtr( ) ) != 0 ){
3831                                         /* Edge has no label */
3832                                 } else if( dynamic_cast< const Lang::Symbol * >( label.getPtr( ) ) != 0 ){
3833                                         hasEdgeLabels = true;
3834                                 } else if( dynamic_cast< const Lang::Integer * >( label.getPtr( ) ) != 0 ){
3835                                         hasEdgeLabels = true;
3836                                 } else {
3837                                         throw Exceptions::TypeMismatch( callLoc, "EdgeData field 'label' in graph construction", label->getTypeName( ), Exceptions::GraphKeyTypeMismatch::expectedType );
3838                                 }
3839                         }
3840
3841                         if( e->directed_ ){
3842                                 if( ! domain.directed( ) )
3843                                         throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::DIRECTED, e->directed_, sourceKey, targetKey, callLoc );
3844                                 if( ! domain.parallel( ) ){
3845                                         std::pair< size_t, size_t > newEdge = std::pair< size_t, size_t >( source, target );
3846                                         if( directedSet.find( newEdge ) != directedSet.end( ) )
3847                                                 throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::PARALLEL, e->directed_, sourceKey, targetKey, callLoc );
3848                                         directedSet.insert( directedSet.begin( ), newEdge );
3849                                 }
3850                                 if( source == target ){
3851                                         if( ! domain.loops( ) )
3852                                                 throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::LOOPS, e->directed_, sourceKey, targetKey, callLoc );
3853                                         dloopDataIndexed.push_back( Kernel::LoopDataIndexed( source, e->value_, e->label_ ) );
3854                                 }else{
3855                                         dedgeDataIndexed.push_back( Kernel::EdgeDataIndexed( source, target, e->value_, e->label_ ) );
3856                                 }
3857                         }else{
3858                                 if( source > target ){
3859                                         size_t tmpIndex = source;
3860                                         source = target;
3861                                         target = tmpIndex;
3862                                         RefCountPtr< const Lang::Value > tmpVal = sourceKey;
3863                                         sourceKey = targetKey;
3864                                         targetKey = tmpVal;
3865                                 }
3866                                 if( ! domain.undirected( ) )
3867                                         throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::UNDIRECTED, e->directed_, sourceKey, targetKey, callLoc );
3868                                 if( ! domain.parallel( ) ){
3869                                         std::pair< size_t, size_t > newEdge = std::pair< size_t, size_t >( source, target );
3870                                         if( undirectedSet.find( newEdge ) != undirectedSet.end( ) )
3871                                                 throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::PARALLEL, e->directed_, sourceKey, targetKey, callLoc );
3872                                         undirectedSet.insert( undirectedSet.begin( ), newEdge );
3873                                 }
3874                                 if( source == target ){
3875                                         if( ! domain.loops( ) )
3876                                                 throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::LOOPS, e->directed_, sourceKey, targetKey, callLoc );
3877                                         uloopDataIndexed.push_back( Kernel::LoopDataIndexed( source, e->value_, e->label_ ) );
3878                                 }else{
3879                                         uedgeDataIndexed.push_back( Kernel::EdgeDataIndexed( source, target, e->value_, e->label_ ) );
3880                                 }
3881                         }
3882                 }
3883         }
3884
3885         RefCountPtr< const Lang::Graph::ValueVector > nodeValues = RefCountPtr< const Lang::Graph::ValueVector >( NullPtr< const Lang::Graph::ValueVector >( ) );
3886         RefCountPtr< const Lang::Graph::ValueVector > edgeValues = RefCountPtr< const Lang::Graph::ValueVector >( NullPtr< const Lang::Graph::ValueVector >( ) );
3887         RefCountPtr< const Kernel::Graph > kernelGraph( new Kernel::Graph( domain, partitions, nodeData, hasEdgeLabels, uedgeDataIndexed, dedgeDataIndexed, uloopDataIndexed, dloopDataIndexed, & nodeValues, & edgeValues, callLoc ) );
3888
3889         return RefCountPtr< const Lang::Graph >( new Lang::Graph( kernelGraph, nodeValues, edgeValues ) );
3890 }
3891
3892 namespace Shapes
3893 {
3894         namespace Kernel
3895         {
3896
3897                 class Mutator_Graph_addNode : public Lang::CoreMutator
3898                 {
3899                 public:
3900                         Mutator_Graph_addNode( const char * name )
3901                                 : CoreMutator( name, new Kernel::EvaluatedFormals( Ast::FileID::build_internal( name ), true ) )
3902                         {
3903                                 formals_->appendEvaluatedCoreFormal( "key", Kernel::THE_SLOT_VARIABLE );
3904                                 formals_->appendEvaluatedCoreFormal( "value", Kernel::THE_VOID_VARIABLE );
3905                                 formals_->appendEvaluatedCoreFormal( "partition", Kernel::THE_VOID_VARIABLE );
3906                         }
3907                         virtual void
3908                         call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3909                         {
3910                                 args.applyDefaults( callLoc );
3911
3912                                 typedef WarmGraph StateType;
3913                                 StateType * state = Helpers::mutator_cast_self< StateType >( args.getMutatorSelf( ) );
3914
3915                                 size_t argsi = 0;
3916                                 RefCountPtr< const Lang::Value > key = args.getValue( argsi );
3917                                 do{
3918                                         if( dynamic_cast< const Lang::Symbol * >( key.getPtr( ) ) != 0 )
3919                                                 break;
3920                                         if( dynamic_cast< const Lang::Integer * >( key.getPtr( ) ) != 0 )
3921                                                 break;
3922                                         throw Exceptions::CoreTypeMismatch( callLoc, new Interaction::MutatorLocation( state, name_ ), args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
3923                                 }while( false );
3924
3925                                 ++argsi;
3926                                 RefCountPtr< const Lang::Value > value = args.getValue( argsi );
3927
3928                                 ++argsi;
3929                                 RefCountPtr< const Lang::Value > partition = args.getValue( argsi );
3930                                 do{
3931                                         if( partition == Lang::THE_VOID )
3932                                                 break;
3933                                         if( dynamic_cast< const Lang::Symbol * >( key.getPtr( ) ) != 0 )
3934                                                 break;
3935                                         if( dynamic_cast< const Lang::Integer * >( key.getPtr( ) ) != 0 )
3936                                                 break;
3937                                         throw Exceptions::CoreTypeMismatch( callLoc, new Interaction::MutatorLocation( state, name_ ), args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
3938                                 }while( false );
3939
3940                                 if( state->partitionKeys( ) != NullPtr< const Lang::SingleList >( ) ){
3941                                         if( partition == Lang::THE_VOID )
3942                                                 throw Exceptions::MiscellaneousRequirement( callLoc, "NodeData field 'partition' cannot be void in a graph with partitions." );
3943                                         /* Although we could check that partition is a valid key here, we let Helpers::graphFromNodeEdgeData
3944                                          * take care of that.  If it turns out to be a big problem that the errors are not reportat at the place of insertion,
3945                                          * this can be changed.
3946                                          */
3947                                 }else{
3948                                         if( partition != Lang::THE_VOID )
3949                                                 throw Exceptions::MiscellaneousRequirement( callLoc, "NodeData field 'partition' must be void in a graph without partitions." );
3950                                 }
3951
3952                                 state->addNode( Kernel::NodeData( key, value, partition ) );
3953
3954                                 Kernel::ContRef cont = evalState->cont_;
3955                                 cont->takeValue( Lang::THE_VOID,
3956                                                                                                  evalState );
3957                         }
3958                 };
3959
3960                 class Mutator_Graph_addEdge : public Lang::CoreMutator
3961                 {
3962                 public:
3963                         Mutator_Graph_addEdge( const char * name )
3964                                 : CoreMutator( name, new Kernel::EvaluatedFormals( Ast::FileID::build_internal( name ), true ) )
3965                         {
3966                                 formals_->appendEvaluatedCoreFormal( "source", Kernel::THE_SLOT_VARIABLE );
3967                                 formals_->appendEvaluatedCoreFormal( "target", Kernel::THE_SLOT_VARIABLE );
3968                                 formals_->appendEvaluatedCoreFormal( "value", Kernel::THE_VOID_VARIABLE );
3969                                 formals_->appendEvaluatedCoreFormal( "label", Kernel::THE_VOID_VARIABLE );
3970                                 formals_->appendEvaluatedCoreFormal( "directed", Kernel::THE_VOID_VARIABLE );
3971                         }
3972                         virtual void
3973                         call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
3974                         {
3975                                 args.applyDefaults( callLoc );
3976
3977                                 typedef WarmGraph StateType;
3978                                 StateType * state = Helpers::mutator_cast_self< StateType >( args.getMutatorSelf( ) );
3979
3980                                 size_t argsi = 0;
3981                                 RefCountPtr< const Lang::Value > sourceKey = args.getValue( argsi );
3982                                 do{
3983                                         if( dynamic_cast< const Lang::Symbol * >( sourceKey.getPtr( ) ) != 0 )
3984                                                 break;
3985                                         if( dynamic_cast< const Lang::Integer * >( sourceKey.getPtr( ) ) != 0 )
3986                                                 break;
3987                                         throw Exceptions::CoreTypeMismatch( callLoc, new Interaction::MutatorLocation( state, name_ ), args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
3988                                 }while( false );
3989
3990                                 ++argsi;
3991                                 RefCountPtr< const Lang::Value > targetKey = args.getValue( argsi );
3992                                 do{
3993                                         if( dynamic_cast< const Lang::Symbol * >( targetKey.getPtr( ) ) != 0 )
3994                                                 break;
3995                                         if( dynamic_cast< const Lang::Integer * >( targetKey.getPtr( ) ) != 0 )
3996                                                 break;
3997                                         throw Exceptions::CoreTypeMismatch( callLoc, new Interaction::MutatorLocation( state, name_ ), args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
3998                                 }while( false );
3999
4000                                 ++argsi;
4001                                 RefCountPtr< const Lang::Value > value = args.getValue( argsi );
4002
4003                                 ++argsi;
4004                                 RefCountPtr< const Lang::Value > label = args.getValue( argsi );
4005                                 if( ! ( label == Lang::THE_VOID
4006                                                                 || dynamic_cast< const Lang::Symbol * >( label.getPtr( ) ) != 0
4007                                                                 || dynamic_cast< const Lang::Integer * >( label.getPtr( ) ) != 0 ) ){
4008                                         throw Exceptions::CoreTypeMismatch( callLoc, new Interaction::MutatorLocation( state, name_ ), args, argsi, Exceptions::GraphKeyTypeMismatch::expectedType );
4009                                 }
4010
4011                                 ++argsi;
4012                                 typedef const Lang::Boolean DirectedType;
4013                                 RefCountPtr< DirectedType > directedVal = Helpers::down_cast_MutatorArgument< DirectedType >( state, name_, args, argsi, callLoc, true );
4014                                 bool directed;
4015                                 if( directedVal != NullPtr< DirectedType >( ) ){
4016                                         directed = directedVal->val_;
4017                                         if( directed ){
4018                                                 if( not state->domain( ).directed( ) )
4019                                                         throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::DIRECTED, directed, sourceKey, targetKey, callLoc );
4020                                         }else{
4021                                                 if( not state->domain( ).undirected( ) )
4022                                                         throw Exceptions::GraphDomainError( Exceptions::GraphDomainError::UNDIRECTED, directed, sourceKey, targetKey, callLoc );
4023                                         }
4024                                 }else{
4025                                         if( state->domain( ).directed( ) && not state->domain( ).undirected( ) )
4026                                                 directed = true;
4027                                         else if( not state->domain( ).directed( ) && state->domain( ).undirected( ) )
4028                                                 directed = false;
4029                                         else
4030                                                 throw Exceptions::MiscellaneousRequirement( callLoc, "The argument 'directed' must be specified since the graph domain does not determine a default interpretation." );
4031                                 }
4032
4033                                 state->addEdge( Kernel::EdgeData( directed, sourceKey, targetKey, value, label ) );
4034
4035                                 Kernel::ContRef cont = evalState->cont_;
4036                                 cont->takeValue( Lang::THE_VOID,
4037                                                                                                  evalState );
4038                         }
4039                 };
4040
4041         }
4042 }
4043
4044 Kernel::WarmGraph::WarmGraph( const Kernel::GraphDomain & domain, const RefCountPtr< const Lang::SingleList > & partitionKeys, RefCountPtr< std::list< Kernel::NodeData > > & nodeDataMem, RefCountPtr< std::list< Kernel::EdgeData > > & edgeDataMem )
4045         : domain_( domain ), partitionKeys_( partitionKeys ), nodeDataMem_( nodeDataMem ), edgeDataMem_( edgeDataMem ), nodeData_( *nodeDataMem_ ), edgeData_( *edgeDataMem_ )
4046 { }
4047
4048 Kernel::WarmGraph::~WarmGraph( )
4049 { }
4050
4051 void
4052 WarmGraph_register_mutators( Lang::SystemFinalClass * dstClass )
4053 {
4054         dstClass->registerMutator( new Kernel::Mutator_Graph_addNode( "node" ) );
4055         dstClass->registerMutator( new Kernel::Mutator_Graph_addEdge( "edge" ) );
4056 }
4057
4058 RefCountPtr< const Lang::Class > Kernel::WarmGraph::TypeID( new Lang::SystemFinalClass( strrefdup( "#Graph" ), WarmGraph_register_mutators ) );
4059 TYPEINFOIMPL_STATE( WarmGraph );
4060
4061 void
4062 Kernel::WarmGraph::tackOnImpl( Kernel::EvalState * evalState, const RefCountPtr< const Lang::Value > & piece, const Ast::SourceLocation & callLoc )
4063 {
4064         throw Exceptions::MiscellaneousRequirement( strrefdup( "A #Graph state has no tack on operation, consider using one of the named mutators instead." ) );
4065 }
4066
4067 void
4068 Kernel::WarmGraph::freezeImpl( Kernel::EvalState * evalState, const Ast::SourceLocation & callLoc )
4069 {
4070         Kernel::ContRef cont = evalState->cont_;
4071         /* Passing callLoc for the source location of the partition keys.  It's not right, but it doesn't matter since the
4072    * partition keys have already been checked.
4073    */
4074         cont->takeValue( Helpers::graphFromNodeEdgeData( domain_, partitionKeys_, nodeData_, edgeData_, callLoc, callLoc ),
4075                                                                          evalState );
4076 }
4077
4078 void
4079 Kernel::WarmGraph::peekImpl( Kernel::EvalState * evalState, const Ast::SourceLocation & callLoc )
4080 {
4081         Kernel::ContRef cont = evalState->cont_;
4082         /* Passing callLoc for the source location of the partition keys.  It's not right, but it doesn't matter since the
4083    * partition keys have already been checked.
4084    */
4085         cont->takeValue( Helpers::graphFromNodeEdgeData( domain_, partitionKeys_, nodeData_, edgeData_, callLoc, callLoc ),
4086                                                                          evalState );
4087 }
4088
4089 void
4090 Kernel::WarmGraph::gcMark( Kernel::GCMarkedSet & marked )
4091 { }
4092
4093 void
4094 Kernel::WarmGraph::addNode( const Kernel::NodeData & node )
4095 {
4096         nodeData_.push_back( node );
4097 }
4098
4099 void
4100 Kernel::WarmGraph::addEdge( const Kernel::EdgeData & edge )
4101 {
4102         edgeData_.push_back( edge );
4103 }