1 // Parallel abstract graph traverser. Contributed by Bjarne Knudsen. 2 3 #ifndef __traverser_h__ 4 #define __traverser_h__ 5 6 /* 7 This file defines a Traverser interface. A Traverser can be used for 8 going through an underlying structure of states. At each state, 9 there is a number of next states. Moving the traverser to a next 10 state changes its internal state. 11 12 When constructing a Traverser, it should be in the start state 13 (i.e. it should have no previous states). The traversal is over when 14 there are no more next states. 15 16 The state space should be a directed acyclic graph, so several 17 previous states to a given state are allowed. There may be any 18 number of end points, but only one start point. 19 20 When traversing in a multi threaded fashion, each Traverser receives 21 some of the collected information. It is up to the user of this 22 interface to join that information when the traversal is done. 23 */ 24 namespace gfan{ 25 26 class Traverser 27 { 28 public: 29 bool aborting; // Added by Anders abort()30 void abort(){aborting=true;} // Added by Anders Traverser()31 Traverser():aborting(false){} // Added by Anders 32 // Virtual destructor ~Traverser(void)33 virtual ~Traverser( void ) {}; 34 35 // Get the number of next states. 36 virtual int getEdgeCountNext( void ) = 0; 37 38 // The return value is the index for moving to the same previous 39 // state again. The indexing of the previous state can be arbitrary, 40 // but zero should be one of the previous index values. The 41 // collect_info parameter will be true once for every edge in the 42 // state graph during the traversal. This allows te traverser to 43 // collect information along its edges. 44 virtual int moveToNext( int index, 45 bool collect_info ) = 0; 46 47 // Go back to a previous state. Due to the return value of 48 // moveToNext(), the state will be unchanged after calling 49 // movetoPrev(moveToNext(index)) with a legal next index. 50 virtual void moveToPrev( int index ) = 0; 51 52 // This function will be called once for every state in a traversal. 53 virtual void collectInfo( void ) = 0; 54 55 // Function for printing the state to cout for debug purposes. 56 virtual void printState( void ) = 0; 57 }; 58 59 // Traverse a structure in a single threaded way. The traverser should 60 // be in the start state. The traverser may not be in the start state 61 // when this function returns. 62 void traverse_simple( Traverser* traverser ); 63 64 // Traverse a structure using several traversers in several 65 // threads. The traversers should all be in the start state. Several 66 // traversers may go through the same state, but collectInfo() is only 67 // called once for each state. The traversers may not be in the start 68 // state when this function returns. 69 void traverse_threaded( Traverser** traverser, 70 int count, 71 int step_count ); 72 73 } 74 #endif // __traverser_h__ 75