[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1387
  • Last Modified:

Colored DFS of Directed Graph

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
SurayaF
Asked:
SurayaF
  • 2
1 Solution
 
SurayaFAuthor Commented:
Ok the graph is made correctly. The problem with my DFS function.. can someone please help? Any ideas are appreciated.
0
 
dbkrugerCommented:
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:
 // 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*


0
 
SurayaFAuthor Commented:
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

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now