source/graphtypes.h

   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 #pragma once
  20
  21 #include <list>
  22 #include <set>
  23 #include <vector>
  24
  25 #include "ptrowner.h"
  26 #include "refcount.h"
  27 #include "shapesvalue.h"
  28 #include "environment.h"
  29 #include "charptrless.h"
  30 #include "elementarytypes.h"
  31 #include "containertypes.h"
  32
  33 namespace Shapes
  34 {
  35         namespace Kernel
  36         {
  37
  38                 class Edge
  39                 {
  40                         /* Rather than storing whether an edge is directed or not as a flag here, directed and undirected edges are always kept apart.
  41                          * Lang::Edge, on the other hand, will contain this information explicitly.
  42                          */
  43                         Kernel::Node * source_;
  44                         Kernel::Node * target_;
  45                         size_t index_;
  46                 public:
  47                         Edge( Kernel::Node * source, Kernel::Node * target, size_t index, bool directed );
  48
  49                         size_t index( ) const { return index_; }
  50
  51                         const Kernel::Node * source( ) const { return source_; }
  52                         const Kernel::Node * target( ) const { return target_; }
  53                         Kernel::Node * source( ) { return source_; }
  54                         Kernel::Node * target( ) { return target_; }
  55                 };
  56
  57                 class EdgePtrLessSource
  58                 {
  59                 public:
  60                         bool operator () ( const Edge * x, const Edge * y ) const;
  61                 };
  62
  63                 class EdgePtrLessTarget
  64                 {
  65                 public:
  66                         bool operator () ( const Edge * x, const Edge * y ) const;
  67                 };
  68
  69                 class EdgePredicate
  70                 {
  71                 protected:
  72                         bool always_false_;
  73                         bool always_true_;
  74                 public:
  75                         EdgePredicate( );
  76                         virtual ~EdgePredicate( );
  77                         virtual bool operator () ( const Edge & e ) const = 0;
  78                         bool always_false( ) const { return always_false_; }
  79                         bool always_true( ) const { return always_true_; }
  80                 };
  81
  82                 template< class T >
  83                 class EdgeLabelPredicate : public EdgePredicate
  84                 {
  85                         RefCountPtr< std::vector< Kernel::ValueRef > > edgeLabels_;
  86                         T label_;
  87                 public:
  88                         EdgeLabelPredicate( const RefCountPtr< std::vector< Kernel::ValueRef > > & edgeLabels, const T & label );
  89                         virtual ~EdgeLabelPredicate( );
  90                         virtual bool operator () ( const Edge & e ) const;
  91                 };
  92
  93                 class Node
  94                 {
  95                 public:
  96                         typedef RefCountPtr< const Lang::SingleList > ListRef;
  97                         /* The containers types EdgeSetSource and EdgeSetTarget can be either std::set
  98                          * or std::multiset, depending on whether the comparison will treat parallel edges
  99                          * equal or not (parallel edges can always be distinguished using the edge index).
 100                          * Treating parallel edges as different (using std::set) allows the edges to be
 101                          * stored in a canonical order.  Treating them as equal (using std::multiset) makes
 102                          * it easy to access the parallel edges as an equal range.  However, with std::set
 103                          * it is still easy to access the range of parallel edges, since it is easy to construct
 104                          * the elements to use with lower_bound and upper_bound that will do the job.
 105                          */
 106                         typedef std::set< const Kernel::Edge *, EdgePtrLessSource > EdgeSetSource;
 107                         typedef std::set< const Kernel::Edge *, EdgePtrLessTarget > EdgeSetTarget;
 108
 109                 private:
 110                         EdgeSetSource uedgesLow_; /* Adjacent node has lower index. */
 111                         EdgeSetTarget uedgesHigh_; /* Adjacent node has higher index. */
 112                         EdgeSetSource uloops_;
 113                         EdgeSetSource dedgesIn_;
 114                         EdgeSetTarget dedgesOut_;
 115                         EdgeSetSource dloops_;
 116                         size_t index_;
 117                         RefCountPtr< const Lang::Value > key_;
 118                 public:
 119                         Node( size_t index, const RefCountPtr< const Lang::Value > & key )
 120                                 : index_( index ), key_( key )
 121                         { }
 122
 123                         size_t index( ) const { return index_; }
 124                         const RefCountPtr< const Lang::Value > & key( ) const { return key_; }
 125
 126                         void show( std::ostream & os ) const;
 127
 128                         void add_uedgeLow( Kernel::Edge * edge ) { uedgesLow_.insert( edge ); }
 129                         void add_uedgeHigh( Kernel::Edge * edge ) { uedgesHigh_.insert( edge ); }
 130                         void add_uloop( Kernel::Edge * edge ) { uloops_.insert( edge ); }
 131                         void add_dedgeIn( Kernel::Edge * edge ) { dedgesIn_.insert( edge ); }
 132                         void add_dedgeOut( Kernel::Edge * edge ) { dedgesOut_.insert( edge ); }
 133                         void add_dloop( Kernel::Edge * edge ) { dloops_.insert( edge ); }
 134
 135                         size_t u_degree( ) const { return uedgesLow_.size( ) + uedgesHigh_.size( ) + uloops_.size( ); }
 136                         size_t d_degree_in( ) const { return dedgesIn_.size( ) + dloops_.size( ); }
 137                         size_t d_degree_out( ) const { return dedgesOut_.size( ) + dloops_.size( ); }
 138                         size_t d_degree( ) const { return dedgesIn_.size( ) + dedgesOut_.size( ) + 2 * dloops_.size( ); }
 139                         size_t degree( ) const { return uedgesLow_.size( ) + uedgesHigh_.size( ) + uloops_.size( ) + dedgesIn_.size( ) + dedgesOut_.size( ) + 2 * dloops_.size( ); }
 140                         size_t u_loop_count( ) const { return uloops_.size( ); }
 141                         size_t d_loop_count( ) const { return dloops_.size( ); }
 142                         size_t loop_count( ) const { return uloops_.size( ) + dloops_.size( ); }
 143
 144                         ListRef prepend_uedges( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 145                         ListRef prepend_dedgesIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 146                         ListRef prepend_dedgesOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 147                         ListRef prepend_uloops( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 148                         ListRef prepend_dloops( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 149
 150                         ListRef prepend_uedges_to( Kernel::Node * neighbor, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 151                         ListRef prepend_dedges_from( Kernel::Node * source, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 152                         ListRef prepend_dedges_to( Kernel::Node * target, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter = 0 ) const;
 153
 154                         ListRef prepend_uedgeNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 155                         ListRef prepend_dedgeNeighborsIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 156                         ListRef prepend_dedgeNeighborsOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 157                         ListRef prepend_uloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 158                         ListRef prepend_dloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 159
 160                         ListRef prepend_unique_uedgeNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const;
 161                         ListRef prepend_unique_dedgeNeighborsIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const;
 162                         ListRef prepend_unique_dedgeNeighborsOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const;
 163                         ListRef prepend_unique_uloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const;
 164                         ListRef prepend_unique_dloopNeighbors( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, std::set< size_t > * added ) const;
 165
 166                         /* Note on efficiency:  With the current representation of multiedges, there is a certain lack of symmetry
 167                          * in the methods below.  Both prepend_d_multiedgesOut and prepend_u_multiedgesHigh have much worse time
 168                          * complexicy than the other methods, as they need to find the edges as stored in adjacent nodes.
 169                          */
 170                         ListRef prepend_u_multiedges( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 171                         ListRef prepend_d_multiedgesIn( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 172                         ListRef prepend_d_multiedgeInFrom( const Kernel::Node * source, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 173                         ListRef prepend_d_multiedgesOut( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 174                         ListRef prepend_u_multiloops( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 175                         ListRef prepend_d_multiloops( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 176                         ListRef prepend_u_multiedgesLow( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 177                         ListRef prepend_u_multiedgeLowFrom( const Kernel::Node * source, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 178                         ListRef prepend_u_multiedgesHigh( const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph ) const;
 179
 180                 private:
 181                         template< class T >
 182                         static ListRef prepend_edges( const T & edges, bool directed, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter );
 183                         template< class T >
 184                         static ListRef prepend_edges_neighbor( Kernel::Node * neighbor, const T & edges, bool directed, const ListRef & rest, const RefCountPtr< const Lang::Graph > & graph, const Kernel::EdgePredicate * filter );
 185                 };
 186
 187                 inline
 188                 bool
 189                 EdgePtrLessSource::operator () ( const Edge * x, const Edge * y ) const
 190                 {
 191                         if( x->source( )->index( ) < y->source( )->index( ) )
 192                                 return true;
 193                         if( x->source( )->index( ) > y->source( )->index( ) )
 194                                 return false;
 195                         return x->index( ) < y->index( );
 196                 }
 197
 198                 inline
 199                 bool
 200                 EdgePtrLessTarget::operator () ( const Edge * x, const Edge * y ) const
 201                 {
 202                         if( x->target( )->index( ) < y->target( )->index( ) )
 203                                 return true;
 204                         if( x->target( )->index( ) > y->target( )->index( ) )
 205                                 return false;
 206                         return x->index( ) < y->index( );
 207                 }
 208
 209                 class GraphDomain
 210                 {
 211                         bool undirected_;
 212                         bool directed_;
 213                         bool loops_;
 214                         bool parallel_;
 215                 public:
 216                         GraphDomain( )
 217                                 : undirected_( false ), directed_( false ), loops_( false ), parallel_( false )
 218                         { }
 219
 220                         void allowUndirected( ) { undirected_ = true; }
 221                         void allowDirected( ) { directed_ = true; }
 222                         void allowLoops( ) { loops_ = true; }
 223                         void allowParallel( ) { parallel_ = true; }
 224
 225                         bool undirected( ) const { return undirected_; }
 226                         bool directed( ) const { return directed_; }
 227                         bool loops( ) const { return loops_; }
 228                         bool parallel( ) const { return parallel_; }
 229                 };
 230
 231                 class NodeData
 232                 {
 233                 public:
 234                         Kernel::ValueRef key_;
 235                         Kernel::ValueRef value_;
 236                         Kernel::ValueRef partition_;
 237                         NodeData( const Kernel::ValueRef & key, const Kernel::ValueRef & value, const Kernel::ValueRef & partition )
 238                                 : key_( key ), value_( value ), partition_( partition )
 239                         { }
 240                 };
 241
 242                 class EdgeData
 243                 {
 244                 public:
 245                         bool directed_;
 246                         Kernel::ValueRef sourceKey_;
 247                         Kernel::ValueRef targetKey_;
 248                         Kernel::ValueRef value_;
 249                         Kernel::ValueRef label_;
 250                         EdgeData( bool directed, const Kernel::ValueRef & sourceKey, const Kernel::ValueRef & targetKey, const Kernel::ValueRef & value, const Kernel::ValueRef & label )
 251                                 : directed_( directed ), sourceKey_( sourceKey ), targetKey_( targetKey ), value_( value ), label_( label )
 252                         { }
 253                 };
 254
 255                 class EdgeDataIndexed
 256                 {
 257                 public:
 258                         /* The directed property is not stored, since directed and undirected edges should not be mixed in the same container. */
 259                         size_t source_;
 260                         size_t target_;
 261                         Kernel::ValueRef value_;
 262                         Kernel::ValueRef label_;
 263                         EdgeDataIndexed( size_t source, size_t target, const Kernel::ValueRef & value, const Kernel::ValueRef & label )
 264                                 : source_( source ), target_( target ), value_( value ), label_( label )
 265                         { }
 266                 };
 267
 268                 class LoopDataIndexed
 269                 {
 270                 public:
 271                         /* The directed property is not stored, since directed and undirected edges should not be mixed in the same container. */
 272                         size_t node_;
 273                         Kernel::ValueRef value_;
 274                         Kernel::ValueRef label_;
 275                         LoopDataIndexed( size_t node, const Kernel::ValueRef & value, const Kernel::ValueRef & label )
 276                                 : node_( node ), value_( value ), label_( label )
 277                         { }
 278                 };
 279
 280                 /* The Kernel::Graph only stores the graph structure.
 281                  * In particular, node and edge values are only stored in the Lang::Graph.
 282                  */
 283                 class Graph
 284                 {
 285                 public:
 286                         typedef std::vector< Kernel::Node * > NodeVector;
 287                         typedef std::vector< Kernel::Edge * > EdgeVector;
 288                         typedef RefCountPtr< const Lang::SingleList > ListRef;
 289                         typedef std::vector< Kernel::ValueRef > ValueVector;
 290                         enum SubgraphKind{ INDUCED, SPANNING };
 291                         enum ItemType{ NODE, EDGE };
 292
 293                 private:
 294                         typedef std::map< Lang::Symbol::KeyType, const Kernel::Node * > SymbolKeyMap;
 295                         typedef std::map< Lang::Integer::ValueType, const Kernel::Node * > IntegerKeyMap;
 296                         typedef std::map< Lang::Symbol::KeyType, NodeVector * > SymbolKeyPartitionMap;
 297                         typedef std::map< Lang::Integer::ValueType, NodeVector * > IntegerKeyPartitionMap;
 298
 299                         Kernel::GraphDomain domain_;
 300                         ListRef partitionKeys_; /* Partition keys in original order.  Null if graph is not partitioned. */
 301                         NodeVector nodes_;
 302                         EdgeVector uedges_;
 303                         EdgeVector uloops_;
 304                         EdgeVector dedges_;
 305                         EdgeVector dloops_;
 306                         bool keyIsRange_;
 307                         Lang::Integer::ValueType keyOffset_;
 308
 309                         SymbolKeyMap symbolKeyMap_;
 310                         IntegerKeyMap integerKeyMap_;
 311
 312                         RefCountPtr< ValueVector > edgeLabels_; /* Null if all edge labels are void. */
 313
 314                         RefCountPtr< ValueVector > nodePartitions_; /* The partition of each node.  Null if graph is not partitioned. */
 315                         PtrOwner_back_Access< std::list< NodeVector * > > partitions_; /* Partition storage.  Empty if graph is not partitioned. */
 316                         SymbolKeyPartitionMap symbolKeyPartitionMap_;
 317                         IntegerKeyPartitionMap integerKeyPartitionMap_;
 318
 319                 public:
 320                         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 ); /* Generally invoked by Helpers::graphFromNodeEdgeData. */
 321                         Graph( const Kernel::Graph & orig, const std::set< size_t > & subgraphIndices, SubgraphKind kind, const RefCountPtr< const ValueVector > & origNodeValues, const RefCountPtr< const ValueVector > & origEdgeValues, RefCountPtr< const ValueVector > * nodeValues, RefCountPtr< const ValueVector > * edgeValues );
 322                         Graph( const Kernel::Graph & orig, Lang::Integer::ValueType offset ); /* Rekey with index. */
 323                         virtual ~Graph( );
 324
 325                         const NodeVector & nodes( ) const { return nodes_; }
 326                         const EdgeVector & uedges( ) const { return uedges_; }
 327                         const EdgeVector & dedges( ) const { return dedges_; }
 328                         const EdgeVector & uloops( ) const { return uloops_; }
 329                         const EdgeVector & dloops( ) const { return dloops_; }
 330
 331                         void show( std::ostream & os ) const;
 332
 333                         const Kernel::GraphDomain & domain( ) const { return domain_; }
 334                         size_t nodeCount( ) const { return nodes_.size( ); }
 335                         size_t edgeCount( ) const;
 336                         bool keyIsRange( ) const { return keyIsRange_; }
 337                         Lang::Integer::ValueType keyOffset( ) const { return keyOffset_; }
 338                         bool partitioned( ) const { return partitionKeys_ != NullPtr< const Lang::SingleList >( ); }
 339                         size_t partitionCount( ) const { return partitions_.size( ); }
 340                         ListRef partitionKeys( ) const { return partitionKeys_; }
 341
 342                         bool isKey( const RefCountPtr< const Lang::Value > & key ) const;
 343                         RefCountPtr< const Lang::Node > indexNode( const RefCountPtr< const Lang::Graph > & owner, size_t index ) const;
 344                         RefCountPtr< const Lang::Edge > indexEdge( const RefCountPtr< const Lang::Graph > & owner, size_t index ) const;
 345                         RefCountPtr< const Lang::Node > findNode( const RefCountPtr< const Lang::Graph > & owner, const RefCountPtr< const Lang::Value > & key ) const;
 346                         size_t findIndex( const RefCountPtr< const Lang::Value > & key ) const;
 347                         ListRef findEdges( const RefCountPtr< const Lang::Graph > & owner, Kernel::Node * source, Kernel::Node * target, bool directed, bool undirected, bool loops, const Kernel::ValueRef & label ) const;
 348                         ListRef findMultiEdges( const RefCountPtr< const Lang::Graph > & owner, const Kernel::Node * source, const Kernel::Node * target, bool directed, bool undirected, bool loops ) const;
 349                         const NodeVector * getPartition( const Kernel::ValueRef & key ) const;
 350
 351                         Kernel::VariableHandle edgeLabel( const Kernel::Edge * edge ) const;
 352                         Kernel::VariableHandle nodePartition( const Kernel::Node * node ) const;
 353
 354                         Kernel::State * newState( const RefCountPtr< const ValueVector > & nodeValues, const RefCountPtr< const ValueVector > & edgeValues ) const;
 355
 356                 private:
 357                         void initializeKeyRangeOffset( );
 358                         void initializeKeyMaps( );
 359                         void initializeAndCheckPartitions( const Ast::SourceLocation & callLoc );
 360                         void addEdgesToNodes( );
 361                         void 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 );
 362                         void 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 );
 363                 };
 364
 365         }
 366
 367         namespace Lang
 368         {
 369
 370                 class Node : public Lang::NoOperatorOverloadValue
 371                 {
 372                         RefCountPtr< const Lang::Graph > graph_;
 373                         const Kernel::Node * node_;
 374                 public:
 375                         Node( const RefCountPtr< const Lang::Graph > & graph, const Kernel::Node * node );
 376                         virtual ~Node( );
 377
 378                         RefCountPtr< const Lang::Graph > graph( ) const { return graph_; }
 379                         const Kernel::Node * node( ) const { return node_; }
 380
 381                         virtual void show( std::ostream & os ) const;
 382                         virtual Kernel::VariableHandle getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const;
 383                         virtual void gcMark( Kernel::GCMarkedSet & marked );
 384                         TYPEINFODECL;
 385                 };
 386
 387                 class Edge : public Lang::NoOperatorOverloadValue
 388                 {
 389                         RefCountPtr< const Lang::Graph > graph_;
 390                         const Kernel::Edge * edge_;
 391                         bool directed_; /* The Kernel::Edge does not store whether the edge is directed or not. */
 392                 public:
 393                         Edge( const RefCountPtr< const Lang::Graph > & graph, const Kernel::Edge * edge, bool directed );
 394                         virtual ~Edge( );
 395
 396                         RefCountPtr< const Lang::Graph > graph( ) const { return graph_; }
 397                         const Kernel::Edge * edge( ) const { return edge_; }
 398                         bool directed( ) const { return directed_; }
 399
 400                         const Kernel::Node * trace( const Kernel::Node * source, bool nullOnError = false ) const;
 401                         const Kernel::Node * trace( const Kernel::Node * source, const Ast::SourceLocation & callLoc ) const;
 402                         const Kernel::Node * backtrace( const Kernel::Node * target, bool nullOnError = false ) const;
 403                         const Kernel::Node * backtrace( const Kernel::Node * target, const Ast::SourceLocation & callLoc ) const;
 404
 405                         virtual void show( std::ostream & os ) const;
 406                         virtual Kernel::VariableHandle getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const;
 407                         virtual void gcMark( Kernel::GCMarkedSet & marked );
 408                         TYPEINFODECL;
 409                 };
 410
 411                 class MultiEdge : public Lang::NoOperatorOverloadValue
 412                 {
 413                 public:
 414                         typedef Kernel::Node::EdgeSetSource SetType;
 415                 private:
 416                         RefCountPtr< const Lang::Graph > graph_;
 417                         bool directed_;
 418                         const Kernel::Node * source_;
 419                         const Kernel::Node * target_;
 420                         size_t count_;
 421                         /* The parallel edges are stored as a sub-range of a node's edge set.
 422                          * While a Kernel::Node uses two different types of sets to store its incident
 423                          * edges, every edge is stored somewhere in a set of type Kernel::Node::EdgeSetSource.
 424                          * This means that we will pay a time penalty for for constructing all multiedges
 425                          * incident to a node, as all multiedges which are not sorted by source in the
 426                          * current node will require a search in an adjacent node.
 427                          */
 428                         SetType::const_iterator begin_;
 429                         SetType::const_iterator end_;
 430                 public:
 431                         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 );
 432                         virtual ~MultiEdge( );
 433
 434                         RefCountPtr< const Lang::Graph > graph( ) const { return graph_; }
 435                         bool directed( ) const { return directed_; }
 436                         const Kernel::Node * source( ) const { return source_; }
 437                         const Kernel::Node * target( ) const { return target_; }
 438                         size_t count( ) const { return count_; }
 439                         SetType::const_iterator begin( ) const { return begin_; }
 440                         SetType::const_iterator end( ) const { return end_; }
 441
 442                         const Kernel::Node * trace( const Kernel::Node * source, bool nullOnError = false ) const;
 443                         const Kernel::Node * trace( const Kernel::Node * source, const Ast::SourceLocation & callLoc ) const;
 444                         const Kernel::Node * backtrace( const Kernel::Node * target, bool nullOnError = false ) const;
 445                         const Kernel::Node * backtrace( const Kernel::Node * target, const Ast::SourceLocation & callLoc ) const;
 446
 447                         RefCountPtr< const Lang::SingleList > edges( ) const;
 448
 449                         virtual void show( std::ostream & os ) const;
 450                         virtual Kernel::VariableHandle getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const;
 451                         virtual void gcMark( Kernel::GCMarkedSet & marked );
 452                         TYPEINFODECL;
 453                 };
 454
 455                 class Graph : public Lang::Hot
 456                 {
 457                 public:
 458                         typedef Kernel::Graph::ValueVector ValueVector;
 459                         typedef RefCountPtr< const Lang::SingleList > ListRef;
 460
 461                         RefCountPtr< const Kernel::Graph > graph_;
 462                         RefCountPtr< const ValueVector > nodeValues_; /* Null in case all values are void. */
 463                         RefCountPtr< const ValueVector > edgeValues_; /* Null in case all values are void. */
 464
 465                 public:
 466                         Graph( const RefCountPtr< const Kernel::Graph > & graph );
 467                         Graph( const RefCountPtr< const Kernel::Graph > & graph, const RefCountPtr< const ValueVector > & nodeValues, const RefCountPtr< const ValueVector > & edgeValues );
 468                         Graph( const Lang::Graph & orig, const std::set< size_t > & subgraphIndices, Kernel::Graph::SubgraphKind kind );
 469                         Graph( const Lang::Graph & orig, Lang::Integer::ValueType offset ); /* Rekey with index. */
 470                         virtual ~Graph( );
 471                         void setNodeValues( const RefCountPtr< const ValueVector > nodeValues );
 472                         void setNodeValues( const std::list< Kernel::NodeData > & nodeData );
 473                         void setEdgeValues( const RefCountPtr< const ValueVector > edgeValues ); /* Only invoke if at least one value is different from void. */
 474                         void 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 ); /* Only invoke if at least one value is different from void. */
 475
 476                         virtual void show( std::ostream & os ) const;
 477                         virtual Kernel::VariableHandle getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const;
 478                         virtual Kernel::State * newState( ) const;
 479                         virtual void gcMark( Kernel::GCMarkedSet & marked );
 480
 481                         RefCountPtr< const Kernel::Graph > graph( ) const { return graph_; }
 482                         RefCountPtr< const ValueVector > nodeValues( ) const { return nodeValues_; }
 483                         RefCountPtr< const ValueVector > edgeValues( ) const { return edgeValues_; }
 484
 485                         Kernel::VariableHandle nodeValue( const Kernel::Node * node ) const;
 486                         Kernel::VariableHandle nodePartition( const Kernel::Node * node ) const;
 487                         Kernel::VariableHandle edgeValue( const Kernel::Edge * edge ) const;
 488                         Kernel::VariableHandle edgeLabel( const Kernel::Edge * edge ) const;
 489                         /* The access to Kernel::Node pointers should only be used by Lang::Graph methods. */
 490                         Kernel::Node * kernelNodeByValue( Kernel::Arguments & args, size_t argsi, bool voidIsNull, const RefCountPtr< const Interaction::CoreLocation > & coreLoc, const Ast::SourceLocation & callLoc ) const;
 491
 492                         RefCountPtr< const Lang::SingleList > getPartition( const Kernel::ValueRef & key, const RefCountPtr< const Lang::Graph > & selfRef ) const;
 493                         size_t getPartitionSize( const Kernel::ValueRef & key ) const;
 494
 495                         static ListRef prepend_nodes( const Kernel::Graph::NodeVector & nodes, const ListRef & rest, const RefCountPtr< const Lang::Graph > & selfRef );
 496                         static ListRef prepend_edges( const Kernel::Graph::EdgeVector & edges, bool directed, const ListRef & rest, const RefCountPtr< const Lang::Graph > & selfRef, const Kernel::EdgePredicate * filter = 0 );
 497
 498                         TYPEINFODECL;
 499                 };
 500
 501                 class Walk : public Lang::NoOperatorOverloadValue
 502                 {
 503                         RefCountPtr< const Lang::Graph > graph_;
 504                         RefCountPtr< const Lang::Node > first_;
 505                         RefCountPtr< const Lang::Node > last_;
 506                         RefCountPtr< const Lang::SingleList > edges_;
 507                         bool closed_;
 508                         bool simple_;
 509                         bool trail_;
 510                         bool nodeCover_;
 511                         bool edgeCover_;
 512                         size_t edgeCount_;
 513                 public:
 514                         /* The constructor allows the <first> and <last> arguments to be null pointers, in which case the nodes will be determined
 515                          * based on the other arguments.
 516                          */
 517                         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 );
 518                         virtual Kernel::VariableHandle getField( const char * fieldID, const RefCountPtr< const Lang::Value > & selfRef ) const;
 519                         virtual ~Walk( );
 520                         TYPEINFODECL;
 521                         virtual void show( std::ostream & os ) const;
 522                         virtual void gcMark( Kernel::GCMarkedSet & marked );
 523                 };
 524
 525         }
 526
 527         namespace Helpers
 528         {
 529
 530                 /* Helper for Graph construction.
 531                  * Takes care of input data checking, so that all errors detected in Graph::Graph can be considered internal errors.
 532                  */
 533                 RefCountPtr< const Lang::Graph > 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 );
 534
 535         }
 536
 537         namespace Kernel
 538         {
 539
 540                 class WarmGraph : public Kernel::State
 541                 {
 542                         Kernel::GraphDomain domain_;
 543                         RefCountPtr< const Lang::SingleList > partitionKeys_; /* Partition keys in original order.  Null if graph is not partitioned. */
 544                         RefCountPtr< std::list< Kernel::NodeData > > nodeDataMem_;
 545                         RefCountPtr< std::list< Kernel::EdgeData > > edgeDataMem_;
 546                         std::list< Kernel::NodeData > & nodeData_;
 547                         std::list< Kernel::EdgeData > & edgeData_;
 548                 public:
 549                         WarmGraph( const Kernel::GraphDomain & domain, const RefCountPtr< const Lang::SingleList > & partitionKeys, RefCountPtr< std::list< Kernel::NodeData > > & nodeDataMem, RefCountPtr< std::list< Kernel::EdgeData > > & edgeDataMem );
 550                         virtual ~WarmGraph( );
 551                         virtual void tackOnImpl( Kernel::EvalState * evalState, const RefCountPtr< const Lang::Value > & piece, const Ast::SourceLocation & callLoc );
 552                         virtual void peekImpl( Kernel::EvalState * evalState, const Ast::SourceLocation & callLoc );
 553                         virtual void freezeImpl( Kernel::EvalState * evalState, const Ast::SourceLocation & callLoc );
 554                         virtual void gcMark( Kernel::GCMarkedSet & marked );
 555                         const Kernel::GraphDomain & domain( ) const { return domain_; }
 556                         RefCountPtr< const Lang::SingleList > partitionKeys( ) const { return partitionKeys_; }
 557                         void addNode( const Kernel::NodeData & node );
 558                         void addEdge( const Kernel::EdgeData & edge );
 559                         TYPEINFODECL;
 560                 };
 561
 562         }
 563 }