All pastes #915158 Raw Edit

Something

public text v1 · immutable
#915158 ·published 2008-02-23 15:57 UTC
rendered paste body
vector<unsigned> CMarkov::connect(vector<unsigned> keywords)
{
	vector<unsigned>::iterator it;
	
	map<unsigned, bool> foundnodes; //marks found nodes from the keywords
	map<unsigned, bool> blacknodes; //explored nodes
	deque<unsigned>     graynodes;  //nodes to be explored.
	deque<unsigned>::iterator next; //next gray node in list.
	
	TNodeLinks previousnode;
	
	vector<unsigned> result;
	
	unsigned currentnode;
	if (keywords.count() > 0)
		currentnode = keywords[0];
		foundnodes[currentnode] = true;
	}
	else {
		return result;
	}

	bool finished = false;
	unsigned nodecount = 0;
	graynodes.push_back(currentnode);
	previousnode[currentnode] = 0;
    previousnode[0] = 0;

	while ((!finished) && (nodecount++ <= TRIP_AI_MAXDEPTH))
	{
		graynodes.pop_front();
		if (blacknodes.find(currentnode) == blacknodes.end()) 
		{ //node not black
			
			TGraphH::iterator links = data[1].GetFwdLinks(currentnode);
			blacknodes[currentnode] = true;
			
						 
			//it->first is the node number, 
			//it->second is a map<unsigned, unsigned>
			TNodeLinks::iterator node;
			for (node = links->second.begin(); 
				 node != links->second.end(); ++node)
			{
				if (blacknodes.find(node->first) == blacknodes.end())
				{ //node not black
					unsigned k = 2;
					unsigned previous = previousnode[currentnode];
					bool nth_order_connected = true;
					while (k <= order)
					{
						if ((!data[k].CheckLink(previous, node->first)) 
							|| (!previous)) //either previous zero, or 
											//if not zero, there is a link.
						{
							nth_order_connected = false;
							break;
						}
						previous = previousnode[previous];
						k++;
					}
					if (nth_order_connected)
					{ //add to gray nodes
						graynodes.push_back(node->first);
						previousnode[node->first] = currentnode;
					}
					
				} //if linked node not blacknode 
			} //for all nodes linked to the current
		} //if currentnode not black
		next = graynodes.begin();
		if (next != graynodes.end())
		{
			currentnode = *next;
			//check if we have come to any of the other keyword nodes.
			for (it = keywords.begin(); it != keywords.end(); ++it)
			{
				if ((currentnode == *it) && (!foundnodes[*it]))
				{ // if we arrived to a previously not found node.
					
					unsigned pathnode = currentnode;
					TNodeLinks::iterator node;
					vector<unsigned>::iterator reversalBegin = result.end();
					
					while ( 
						   (( (node = previousnode.find(pathnode)) 
							!= previousnode.end() ))
						  && (!foundnodes[pathnode])
						   )
					{
						result.push_back(node->second);
						pathnode=node->second;
					}
					foundnodes[currentnode] = true; // mark node as found
					blacknodes.clear(); // clear all black nodes.
					graynodes.clear(); // clear all gray nodes
					graynodes.push_back(currentnode);
					
					reverse(reversalBegin, result.end()); // partial reverse.
					if (foundnodes.count() == keywords.count()) 
					{
						result.push_back(currentnode); // push last node :P
						finished = true;
					}
					//otherwise, we are not finished, begin exploring again
					break; //break the for loop. current node is setup right.
				}
			} //for each keyword	
		}
		else
		{ //fully expanded tree, but no next keyword found.
			graynodes.clear();
			blacknodes.clear();
			results.push_back(0); // add a zero to signify lack of connector
			
			// pick any node not in foundnodes as the next node to resume.
			for (it = keywords.begin(); it != keywords.end(); ++it)
			{
				if (!foundnodes[*it])
				{
					currentnode = *it;
					graynodes.push_back(currentnode);
					break;
				}
			}
		} //assigning next node done.
		
	} // done finding the path (or a partial path)
	  //return whatever results found.
	return results;
}