Ok the graph is made correctly. The problem with my DFS function.. can someone please help? Any ideas are appreciated.

Solved

Posted on 2006-05-07

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;

}

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

}

infile.close();

index = 0;

//Set the Output Values for All States

for (int i=0; i < transition_table.size()/5;

{

Node* p = new Node(transition_table[inde

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;

{

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_InputZ

}

else

{

for (int j=0; j < transition_table.size()/5;

{

Node* p;

p = state_pointers[j];

if (p->State == nszero)

{ ptr->Set_Next_State_InputZ

}

}

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_InputO

}

else

{

for (int j=0; j < transition_table.size()/5;

{

Node* p;

p = state_pointers[j];

if (p->State == nsone)

{ ptr->Set_Next_State_InputO

}

}

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;

}

3 Comments

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:

// write your 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*

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.

Title | # Comments | Views | Activity |
---|---|---|---|

ADO Memory leak with DELPHI 2007 | 37 | 140 | |

How do I add zip/compression functionality to a C++ (Windows and Linux) application? | 3 | 73 | |

Losing latter half of command line in Visual Studio C++ online program | 10 | 67 | |

How to copy an image file into clipboard C/C++? | 1 | 108 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**19** Experts available now in Live!