/* This is a program written in D (dlang.org) to obtain the strongly connected components (SCC's) of a directed graph 
using Tarjan's algorithm (https://doi.org/10.1137/0201010).
 An SCC is a subset of the nodes of a directed graph (digraph) together with all the edges both ends of which are in
 the subset, such that every pair of nodes in the SCC is connected in both directions, directly or indirectly via the directed edges.
 This can includes single nodes regardless of whether or not they are connected to themselves.
 The input graph is input in the following format:
For each input node, all the nodes it leads to are given on one line. Every node is represented by a character string, and "leads to" is represented by ">" and the list of nodes lead to is preceded by integer giving the number of them, and they are separated and termined by &.
Extra spaces between the strings are ignored. For example

1 > 0
1,4 > 0
2 > 0
3 > 1 12 &
12 > 2 3 & 13,57 &
13,57 > 4  1,4 & 79 & 3 & 116 &
13,57,61 > 4 3 & 12 & 39 & 3 &

The program creates and output text file containing the contents of each SCC.
To run the program first compile it then run it with the data input file name e.g.

dmd Tarjan.d
./Tarjan <file of input graph>
*/


import std.stdio;
import std.algorithm;
import std.string;
import std.file;
import std.conv;
  class vertex {
    string name;
    int index;
    int lowlink;
    bool onStack;
    vertex [] descendents;
    void write(){
      writeln("(name = ",name, ", index = ",index," lowlink = ",lowlink," onStack = ",onStack,", # descendents = ",descendents.length,")");}
    this(string name,int index,int lowlink,bool onStack,vertex [] descendents){
      this.name = name;
      this.index = index;
      this.lowlink = lowlink;
      this.onStack = onStack;
      this.descendents = descendents;}
    }
  int index;
  vertex w;
  vertex[] S;//the stack
  vertex[] SCC;//accumulates each SCC as it is found, then it is emptied to the output.
  vertex[] G;//the graph
  File of;//output file
//************************************ function strongConnect ********************************
// index is zero if it has not been set. Values >0 have been set
void strongConnect(vertex v){
  v.index = index;
  v.lowlink = index;
  index++;
  S ~= v;//push in v
  v.onStack = true;
  foreach(w;v.descendents){
    if(w.index == -1){writeln("calling strongConnect for ",w.name);
      strongConnect(w);
      writeln("strongConnect for ",w.name," ended");
      v.lowlink = min(v.lowlink,w.lowlink);}
    else if(w.onStack){
      v.lowlink = min(v.lowlink,w.index);}}
  if(v.lowlink == v.index){
    SCC = remove!("true")(SCC);//empties SCC if not already empty
    do{
      writeln("S.length-1 = ",S.length-1);
      w= S[(S.length)-1];
      SCC ~= w;
      --S.length;//s.pop() 
      w.onStack = false;
      writeln("w = ");w.write();writeln(" v = ");v.write();}while(w.name!= v.name);
    of.write("SCC = ");foreach(v1;SCC){of.write(v1.name);of.write(" ");}of.writeln("");}
}
//************************************* function G_write_full ***************************
void G_write_full(){
  foreach(v;G){
    v.write();
    foreach(x;v.descendents){
      write("  ");x.write();}}}
//************************************* G_write_short ***********************************
void G_write_short(){
  foreach(v;G){v.write();}}
//************************************* function main ***********************************
void main(string[] args){
  writeln("This is program Tarjan that implements Tarjan's algorithm for finding the");
  writeln("maximal strongly connected components of the graph G");
  if(args.length!=2){
    writeln("Usage: <directory and program name> <input file for the graph");
    writeln("For example if the program is in the currect directory");
    writeln("./<executable program name> <input file for the graph>");
    return;}
//create the input and output file names, and File objects, and reading in the data sp.
  string inputfilename = args[1];
  File infile = File(inputfilename,"r");
  if(!exists(inputfilename)){writeln("I cannnot find file ",inputfilename);return;}
  char[] outputfilename = can_write(inputfilename,"_out.txt");
  of.open(outputfilename.idup,"w");
  string[][] sp;//Each line corresponds to a set of strings, of which element 0 is the LHS of the string pairs and the remaining
  string[] buf;//the vertex names (with repetition)
//elements are the RHS's corresponding to the LHS.
  //read in string pairs for the edges and populate vp.
  string s1,s2;
  int n;
  string line;
  for(;;){
    infile.readf(" %s >",s1);buf ~= s1;//the LHS
    writeln("s1 = ",s1);
    if(infile.eof())break;
    infile.readf(" %s",n);
    for(int i=0;i<n;++i){
      writeln("i = ",i);
      infile.readf(" %s &",s2);
      writeln("s2 = ",s2);buf ~= s2; sp ~= [s1,s2];}}
//    infile.readf(" %s & %s\n ",s1,s2);
//    sp ~= [s1,s2];buf ~= s1; buf ~= s2;}
//Creating from sp the data structures V,G.
//sp = [["a", "b"], ["a", "c"], ["c", "d"], ["c", "a"]];
//string[] V = ["a", "b", "c", "d"];
  writeln("sp = ",sp);
  auto V = buf.sort().uniq();//vertex names sorted, and reduced to a unique set
  writeln("V = ",V);
  foreach(s;V){//put the vertex names into G together with default values of link, lowlink, and inStack.
    G ~= new vertex(s,-1,0,false,[]);}//index is -1 if it is undefined (see algorithm in Wikipedia).
//  writeln("Writing out G");
//  G_write_full();
  foreach(s;G){//put in G the array of pointers to descendents
    foreach(link;sp){
      if (link[0] == s.name){
        foreach(t;G){
          if(link[1] == t.name) {
            writeln("s.name = ",s.name," t.name = ",t.name);
            s.descendents ~= t;}
          }}}writeln("s = ");s.write();}
//write out G
//  G_write_full();
  writeln("Now run Tarjan's algorithm\n\n");
//Tarjan's algorithm
  index=0;
  foreach(v;G){
    if(v.index == -1) {writeln("calling strongConnect for ",v.name);strongConnect(v);writeln("strongConnect for ",v.name," ended");
//  writeln("G = ");G_write_full();
}}}

//************************************** function yes *****************************************
//This function asks the user the question by dispaying the text 'question' and waits for
//the response y (for yes) or n (for no)
bool yes(const char[] question){
  char ans='*';
  bool ret;
  char[] res;
  while(ans!='y' && ans!='n'){
    std.stdio.write(question,"(y/n): ");
    res=chomp(readln().dup);
    ans=res[0];
    if(res.length==1){
      if(ans=='y')ret = true;
      else if(ans=='n') ret = false;}
    else{ans='*';}}
  return ret;
}

//********************************** function can_write **************************************
//This function finds a filename to be written to for output and returns it. It ensures
//that no file is overwritten without the consent of the user. "base_name" is usually the input
//datafile name and "extension" is the default file extension for output (including the dot)
//arrays and class objects are not copied
char[] can_write(const char[] base_name,const char[] extension){
  char[] filename = (base_name ~ extension).dup;
  char[] chars;
  char[] question;
  bool write1,fn,overwrite=false;
  do{
    fn = exists(filename);
    if(fn){
      writeln("The file ",filename," already exists.");
      question="Do you want me to overwrite it?".dup;    
      overwrite=yes(question);
      if(!overwrite){
        writeln("The new path and file name is ",base_name,"<extra characters>",extension);
        write("Enter the extra characters: ");
        readln(chars);chars=chomp(chars);
        filename=base_name ~ chars ~ extension;}}
    write1=(!fn) || overwrite;}
  while (!write1);
  writeln("Output will be to the file ",filename);
  return filename;}