Solved

# Colored DFS of Directed Graph

Posted on 2006-05-07
1,373 Views
Hi,

I have an assignment to do in which I must figure out whether a given state machine has a cycle or not. The state transition table must be read from a given file. Once I have the state transition graph I must traverse it using the DFS (Depth First Search) and find out whether it has cycle or not.

You must have data structures to represent the nodes and transitions in the graph. Each state is represented using a node. The idea is to keep pointers to next nodes and corresponding input and output information associated with the transitions in the node itself. Every transition has an input on which it is activated and an output associated with it.
This information can be enclosed in a transition structure. A node has 2 transitions associated with it and also a state number. I must use the DFS to detect a cycle in the graph, marking nodes as they are encountered (say by adding them to a set of visited nodes). If a previously marked node is seen again, then a cycle exists. However, this algorithm has a problem and can falsly report a cycle. Therefore I must use a modified depth first search called a colored DFS. All nodes are initially marked white. When a node is encountered, it is marked grey, and when its descendants are completely visited, it is marked black. If a grey node is ever encountered, then there is a cycle.

The code I have successfully reads the transition table and stores it into a vector. From the vector, it creates a directed graph with each state as a Node, which is a defined class. I know the states are being read correctly from outputs I used to debugging so I won't post the ccomand function. However, the program terminates somewhere in the process of making the graph and performing the DFS traversal and I can't pinpoint why.

Any comments or advice on why or how I could resolve this problem would be extremely appreciated. Thank you for your time.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;

class Node
{
public:

//A node contains a state, a pointer to next state if input is one, a pointer to next state if input is zero, and a color
string State;
string Color;
string outputOne;
string outputZero;
Node *inputOne;
Node *inputZero;

//Default constructor: state value empty, pointers null
Node (string s)
{
State = s;
inputOne = NULL;
inputZero = NULL;
outputOne = "";
outputZero = "";
Color = "white";
}

//Default constructor: given state and output values, pointers null
Node (string s, string z_output, string o_output)
{
State = s;
inputOne = NULL;
inputZero = NULL;
outputOne = o_output;
outputZero = z_output;
Color = "white";
}

string Get_State()
{      return State;      }

//Assign pointer to new state if input is one
void Set_Next_State_InputOne (Node* a_state)
{      inputOne = a_state;      }

//Assign pointer to new state if input is zero
void Set_Next_State_InputZero (Node* a_state)
{      inputZero = a_state;      }

};

bool Depth_First_Search (vector <Node*> pointers, int n);
int Color_Depth_First_Search (Node* p);
int ccommand(char ***argv);

int main(int argc, char** argv)
{
argc = ccommand(&argv);
ifstream infile ( argv[1] );
string s;
int index;
vector <string> transition_table;
vector <Node*> state_pointers;

//Put the Transition Table Into a Vector
while (!infile.eof())
{
infile >> s;
transition_table.push_back(s);
}
infile.close();

index = 0;

//Set the Output Values for All States
for (int i=0; i < transition_table.size()/5; i++)
{
Node* p = new Node(transition_table[index], transition_table[index+3], transition_table[index+4]);
state_pointers.push_back(p);
index = index + 5;
}

index = 1;
Node* ptr;
string nsone;
string nszero;

//Make a Directed Graph by Setting Pointers
for (int i=0; i< transition_table.size()/5; i++)
{
ptr = state_pointers[i];
nsone = transition_table[index];
nszero = transition_table[index+1];

if (nszero != transition_table[0] and nszero != transition_table[5] and nszero != transition_table[10] and nszero != transition_table[15])
{
Node* p = new Node(nszero);
state_pointers.push_back(p);
ptr->Set_Next_State_InputZero (p);
}
else
{
for (int j=0; j < transition_table.size()/5; j++)
{
Node* p;
p = state_pointers[j];

if (p->State == nszero)
{      ptr->Set_Next_State_InputZero (p);      }
}
}

if (nsone != transition_table[0] and nsone != transition_table[5] and nsone != transition_table[10] and nsone != transition_table[15])
{
Node* p = new Node(nsone);
state_pointers.push_back(p);
ptr->Set_Next_State_InputOne (p);
}
else
{
for (int j=0; j < transition_table.size()/5; j++)
{
Node* p;
p = state_pointers[j];

if (p->State == nsone)
{      ptr->Set_Next_State_InputOne (p);      }
}

}

index = index + 5;
}

int num_vertices;
bool cyclic;

//Perform Colored DFS Traversal To Determine Cyclicity
num_vertices = transition_table.size()/5;
cyclic = Depth_First_Search (state_pointers, num_vertices);

if (cyclic)
{      cout << endl << "This finite state machine has at least one cycle.";      }
else
{      cout << endl << "This finite state machine does not have any cycle.";      }
}

bool Depth_First_Search (vector <Node*> pointers, int n)
{
Node* p;
int cycle_found;

for (int i=0; i < n; i++)
{
p = pointers[i];
if (p->Color == "white")
{      cycle_found = Color_Depth_First_Search(p);      }
}

if (cycle_found)
{      return true;      }
else
{      return false;      }
}

int Color_Depth_First_Search (Node* p)
{

p->Color = "grey";

if (p->inputOne->Color == "grey")
{
return 1;            // return cycle_found
}
else
if (p->inputOne->Color == "white")
{
Color_Depth_First_Search(p);
}

if (p->inputZero->Color == "grey")
{
return 1;            // return cycle_found
}
else
if (p->inputZero->Color == "white")
{
Color_Depth_First_Search(p);
}

p->Color = "black";

return 0;                    //return no_cycle at vertex u;
}
0
Question by:SurayaF

Author Comment

0

LVL 11

Accepted Solution

I don't understand how you are representing the state machine.
It seems incorrect.

A node contains (and you should make those private for good design)
//A node contains a state, a pointer to next state if input is one, a pointer to next state if input is zero, and a color
string State;
string Color;
string outputOne;
string outputZero;
Node *inputOne;
Node *inputZero;
if input==0, you transition to state inputZero, and if 1 you transition to state inputOne. What if they are NULL, is that an error that should never occur? You don't appear to check for that in your depth first search.
state appears to be unused in each node.

Unless the assignment explicitly requires it, there is no reason to use the convoluted white/black/grey scheme. Mark all nodes visited = false, and set visited= true every time you visit one. If you look at a node with visited = true, you have a cycle. Your depth first search looks ok except if there are nulls, which you have not checked in that routine. The whole thing is quite a bit more complicated than it needs to be, which isn't helping your cause. Here's a dramatically simplified design:

class Node {
private:
string output0, output1;
int next0;
int next1;
bool visited;
public:
friend class FSM;
};

class FSM {
private:
vector<Node> nodes;
int state;
bool detectCycle(int s) {
if (nodes[s].visited)
return true;
nodes[s].visited = true;
bool c = detectCycle(nodes[s].next0);
if (c) return true;
return detectCycle(nodes[s].next1);
}
};

In the above model, state = 0 to start
If you want to stick with pointers, then replace the int by Node*

0

Author Comment

Hi dbkruger,

Thanks for your help. My assignment actually requires that the depth first search algorithm be modified to use the white/grey/black scheme. I have since continued debugging the program and when I finally got it to stop terminating prematurely, I got it to output correctly according to requirements.

Nevertheless, thank you for your time.
0

## Featured Post

This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.