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;
}