/****************************************************************************
*****************************************************************************

FILE NAME: dfs.c 

ABSTRACT: File containing code for depth-first search.

AUTHOR: Shantanu Tarafdar

*****************************************************************************
****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <HLS/generic.h>
#include <HLS/graphlib.h>

/* Global display enable variable */
extern Boolean display;

/*****************************************************************************

FUNCTION: visit_node

AUTHOR: Shantanu Tarafdar     DATE: Sep 29, 1997

ABSTRACT: Visits a node in DFS order. i.e. it passes through recursively unless
          all of it's children are visited.

RETURNS: Nothing

*****************************************************************************/

void visit_node(Node *n, List *dfs_nl)
{
  char *b;     /* Value of "visited" attribute */
  Edge *e;     /* Outedge of node n */
  Node *c_n;   /* Child node of node n */

  /* Sanity check */
  assert(n);
  assert(dfs_nl);

  /* Check if this node is visited, and ignore it if it has been or is being
     visited */
  b = node_getattr(n, "visited?");
  assert(b);                              /* Sanity check */
  if ((streq(b, "yes") == TRUE) ||
      (streq(b, "is being visited") == TRUE)) 
    return;

  /* We need to visit this node, so mark it as being visited */
  node_setattr(n, "visited?", "is being visited");
  if (display) {
    /* Re-display graph after greying out this node */
    node_setattr(n, "vcg:color", "lightgrey"); 
    node_setattr(n, "vcg:textcolor", "darkgrey");
    graph_display(node_get_owner_graph(n));
  }

  /* Otherwise, visit all the children first */
  l_fforeach(node_outedges(n), e) {
    c_n = edge_dst(e);        /* Get the child node */
    assert(c_n);              /* Sanity check */
    visit_node(c_n, dfs_nl);  /* Visit the node */
  } l_endfor;

  /* All children have been visited. Mark this node as visited */
  node_setattr(n, "visited?", "yes"); 
  if (display) {
    /* Re-display graph after blackening this node */
    node_setattr(n, "vcg:color", "black");
    node_setattr(n, "vcg:textcolor", "white");
    graph_display(node_get_owner_graph(n));
  }

  /* Add it to the end of the DFS nodelist */
  l_append(dfs_nl, n);
  
  return;
}

/*****************************************************************************

FUNCTION: graph_dfs

AUTHOR: Shantanu Tarafdar     DATE: Sep 29, 1997

ABSTRACT: Executes a depth-first search on graph and returns a list of nodes
          in that order. First node visited is at the head of the list.

RETURNS: Nothing

*****************************************************************************/

List *graph_dfs(Graph *g)
{
  List *dfs_nl;  /* DFS nodelist */
  Node *n;       /* Node of graph */

  /* Sanity check */
  assert(g);

  /* Create the DFS nodelist */
  dfs_nl = l_new();
  
  /* Mark all nodes in graph as not visited */
  l_fforeach(graph_nodes(g), n) {
    node_setattr(n, "visited?", "no");
    if (display) {
      /* Whiten all nodes on display */
      node_setattr(n, "vcg:color", "white");
      node_setattr(n, "vcg:textcolor", "black");
    }
  } l_endfor;
  
  /* Re-display graph */
  if (display)
    graph_display(g);

  /* For every node, do */
  l_fforeach(graph_nodes(g), n) {
    visit_node(n, dfs_nl); /* Start the DFS here */
  } l_endfor;

  return dfs_nl;
}