/*****************************************************************
*                                                                *
*                         Projektarbeit                          *
*                                                                *
*   "Implementierung und Darstellung ebener Fraktale mit LEDA"   *
*                                                                *
*                                                                *
*                   (c) 1998 Sascha Broich                       *
*                                                                *
*                                                                *
*       Programmteil für die Klasse der Affinen Automaten        *
*                                                                *
*****************************************************************/


#include <LEDA/array2.h>
#include <LEDA/basic.h>
#include <LEDA/string.h>
#include <LEDA/panel.h>
#include <LEDA/point.h>
#include <LEDA/random_source.h>
#include <LEDA/graph.h>
#include <LEDA/graph_alg.h>
#include <LEDA/plane_alg.h>
#include <LEDA/window.h>
#include <LEDA/ps_file.h>
#include <LEDA/graphwin.h>
#include <LEDA/file.h>
#include <LEDA/queue.h>
#include <stdio.h>
#include <math.h>

using namespace leda;

class AA
{
private:
	static string aa_text;
	static node z0;
	static double minx,miny,maxx,maxy;

public:
	point punkt(double x,double y);
	bool graph_edit(GRAPH<int,string>& ZeigG);
	bool proof(GRAPH<int,string>& ZeigG);
	void graph_copy(GRAPH<int,string>& ZeigG, GRAPH<int,int>& ArbG);
	void det_draw(window& w,array2<double>& f,GRAPH<int,int>& ArbG,array2<double>& fs, array<int>& op_stack,int i,node v,int k);
	void det_draw(ps_file& w,array2<double>& f,GRAPH<int,int>& ArbG,array2<double>& fs,array<int>& op_stack,int i,node v,int k);
	void det_range(array2<double>& f,GRAPH<int,int>& ArbG,array2<double>& fs,array<int>& op_stack,int i,node v,int k);
	void prob_draw(window& w, array2<double>& f,GRAPH<int,int>& ArbG, edge_array<double>& edge_prob, int k);
	void prob_draw(ps_file& w, array2<double>& f,GRAPH<int,int>& ArbG, edge_array<double>& edge_prob, int k);
	void prob_range(array2<double>& f,GRAPH<int,int>& ArbG,edge_array<double>& edge_prob,int k);
	void det(array2<double>& f, GRAPH<int,int>& ArbG, int k);
	void prob(array2<double>& f, GRAPH<int,int>& ArbG, int k,double p);
	void draw(array2<double>& f, GRAPH<int,int>& ArbG);
	bool fs_eingabe(array2<double>& f, GRAPH<int,int>& ArbG);
	void fsave(array2<double>& f);
	void fload(array2<double>& f);
	void make_strong_connected(GRAPH<int,int>& ArbG,const array2<double>& f,array2<double>& fnew, double p);
	void menue();
	static void PAINT(window* win);
	static void Non_Det(GraphWin& gw);
	static void new_edge(GraphWin& grw,edge e);
	static void new_node(GraphWin& grw,node v);
	static char* pix;
	static double size;
	AA();
	~AA();
};

AA::AA(){}

AA::~AA(){}

inline point AA::punkt(double x,double y) 
{
	point p(x,y);
	return(p);
}

string AA::aa_text="Affiner Automat";
node AA::z0;
double AA::maxx;
double AA::maxy;
double AA::minx;
double AA::miny;
char* AA::pix;
double AA::size=900.0;

void AA::graph_copy(GRAPH<int,string>& ZeigG, GRAPH<int,int>& ArbG)
{
	int n,i,j,a;
	string s,t;
	edge e;
	node v,w;

	n=0;
	forall_nodes(v,ZeigG) if(n<ZeigG.inf(v)) n=ZeigG.inf(v);

	array<node> z_list(0,n);

	ArbG.clear();

	for(i=0;i<=n;i++)
	{
		z_list[i]=ArbG.new_node(i);
	}
	forall_edges(e,ZeigG)
	{
		v=z_list[ZeigG.inf(ZeigG.source(e))];
		w=z_list[ZeigG.inf(ZeigG.target(e))];
		s=ZeigG.inf(e)+",";
		printf("\n%2d->%2d:",ZeigG[v],ZeigG[w]);
		i=0;j=0;
		while (j>-1)
		{
			j=s.pos(",",i);
			if (j>i)
			{
				a=atoi(s(i,j-1));
				printf("%2d,",a);
				ArbG.new_edge(v,w,a);
				i=j+1;
			}
		}
	}
}

bool AA::graph_edit(GRAPH<int,string>& ZeigG)
{
	GraphWin gw(ZeigG,"Eingabe des Automaten");
//	gw.auto_create_target=false;
	gw.set_directed(true);
	gw.set_edge_shape(poly_edge,true);
	gw.set_edge_style(solid_edge,true);
	gw.set_edge_thickness(1,true);
	gw.set_edge_width(1,true);
	gw.set_edge_label_type(data_label,true);
	gw.set_node_label_type(data_label,true);

	gw.set_new_node_handler(new_node);
	gw.set_new_edge_handler(new_edge);

	gw_add_simple_call(gw,AA::Non_Det,"Nichtdeterminismen",0);
	gw.enable_calls();	
	int ret=1;
	bool z_null=false;
	while((!z_null)&&ret)
	{
		ret=gw.open();
		node v;
		z_null=proof(ZeigG);
	}
	return(ret);
}


void AA::menue()
{
  int n,m;
  edge e;
  GRAPH<int,string> ZeigG;
  GRAPH<int,int> ArbG;
  while (graph_edit(ZeigG))
    {
      printf("\nGraph eingegeben");
      graph_copy(ZeigG,ArbG);
      printf("\nGraph umgewandelt");
      if (!ArbG.empty()) 
	{
	  e=ArbG.choose_edge();
	  m=ArbG.inf(e);
	  n=ArbG.inf(e);
	  forall_edges(e,ArbG) 
	    {
	      n=(ArbG.inf(e)>n)?ArbG.inf(e):n;
	      m=(ArbG.inf(e)<m)?ArbG.inf(e):m;
	    }
	  array2<double> f(m,n,0,9);
	  while (fs_eingabe(f,ArbG))
	    draw(f,ArbG);
	}
    }
}

bool AA::fs_eingabe(array2<double>& f,GRAPH<int,int>& ArbG)
{
  int i,j;
  int k=0,k_max=50;
  double fix;
  string f_text="abcdef";
  node v;
  edge e;
  int n=f.high1();
  int m=f.low1();
  printf("\nEingabe des Funktionensystems\n");

  forall_edges(e,ArbG) f(ArbG.inf(e),9)=1.0;
  forall_nodes(v,ArbG) if (ArbG.inf(v)==0) z0=v;
  
  array<string> f_num(m,n);
  //array<string> f_num(m);
  for(i=m;i<=n;i++)
    {
      if (i<10) f_num[i]=" ";
      else f_num[i]=(string)(48+(i/10));
      f_num[i]+=(char)(48+(i%10));
    }
  float w,h;
  w=800.0;
  h=(n-m)*60.0+100.0;
  
  panel eingabe((int)w,(int)h,"Eingabe der Funktionen");
  int save=eingabe.button("Speichern");
  int load=eingabe.button("Laden");
  eingabe.buttons_per_line(6);
  for(i=m;i<=n;i++)
    {
      if (f(i,9)==1.0)
	{
	  eingabe.real_item(f_num[i]+"."+f_text(0,0),f(i,0));
	  for(j=1;j<6;j++)
	    eingabe.real_item("    "+f_text(j,j),f(i,j));
	}
      else
	{
	  for(j=0;j<6;j++)
	    f(i,j)=0;
	}
    }
  int ok=eingabe.button("OK");
  int no=eingabe.button("Abbrechen");
  int ch=-1;
  eingabe.display();
  while (ch!=no)
    {
      ch=eingabe.read();
      if (ch==save)
	{
	  eingabe.close();
	  fsave(f);
	  eingabe.display();
	}
      
      if (ch==load)
	{
	  eingabe.close();
	  fload(f);
	  eingabe.display();
	}
      
      if(ch==ok) 
	{
	  for (i=m;i<=n;i++)
	    {
	      if(f(i,9)==1.0);
	      {
		fix=((1-f(i,0))*(1-f(i,3)))-(f(i,1)*f(i,2));
		if(fix!=0.0)
		  {
		    f(i,6)=((f(i,1)*f(i,5))+(f(i,4)*(1-f(i,3))))/fix;
		    f(i,7)=((f(i,2)*f(i,4))+(f(i,5)*(1-f(i,0))))/fix;
		  }
		else
		  {
		    f(i,6)=0.0;
		    f(i,7)=0.0;
		  }
	      }
	    }
	  maxx=f(m,6);
	  maxy=f(m,7);
	  minx=f(m,6);
	  miny=f(m,7);
	  
	  eingabe.close();
	  return(true);
	}
    }
  return(false);
}

void AA::draw(array2<double>& f, GRAPH<int,int>& ArbG)
{
	int n=f.high1();
	int i,k;

	array<string> f_num(n+1);
	for(i=1;i<=n;i++)
	{
		if (i<10) f_num[i]+=" ";
		else f_num[i]+=(char)(48+(i/10));
		f_num[i]+=(char)(48+(i%10));
	}


	panel choose(aa_text);
	choose.text_item("Wählen Sie zwischen deterministischer und probabilistischer Berechnung des "+aa_text);
	choose.buttons_per_line(2);
	int Det=choose.button("Deterministisch");
	int Prob=choose.button("Probabilistisch");
	int no=choose.button("Abbrechen");
	int choice=-1;
	choose.display();
	while (choice!=no)
	{
		choice=choose.read();
		if (choice==Det) 
		{
			choose.close();
			panel detk("Deterministischer "+aa_text);
			detk.int_item("Iterations-Tiefe",k=1,0,20);
			detk.real_item("Fenstergroesse",size);
			int kok=detk.button("OK");
			int kno=detk.button("Abbrechen");
			detk.display();
			choice=-1;
			while (choice!=kno)
			{
				choice=detk.read();
				if (choice==kok)	
				{
					detk.close();
					det(f,ArbG,k);
					detk.display();
				}
			}
			detk.close();
			choice=-1;
			choose.display();
		}
		else if (choice==Prob) 
		{
                        double p;
        	        choose.close();
			string f_text="abcdef";
			panel prob_for_func("Wahrscheinlichkeiten");	//Eingabe der Wahrscheinlichkeiten
			for (i=1;i<=n;i++)
			{
				if (f(i,8)<0.01)
				  f(i,8)=sqrt((f(i,0)*f(i,3)-f(i,1)*f(i,2))*(f(i,0)*f(i,3)-f(i,1)*f(i,2)))+0.01; // Initialisieren der Wahrscheinlichkeit mit Determinantenbetrag
			}
			for (i=1;i<=n;i++)
			{
				prob_for_func.real_item("Funktion "+f_num[i],f(i,8));
			}
                        prob_for_func.real_item("Wahrscheinlichkeit weiterer Funktionen ",p=0.01);
			prob_for_func.int_item("Rekursionstiefe",k=10000);
			prob_for_func.real_item("Fenstergroesse",size);
			int pok=prob_for_func.button("OK");
			int pno=prob_for_func.button("Abbrechen");
			int psav=prob_for_func.button("Speichern");
			prob_for_func.display();
			choice=-1;
			while (choice!=pno)
			{
				choice=prob_for_func.read();
				if (choice==pok)
				{
					prob_for_func.close();
					prob(f,ArbG,k,p);
					prob_for_func.display();
				}
				if(choice==psav)	//Moeglichkeit zum Abspeichern der Wahrscheinlichkeiten
				{
					prob_for_func.close();
					fsave(f);
					prob_for_func.display();
				}
			}
			prob_for_func.close();
			choose.display();
		}
	}
	choose.close();
}

void AA::det(array2<double>& f, GRAPH<int,int>& ArbG, int k)
{
	float t0,t1,t2,t3,b,h;
	array2<double> fs(k+1,6);
	array<int> op_stack(k);
	node v;
	forall_nodes(v,ArbG) if(ArbG.inf(v)==0) z0=v;

	fs(0,0)=1.0;
	fs(0,1)=0.0;
	fs(0,2)=0.0;
	fs(0,3)=1.0;
	fs(0,4)=0.0;
	fs(0,5)=0.0;

	maxx=f(f.low1(),6);
	maxy=f(f.low1(),7);
	minx=f(f.low1(),6);
	miny=f(f.low1(),7);

	panel range("Berechne Bereich");
	range.button("Bitte Warten,Berechne Bereich");
	range.display();
	t0=used_time();

	det_range(f,ArbG,fs,op_stack,0,z0,k);

	t1=used_time();
	range.close();

	if (minx==maxx) maxx=minx+1;

	b=maxx-minx;
	h=maxy-miny;
	minx-=b*0.1;
	miny-=h*0.1;
	maxx+=b*0.1;
	maxy+=h*0.1;
	b*=1.2;
	h*=1.2;

	if(b>h) 
	{
		h*=size/b;
		b=size;
	}
	else
	{
		b*=size/h;
		h=size;
	}

	printf("\n Range:   (%.3f,%.3f) zu (%.3f,%.3f)",minx,miny,maxx,maxy);
	window w((int)b,(int)h,"Deterministischer "+aa_text);
	w.set_redraw(AA::PAINT);
	w.set_flush(true);
	w.init(minx,maxx,miny);
	printf("\n Fenster: (%.3f,%.3f) zu (%.3f,%.3f) mit %.3f\n",w.xmin(),w.ymin(),w.xmax(),w.ymax(),w.scale());
	w.display();

	t2=used_time();

	det_draw(w,f,ArbG,fs,op_stack,0,z0,k);
	pix=w.get_window_pixrect();
	
	t3=used_time();

	printf("%.2f und %.2f Sekunden.\n",t1-t0,t3-t2);

	panel wp("Fertig");
	int wok=wp.button("Fertig");
	int wsave=wp.button("Speichern");
	wp.display();
	int wch=-1;
	while (wch!=wok)
	{
		wch=wp.read();
		if (wch==wsave)
		{
			wp.close();
			string name;
			panel w2ps("Speichern");
			w2ps.string_item("Dateiname",name);
			int ps_ok=w2ps.button("Speichern");
			int ps_no=w2ps.button("Abbrechen");
			int ps_ch=-1;
			w2ps.display();
			while ((ps_ch!=ps_ok)&&(ps_ch!=ps_no))
			{
				ps_ch=w2ps.read();
				if (ps_ch==ps_ok) 
				{
					panel ps_wait("Bitte warten");
					ps_wait.button("Bitte warten");
					ps_wait.display();
					ps_file ps(name);
					ps.init(minx,((maxx-minx)>(maxy-miny))?maxx:maxy,miny);
					det_draw(ps,f,ArbG,fs,op_stack,0,z0,k);
					ps_wait.close();
				}
			}
			w2ps.close();
			wp.display();
		}
	}
	wp.close();
	w.close();
}


void AA::det_range(array2<double>& f,GRAPH<int,int>& ArbG,array2<double>& fs,array<int>& op_stack,int i,node v,int k)
{
  int j,m=f.low1(),n=f.high1();
  if(i>=k)
    {
      double x,y,xn,yn;
      for(j=m;j<=n;j++)
	{
	  if(f(j,9)==1.0)
	    {
	      // 	x=fs(k,0)*f(j,6)+fs(k,1)*f(j,7)+fs(k,4);
	      //       	y=fs(k,2)*f(j,6)+fs(k,3)*f(j,7)+fs(k,5);
	      x=f(j,6); y=f(j,7);
	      for(int t=k;t>0;t--)
		{
		  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
		  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
		  x=xn; y=yn;
		}
	      minx=(minx<x)?minx:x;
	      miny=(miny<y)?miny:y;
	      maxx=(maxx>x)?maxx:x;
	      maxy=(maxy>y)?maxy:y;
	    }
	}
      
    }
  else
    {
      edge e;
      int i1=i+1;
      forall_out_edges(e,v)
	{
	  j=ArbG.inf(e);
	  op_stack[i]=j;
	  det_range(f,ArbG,fs,op_stack,i1,ArbG.target(e),k);
	}
    }
}

void AA::det_draw(window& w,array2<double>& f,GRAPH<int,int>& ArbG,array2<double>& fs,array<int>& op_stack,int i,node v,int k)
{
  int j,m=f.low1(),n=f.high1();
  if(i>=k)
    {
      list<point> lp;
      double x,y,xn,yn;
      double 
	h=w.ymax()-w.ymin(),
	b=w.xmax()-w.xmin(),
	maxx=w.xmax()-b/11,
	maxy=w.ymax()-h/11,
	minx=w.xmin()+b/11,
	miny=w.ymin()+h/11;
      x=maxx;
      y=maxy;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn;y=yn;
	}
      lp.append(punkt(x,y));
      x=maxx;
      y=miny;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn; y=yn;
	}
      lp.append(punkt(x,y));
      x=minx;
      y=maxy;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn; y=yn;
	}
      lp.append(punkt(x,y));
      x=minx;
      y=miny;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn;y=yn;
	}
      lp.append(punkt(x,y));
      w.draw_filled_polygon(CONVEX_HULL(lp),black);
      while(!lp.empty())
	{
	  point p=lp.pop();
	  w.draw_pixel(p,black);
	}
    }
  else
    {
      int i1=i+1;
      edge e;
      forall_out_edges(e,v)
	{
	  j=ArbG.inf(e);
	  op_stack[i]=j;
	  det_draw(w,f,ArbG,fs,op_stack,i1,ArbG.target(e),k);
	}
    }
}

void AA::det_draw(ps_file& w,array2<double>& f,GRAPH<int,int>& ArbG,array2<double>& fs,array<int>& op_stack,int i,node v,int k)
{
  int j,m=f.low1(),n=f.high1();
  if(i>=k)
    {
      list<point> lp;
      double x,y,xn,yn;
      double 
	h=w.ymax()-w.ymin(),
	b=w.xmax()-w.xmin(),
	maxx=w.xmax()-b/11,
	maxy=w.ymax()-h/11,
	minx=w.xmin()+b/11,
	miny=w.ymin()+h/11;
      x=maxx;
      y=maxy;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn;y=yn;
	}
      lp.append(punkt(x,y));
      x=maxx;
      y=miny;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn; y=yn;
	}
      lp.append(punkt(x,y));
      x=minx;
      y=maxy;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn; y=yn;
	}
      lp.append(punkt(x,y));
      x=minx;
      y=miny;
      for(int t=k;t>0;t--)
	{
	  xn=f(op_stack[t-1],0)*x+f(op_stack[t-1],1)*y+f(op_stack[t-1],4);
	  yn=f(op_stack[t-1],2)*x+f(op_stack[t-1],3)*y+f(op_stack[t-1],5);
	  x=xn;y=yn;
	}
      lp.append(punkt(x,y));
      w.draw_filled_polygon(CONVEX_HULL(lp),black);
      while(!lp.empty())
	{
	  point p=lp.pop();
	  w.draw_pixel(p,black);
	}
    }
  else
    {
      int i1=i+1;
      edge e;
      forall_out_edges(e,v)
	{
	  j=ArbG.inf(e);
	  op_stack[i]=j;
	  det_draw(w,f,ArbG,fs,op_stack,i1,ArbG.target(e),k);
	}
    }
}


void AA::prob(array2<double>& f, GRAPH<int,int>& ArbG, int k, double p)
{
  	GRAPH<int,int> RevG=ArbG;
	int i,j;
	edge e;
	array2<double> fnew=f;

	printf("\nsuche Komponenten");
	make_strong_connected(RevG,f,fnew,p);
	printf("\nstark zusammenhaengend");
	RevG.rev_all_edges();
	edge_array<double> edge_prob(RevG);
	forall_edges(e,RevG) 
		edge_prob[e]=fnew(RevG.inf(e),8)+0.01;
	
	maxx=f(f.low1(),6);
	maxy=f(f.low1(),7);
	minx=f(f.low1(),6);
	miny=f(f.low1(),7);

	float t0,t1,t2,t3,b,h;

	panel range("Berechne Bereich");
	range.button("Bitte Warten,Berechne Bereich");
	range.display();
	t0=used_time();

	prob_range(fnew,RevG,edge_prob,k);

	t1=used_time();
	range.close();

	if ((minx==maxx) && (miny==maxy)) maxx=minx+1;
	b=maxx-minx;
	h=maxy-miny;
	minx-=b*0.1;
	miny-=h*0.1;
	maxx+=b*0.1;
	maxy+=h*0.1;
	b*=1.2;
	h*=1.2;
	if(b>h) 
	{
		h*=size/b;
		b=size;
	}
	else
	{
		b*=size/h;
		h=size;
	}

	printf("\n Range:   (%.3f,%.3f) zu (%.3f,%.3f)",minx,miny,maxx,maxy);
	window w((int)b,(int)h,"Probabilistischer "+aa_text);
	w.set_redraw(AA::PAINT);
	w.set_flush(true);
	w.init(minx,maxx,miny);
	printf("\n Fenster: (%.3f,%.3f) zu (%.3f,%.3f) mit %.3f\n",w.xmin(),w.ymin(),w.xmax(),w.ymax(),w.scale());
	w.display();

	t2=used_time();

	prob_draw(w,fnew,RevG,edge_prob,k);
	pix=w.get_window_pixrect();
	
	t3=used_time();

	printf("%.2f und %.2f Sekunden.\n",t1-t0,t3-t2);

	panel wp("Fertig");
	int wok=wp.button("Fertig");
	int wsave=wp.button("Speichern");
	wp.display();
	int wch=-1;
	while (wch!=wok)
	{
		wch=wp.read();
		if (wch==wsave)
		{
			wp.close();
			string name;
			panel w2ps("Speichern");
			w2ps.string_item("Dateiname",name);
			int ps_ok=w2ps.button("Speichern");
			int ps_no=w2ps.button("Abbrechen");
			int ps_ch=-1;
			w2ps.display();
			while ((ps_ch!=ps_ok)&&(ps_ch!=ps_no))
			{
				ps_ch=w2ps.read();
				if (ps_ch==ps_ok) 
				{
					panel ps_wait("Bitte warten");
					ps_wait.button("Bitte warten");
					ps_wait.display();
					ps_file ps(name);
					ps.init(minx,maxx,miny);
					prob_draw(ps,fnew,RevG,edge_prob,k);
					ps_wait.close();
				}
			}
			w2ps.close();
			wp.display();
		}
	}
	wp.close();
	w.close();
}

void AA::prob_range(array2<double>& f, GRAPH<int,int>& ArbG,edge_array<double>& edge_prob,int k)
{
	node_array<double> sum_of_prob(ArbG);
	double x,y,x1,y1,p;
	int i;
	node v,z0;
	edge e,e1;
	random_source S;

	forall_nodes(v,ArbG)
	{
		sum_of_prob[v]=0.0;
		if(ArbG.inf(v)==0) z0=v;
		forall_out_edges(e,v)
		{
			sum_of_prob[v]+=edge_prob[e];
		}
	}
	v=z0;
	x=f(f.low1(),6);
	y=f(f.low1(),7);
	minx=x;maxx=x;
	miny=y;maxy=y;

	while(k>0)
	{
		S>>p;
		p*=sum_of_prob[v];
		forall_out_edges(e,v)
		{
			if(p>0.0) e1=e;
			p-=edge_prob[e];
		}
		v=ArbG.target(e1);
		i=ArbG.inf(e1);
		x1=(f(i,0)*x)+(f(i,1)*y)+f(i,4);
		y1=(f(i,2)*x)+(f(i,3)*y)+f(i,5);
		x=x1;
		y=y1;

		if(v==z0)
		{
			minx=(minx<x)?minx:x;
			miny=(miny<y)?miny:y;
			maxx=(maxx>x)?maxx:x;
			maxy=(maxy>y)?maxy:y;
			k--;
		}
	}
	
}

void AA::prob_draw(window& w, array2<double>& f, GRAPH<int,int>& ArbG, edge_array<double>& edge_prob, int k)
{
	node_array<double> sum_of_prob(ArbG);
	double x,y,x1,y1,p;
	int i;
	node v,z0;
	edge e,e1;
	random_source S;

	forall_nodes(v,ArbG)
	{
		sum_of_prob[v]=0.0;
		if(ArbG.inf(v)==0) z0=v;
		forall_out_edges(e,v)
		{
			sum_of_prob[v]+=edge_prob[e];
		}
	}
	v=z0;
	x=f(f.low1(),6);
	y=f(f.low1(),7);

	while(k>0)
	{
		S>>p;
		p*=sum_of_prob[v];
		forall_out_edges(e,v)
		{
			if(p>0.0) e1=e;
			p-=edge_prob[e];
		}
		v=ArbG.target(e1);
		i=ArbG.inf(e1);
		
		x1=(f(i,0)*x)+(f(i,1)*y)+f(i,4);
		y1=(f(i,2)*x)+(f(i,3)*y)+f(i,5);
		x=x1;
		y=y1;

		if(v==z0)
		{
			w.draw_pix(x,y,black);
			k--;
		}
	}
}

void AA::prob_draw(ps_file& w, array2<double>& f, GRAPH<int,int>& ArbG, edge_array<double>& edge_prob, int k)
{
	node_array<double> sum_of_prob(ArbG);
	double x,y,x1,y1,p;
	int i;
	node v,z0;
	edge e,e1;
	random_source S;

	forall_nodes(v,ArbG)
	{
		sum_of_prob[v]=0.0;
		if(ArbG.inf(v)==0) z0=v;
		forall_out_edges(e,v)
		{
			sum_of_prob[v]+=edge_prob[e];
		}
	}
	v=z0;
	x=f(f.low1(),6);
	y=f(f.low1(),7);

	while(k>0)
	{
		S>>p;
		p*=sum_of_prob[v];
		forall_out_edges(e,v)
		{
			if(p>0.0) e1=e;
			p-=edge_prob[e];
		}
		v=ArbG.target(e1);
		i=ArbG.inf(e1);
		
		x1=(f(i,0)*x)+(f(i,1)*y)+f(i,4);
		y1=(f(i,2)*x)+(f(i,3)*y)+f(i,5);
		x=x1;
		y=y1;

		if(v==z0)
		{
			w.draw_pixel(x,y,black);
			k--;
		}
	}
}

void AA::PAINT(window* win){win->put_pixrect(AA::pix);}

void AA::new_edge(GraphWin& grw,edge e)
{
	string s;
	point x=grw.get_target_anchor(e);
	panel p;
	p.string_item("Funktionen:",s);
	int ok=p.button("OK");
	int p1 = (int) x.xcoord();
	int p2 = (int) x.ycoord();
	p.display(p1,p2,grw.get_window());
	while(p.read()!=ok);
	p.close();
	grw.set_data(e,s);
	grw.update_graph();
}

void AA::new_node(GraphWin& grw,node v)
{
	string index="";
	string number="0123456789";
	int i=grw.get_index(v);
	while(i>-1)
	{
		index=number(i%10,i%10).cstring()+index;
		i/=10;
		if(i==0)i--;
	}
	grw.set_data(v,index);
	grw.update_graph();
}

void AA::fsave(array2<double>& f)
{
	string name;
	list<string> flist=get_files(get_directory(),"*.fs");
	panel save("Speichern");
	save.string_item("Dateiname",name,flist);
	int f_save=save.button("Speichern");
	int fs_no=save.button("Abbrechen");
	int fs_ch=-1;
	save.display();
	while((fs_ch!=fs_no)&&(fs_ch!=f_save))
	{
		fs_ch=save.read();
		if ((fs_ch==f_save)&&(!is_directory(name)))
		{
			array<double> sf(10);
			int m,n,i,j;
			file_ostream O(name);
			m=0;
			n=f.high1();
			for(i=f.low1();i<=n;i++)
				if(f(i,9)==1.0) m++;
			O<<m;
			for (i=f.low1();i<=n;i++)
			{
				if(f(i,9)==1.0)
				{
					for(j=0;j<10;j++)
					{
						sf[j]=f(i,j);
					}
					O<<sf;
				}
			}
		}
	}
	save.close();
}

void AA::fload(array2<double>& f)
{
  string name;
  array<double> sf(10);
  list<string> flist=get_files(get_directory(),"*.fs");
  panel load("Laden");
  load.string_item("Dateiname",name,flist);
  int f_load=load.button("Laden");
  int fl_no=load.button("Abbrechen");
  int fl_ch=-1;
  load.display();
  while((fl_ch!=fl_no)&&(fl_ch!=f_load))
    {
      fl_ch=load.read();
      if (fl_ch==f_load)
	{
	  int m,n,i,j;
	  file_istream I(name);
	  I>>n;
	  for (i=f.low1(),m=0;m<=n,i<=f.high1();i++)
	    {
	      if(f(i,9)==1.0)
		{
//		  I>>sf;
		  for(j=0;j<9;j++)
		    {
		      I>>sf[j];
		      f(i,j)=sf[j];
		    }
		  I>>sf[9];
		  m++;
		}
	    }
	}
    }
  load.close();
}

void AA::make_strong_connected(GRAPH<int,int>& ArbG,const array2<double>& f, array2<double>& fnew, double p)
{
	node_array<bool> reached(ArbG);
	node_array<int> compnum(ArbG);
	node_array<edge> pred(ArbG);
	queue<node> scc_q;
	edge e,e1;
	node v,w;

	int c,i,j,k=ArbG.number_of_nodes();
	int final_scc_counter=0;
	int m=f.low1(),n=f.high1();

	c=STRONG_COMPONENTS(ArbG,compnum);

	array<bool> final_scc(c);
	for(i=0;i<c;i++) final_scc[i]=true;
	array<node> scc_member_node(c);
	printf("\nSCC-Felder angelegt");

	forall_nodes(v,ArbG)
	{
		i=compnum[v];
		if(ArbG.inf(v)==0)
		{
			final_scc[i]=false;
			z0=v;
		}
		scc_member_node[i]=v;
		forall_out_edges(e,v)
		{
			if(i!=compnum[ArbG.target(e)]) final_scc[i]=false;
		}
	}

	forall_nodes(v,ArbG) reached[v]=false;
	DFS(ArbG,z0,reached);
	forall_nodes(v,ArbG) 
	{
		if(!reached[v]) 
			final_scc[compnum[v]]=false;
	}

	for(i=0;i<c;i++) 
	{
		if(final_scc[i]) final_scc_counter++;
	}

	array2<double> f1(m,n+final_scc_counter,0,9);
	for(i=m;i<=n;i++)
	{
		for(j=0;j<10;j++) 
			f1(i,j)=f(i,j);
	}
	k=n;

	forall_nodes(v,ArbG) reached[v]=false;
	
	printf("\nBearbeite Final-SCCs");

	for(i=0;i<c;i++)
	{
		if(final_scc[i])
		{ 
			k++;
			scc_q.clear();
			scc_q.append(scc_member_node[i]);
			while(!scc_q.empty()&&(!reached[scc_member_node[i]]))
			{
				v=scc_q.pop();
				forall_out_edges(e,v)
				{
					w=ArbG.target(e);
					if(!reached[w])
					{
						scc_q.append(w);
						reached[w]=true;
						pred[w]=e;
					}
				}
			}
			printf("\nPfad gefunden");
			array<double> psi(6);
			for(j=1;j<9;j++)
			{
				f1(k,j)=0.0;
			}
			f1(k,0)=1.0;
			f1(k,3)=1.0;
			f1(k,9)=1.0;

			w=z0;
			v=scc_member_node[i];
			while(w!=scc_member_node[i])
			{
				w=ArbG.source(pred[v]);
				j=ArbG.inf(pred[v]);
				printf("\n Kante (%d,%d)=%d",ArbG.inf(w),ArbG.inf(v),j);
				v=w;
				psi[0]=(f1(k,0)*f(j,0))+(f1(k,1)*f(j,2));
				psi[1]=(f1(k,0)*f(j,1))+(f1(k,1)*f(j,3));
				psi[2]=(f1(k,2)*f(j,0))+(f1(k,3)*f(j,2));
				psi[3]=(f1(k,2)*f(j,1))+(f1(k,3)*f(j,3));
				psi[4]=(f1(k,0)*f(j,4))+(f1(k,1)*f(j,5))+f1(k,4);
				psi[5]=(f1(k,2)*f(j,4))+(f1(k,3)*f(j,5))+f1(k,5);
				for(j=0;j<6;j++) 
					f1(k,j)=psi[j];
			}
			psi[0]=((f1(k,0)-1)*(f1(k,3)-1))-(f1(k,1)*f1(k,2));
			if(psi[0]!=0.0)
			{
				f1(k,6)=((f1(k,4)*(1-f1(k,3)))+(f1(k,1)*f1(k,5)))/psi[0];
				f1(k,7)=((f1(k,5)*(1-f1(k,0)))+(f1(k,2)*f1(k,4)))/psi[0];
			}
			for(j=0;j<=3;j++) f1(k,j)=0;
			f1(k,4)=f1(k,6);
			f1(k,5)=f1(k,7);
			f1(k,8)=p;
			printf("\nNeue Fkt. %d",k);
			ArbG.new_edge(v,z0,k);
			final_scc[i]=false;
		}
	}
	fnew=f1;
}

void AA::Non_Det(GraphWin& gw)
{
	GRAPH<int,int> ArbG;
	graph& G=gw.get_graph();
	int i,j;
	string s;
	node v,z0;
	node_array<node> copy(G);
	edge e,f;
	list<node> non_det;
	list<node> terminal;
	list<node> non_reach;
	forall_nodes(v,G)
	{
		if(G.outdeg(v)==0) terminal.append(v);
		copy[v]=ArbG.new_node(atoi(gw.get_data(v)));
	}
	
	forall_edges(e,G)
	{
		s=gw.get_data(e)+",";
		i=0;j=0;
		while (j>-1)
		{
			j=s.pos(",",i);
			if (j>i)
			{
				ArbG.new_edge(copy[G.source(e)],copy[G.target(e)],atoi(s(i,j-1)));
				i=j+1;
			}
		}
	}

	node_array<node> rcopy(ArbG);
	forall_nodes(v,G) rcopy[copy[v]]=v;

	forall_nodes(v,ArbG)
	{
		if (ArbG.inf(v)==0) z0=v;
		forall_out_edges(e,v)
		{
			forall_out_edges(f,v)
			{
				if((e!=f)&&(ArbG.inf(e)==ArbG.inf(f))) 
				{
					non_det.append(rcopy[v]);	
				}
			}
		}
	}
	node_array<bool> reached(ArbG);
	forall_nodes(v,ArbG) reached[v]=false;
	DFS(ArbG,z0,reached);
	forall_nodes(v,ArbG) if(!reached[v]) non_reach.append(rcopy[v]);

	gw.set_color(G.all_nodes(),yellow);
	gw.set_color(non_reach,black);
	gw.set_color(non_det,red);
	gw.set_color(terminal,blue);
	//	gw.del_messages();
	s="";
	if(!non_det.empty()) s=s+"Rot=nichtdeterministisch ";
	if(!terminal.empty())s=s+"Blau=keine Out-Kanten ";
	if(!non_reach.empty()) s=s+"Schwarz=nicht erreichbare Knoten";
	gw.message(s);
	gw.update_graph();
}

bool AA::proof(GRAPH<int,string>& ZeigG)
{
	bool t=false,t1;
	string s,c="0123456789,";
	int i,j;
	edge e;
	node v;
	forall_nodes(v,ZeigG) t=t||(ZeigG.inf(v)==0);
	if(t)
	forall_edges(e,ZeigG)
	{
		if(t)
		{
			s=ZeigG.inf(e);
			for(i=0;i<s.length();i++)
			{
				t1=false;
				for(j=0;j<11;j++) t1=t1||(c(j,j)==s(i,i));
				t=t&&t1;		
			}
		}
	}
	return(t);
}