/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *                       GRAPHS                           * */
/* *                                                        * */
/* *  $Module:   GRAPH                                      * */ 
/* *                                                        * */
/* *  Copyright (C) 1998, 2000, 2001 MPI fuer Informatik    * */
/* *                                                        * */
/* *  This program is free software; you can redistribute   * */
/* *  it and/or modify it under the terms of the FreeBSD    * */
/* *  Licence.                                              * */
/* *                                                        * */
/* *  This program is distributed in the hope that it will  * */
/* *  be useful, but WITHOUT ANY WARRANTY; without even     * */
/* *  the implied warranty of MERCHANTABILITY or FITNESS    * */
/* *  FOR A PARTICULAR PURPOSE.  See the LICENCE file       * */ 
/* *  for more details.                                     * */
/* *                                                        * */
/* *                                                        * */
/* $Revision: 1.3 $                                         * */
/* $State: Exp $                                            * */
/* $Date: 2011-05-22 13:27:17 $                             * */
/* $Author: weidenb $                                       * */
/* *                                                        * */
/* *             Contact:                                   * */
/* *             Christoph Weidenbach                       * */
/* *             MPI fuer Informatik                        * */
/* *             Stuhlsatzenhausweg 85                      * */
/* *             66123 Saarbruecken                         * */
/* *             Email: spass@mpi-inf.mpg.de                * */
/* *             Germany                                    * */
/* *                                                        * */
/* ********************************************************** */
/**************************************************************/


/* $RCSfile: graph.c,v $ */

#include "graph.h"

static LIST graph_ROOTS;      /* used as stack by SCC algorithm */
static LIST graph_UNFINISHED; /* used as stack by SCC algorithm */

/*************************************************************
*Previously inlined functions                                *  
*************************************************************/

NAT graph_NodeNumber(GRAPHNODE Node)
{
  return Node->number;
}

int graph_NodeDfsNum(GRAPHNODE Node)
{
  return Node->dfs_num;
}

void graph_NodeSetDfsNum(GRAPHNODE Node, int Number)
{
  Node->dfs_num = Number;
}

int graph_NodeCompNum(GRAPHNODE Node)
{
  return Node->comp_num;
}

void graph_NodeSetCompNum(GRAPHNODE Node, int Number)
{
  Node->comp_num = Number;
}

LIST graph_NodeNeighbors(GRAPHNODE Node)
{
  return Node->neighbors;
}

POINTER graph_NodeInfo(GRAPHNODE Node)
{
  return Node->info;
}

void graph_NodeSetInfo(GRAPHNODE Node, POINTER Info)
{
  Node->info = Info;
}

NAT graph_NodeOutdegree(GRAPHNODE Node)
{
  return list_Length(graph_NodeNeighbors(Node));
}

BOOL graph_NodeVisited(GRAPHNODE Node)
{
  return graph_NodeDfsNum(Node) >= 0;
}

BOOL graph_NodeCompleted(GRAPHNODE Node)
{
  return graph_NodeCompNum(Node) >= 0;
}

NAT graph_Size(GRAPH Graph)
{
  return Graph->size;
}

LIST graph_Nodes(GRAPH Graph)
{
  return Graph->nodes;
}
/*************************************************************
*Previously inlined functions ends here                      *  
**************************************************************/

void graph_NodePrint(GRAPHNODE Node)
/**************************************************************
  INPUT:   A graph node.
  RETURNS: Nothing.
  EFFECT:  Prints some node information to stdout.
***************************************************************/
{
  printf("(%zd,%d,%d) ", graph_NodeNumber(Node), graph_NodeDfsNum(Node),
	 graph_NodeCompNum(Node));
}


GRAPH graph_Create(void)
/**************************************************************
  INPUT:   None.
  RETURNS: A new graph without nodes and edges.
***************************************************************/
{
  GRAPH result;

  result = memory_Malloc(sizeof(GRAPH_STRUCT));
  result->size      = 0;
  result->dfscount  = 0;
  result->compcount = 0;
  result->nodes     = list_Nil();
  return result;
}


void graph_Delete(GRAPH Graph)
/**************************************************************
  INPUT:   A graph.
  RETURNS: Nothing.
  EFFECT:  All memory required by the graph and its nodes
           is freed.
***************************************************************/
{
  for ( ; !list_Empty(Graph->nodes); Graph->nodes = list_Pop(Graph->nodes)) {
    list_Delete(graph_NodeNeighbors(list_Car(Graph->nodes)));
    memory_Free(list_Car(Graph->nodes), sizeof(GRAPHNODE_STRUCT));
  }
  memory_Free(Graph, sizeof(GRAPH_STRUCT));
}


GRAPHNODE graph_GetNode(GRAPH Graph, NAT Number)
/**************************************************************
  INPUT:   A graph and the ID of a node.
  RETURNS: The node with the requested number or NULL
           if such a node doesn't exist.
***************************************************************/
{
  LIST scan;

  for (scan = Graph->nodes; !list_Empty(scan); scan= list_Cdr(scan)) {
    if (graph_NodeNumber(list_Car(scan)) == Number)
      return list_Car(scan);
  }

  return NULL;
}


GRAPHNODE graph_AddNode(GRAPH Graph, NAT Number)
/**************************************************************
  INPUT:   A graph and the ID of a node.
  RETURNS: A node with the requested number.
  EFFECT:  If the graph has no such node, a new node is created.
***************************************************************/
{
  GRAPHNODE result;

  result = graph_GetNode(Graph, Number);
  if (result == NULL) {
    result = memory_Malloc(sizeof(GRAPHNODE_STRUCT));
    Graph->nodes      = list_Cons(result, Graph->nodes);
    result->number    = Number;
    result->dfs_num   = -1;
    result->comp_num  = -1;
    result->info      = NULL;
    result->neighbors = list_Nil();
  }
  return result;
}


void graph_AddEdge(GRAPHNODE From, GRAPHNODE To)
/**************************************************************
  INPUT:   Two graph nodes.
  RETURNS: Nothing.
  EFFECT:  Adds a single (directed) edge (From, To).
***************************************************************/
{
  From->neighbors = list_Cons(To, From->neighbors);
}


void graph_DeleteEdge(GRAPHNODE From, GRAPHNODE To)
/**************************************************************
  INPUT:   Two graph nodes.
  RETURNS: Nothing.
  EFFECT:  Removes ALL edges (From, To) from a graph.
***************************************************************/
{
  From->neighbors = list_PointerDeleteElement(From->neighbors, To);
}


void graph_DeleteDuplicateEdges(GRAPH Graph)
/**************************************************************
  INPUT:   A graph.
  RETURNS: Nothing.
  EFFECT:  Removes duplicate edges between all nodes.
***************************************************************/
{
  LIST scan;

  for (scan = graph_Nodes(Graph); !list_Empty(scan); scan = list_Cdr(scan)) {
    GRAPHNODE n = list_Car(scan);
    n->neighbors = list_PointerDeleteDuplicates(n->neighbors);
  }
}


void graph_SortNodes(GRAPH Graph, BOOL (*SortFunction)(GRAPHNODE, GRAPHNODE))
/**************************************************************
  INPUT:   A graph and a sorting function for graph nodes.
  RETURNS: Nothing.
  EFFECT:  The node list is sorted with respect to the
           sorting function.
***************************************************************/
{
  Graph->nodes = list_Sort(graph_Nodes(Graph),
			   (BOOL (*) (POINTER, POINTER)) SortFunction);  
}


static void graph_ReinitDFS(GRAPH Graph)
/**************************************************************
  INPUT:   A graph.
  RETURNS: Nothing.
  EFFECT:  Prepares the graph and its nodes for a new DFS run.
           The DFS and COMP numbers are reset.
***************************************************************/
{
  LIST scan;

  Graph->dfscount  = 0;
  Graph->compcount = 0;

  for (scan = graph_Nodes(Graph); !list_Empty(scan); scan = list_Cdr(scan)) {
    graph_NodeSetDfsNum(list_Car(scan), -1);
    graph_NodeSetCompNum(list_Car(scan), -1);
  }
}


static void graph_InternSCC(GRAPH Graph, GRAPHNODE Node)
/**************************************************************
  INPUT:   A graph and a node of the graph.
  RETURNS: Nothing.
  EFFECT:  This is an internal function used by
           graph_StronglyConnnectedComponents.
	   It sets information in the graph structure which
           specifies the strongly connected components of
           the graph.
***************************************************************/
{
  GRAPHNODE n;
  LIST      scan;
  NAT       act_dfs;

  act_dfs = (Graph->dfscount)++;
  graph_NodeSetDfsNum(Node, act_dfs);

  graph_UNFINISHED = list_Push(Node, graph_UNFINISHED);
  graph_ROOTS      = list_Push(Node, graph_ROOTS);

  /* putchar('\n'); list_Apply(graph_NodePrint, graph_UNFINISHED);
     putchar('\n'); list_Apply(graph_NodePrint, graph_ROOTS);
     fflush(stdout); DBG */

  for (scan = graph_NodeNeighbors(Node);
       !list_Empty(scan); scan = list_Cdr(scan)) {
    n = list_Car(scan);
    if (!graph_NodeVisited(n)) {
      graph_InternSCC(Graph, n);  /* Visit <n> */
    } else if (!graph_NodeCompleted(n)) {
      /* <n> was visited but is not yet in a permanent component */
      NAT dfs_num_of_n = graph_NodeDfsNum(n);
      while (!list_StackEmpty(graph_ROOTS) &&
	     graph_NodeDfsNum(list_Top(graph_ROOTS)) > dfs_num_of_n)
	graph_ROOTS = list_Pop(graph_ROOTS);
      /* putchar('\n'); list_Apply(symbol_Print, graph_UNFINISHED);
	 putchar('\n'); list_Apply(symbol_Print, graph_ROOTS);
	 fflush(stdout); DBG */
    }
  }

  /* printf("\nDFS(%u) complete.", graph_NodeNumber(Node)); DBG */

  if (Node == list_Top(graph_ROOTS)) {
    /* Node is root of a component, so make this component permanent */
    while (!list_StackEmpty(graph_UNFINISHED) &&
	   graph_NodeDfsNum(list_Top(graph_UNFINISHED)) >= act_dfs) {
      n = list_Top(graph_UNFINISHED);
      graph_UNFINISHED = list_Pop(graph_UNFINISHED);
      graph_NodeSetCompNum(n, Graph->compcount);
    }
    Graph->compcount++;
    graph_ROOTS = list_Pop(graph_ROOTS);
  }

  /* putchar('\n'); list_Apply(graph_NodePrint, graph_UNFINISHED);
     putchar('\n'); list_Apply(graph_NodePrint, graph_ROOTS); fflush(stdout); DBG */
}


NAT graph_StronglyConnectedComponents(GRAPH Graph)
/**************************************************************
  INPUT:   A graph.
  RETURNS: The number of strongly connected components
           in the graph.
  EFFECT:  This function sets the component numbers of all nodes.
           Two nodes that belong to the same component will have
           the same component number.
	   The algorithm is taken from the script
           "Datenstrukturen und Algorithmen" by Kurt Mehlhorn
           in winter semester 1997/98, pages 86-92.
***************************************************************/
{
  LIST scan;

  if (Graph->dfscount != 0)
    graph_ReinitDFS(Graph); /* Reinitializations for Depth First Search */

  graph_ROOTS          = list_Nil();
  graph_UNFINISHED     = list_Nil();

  for (scan = graph_Nodes(Graph); !list_Empty(scan); scan = list_Cdr(scan)) {
    if (!graph_NodeVisited(list_Car(scan)))
      graph_InternSCC(Graph, list_Car(scan));
  }
  return Graph->compcount;
}


void graph_Print(GRAPH Graph)
/**************************************************************
  INPUT:   A graph.
  RETURNS: Nothing.
  EFFECT:  The adjacency list representation of the graph
           is printed to stdout.
***************************************************************/
{
  LIST scan1, scan2;
  
  for (scan1 = graph_Nodes(Graph); !list_Empty(scan1); scan1 = list_Cdr(scan1)) {
    printf("\n%zd -> ", graph_NodeNumber(list_Car(scan1)));
    for (scan2 = graph_NodeNeighbors(list_Car(scan1)); !list_Empty(scan2);
	 scan2 = list_Cdr(scan2)) {
      printf("%zd,", graph_NodeNumber(list_Car(scan2)));
    }
  }
}