import math;

///////////////////////////////////////////////////////////////////////////////////////////////////
//This is the main routine.
//
//trans_probs is a square matrix (double array) of transition probabilities, given as strings
//It is important: they should not be labels
//Using the string "" will make an arrow without label
//Using the string "$0$" will NOT make an arrow
//
//vertices_names is an array of strings, with the names that should go inside the little circles
//If it is omitted, we will go for 1, 2, 3...
//
//v is an array of pairs, indicating the position of the vertices
//If it is omitted, we will choose the vertices of a regular polygon of the appropriate size
//In order for the vertices labels to match the size of the circle, the whole figure diameter
//is expected to be around 2, so rescale your graph appropriately.
//
//label_percent dictates the position on the edge where to put the label
//By default this is 0.48
//It can be changed to adjust the figure, since the control that labels do not intersect other
//labels or edges is not working very well
///////////////////////////////////////////////////////////////////////////////////////////////////
void markov(string[][] trans_probs, string vertices_names[] = new string[], pair v[] = new pair[], real label_percent = 0.48)
{

///////////////////////////////////////////////////////////////////////////////////////////////////
//Constants and new types declaration

	int dimension = trans_probs.length; //The dimension of the transition matrix
	real circle_radius = 0.08; //The dimension of the little circles at the vertices
	real ball_radius = 0.06; //The radius of a imaginary white space containing the transition probabilities
	real arrow_displace = 0.1; //How far to displace incoming and exiting arrows
	real delta = 0.7; //Additional displacement for loop arrows
	real epsilon = 0.02; //The size of the blank space where two arrows intersect
	real label_displace = 0.07; //How far to displace the transition probabilities with respect to their respective arcs
	pen prob_pen = fontsize(5); //The pen to write transition probabilities
	arrowbar LittleArrow = Arrow(5); //The arrow at the end of the arcs


	struct segment
	{
		path arc;
		bool final;
	}

	struct prob_label
	{
		Label name;
		pair position;
	}

	path circles[];
	segment drawn_segments[];
	prob_label probabilities[];

///////////////////////////////////////////////////////////////////////////////////////////////////
//Subroutines

	path create_edge(int a, int b)
	{
		real direction;
		if (a != b)
		{
			direction = angle(v[b]-v[a]);
		}
		else
		{
			direction = angle(v[a]) - delta;
		}
		pair start = point(circles[a], 2*direction/pi + arrow_displace);
		if (a != b)
		{
			direction = angle(v[a]-v[b]);
		}
		else
		{
			direction = angle(v[a]) + delta;
		}
		pair end = point(circles[b], 2*direction/pi - arrow_displace);
		pair startdir = start-v[a];
		pair enddir = v[b]-end;
		path lato = start{startdir}..{enddir}end;
		return lato;
	}

	segment[] break_up(segment my_segment)
	{
		path arc = my_segment.arc;
		segment first_half, second_half, return_value[];
		bool meets = false;
		for(int k=0; k < drawn_segments.length; ++k)
		{
			if(intersect(arc, drawn_segments[k].arc).length != 0)
			{
				real meet_time = intersect(arc, drawn_segments[k].arc)[0];
				first_half.arc = subpath(arc, 0, meet_time - epsilon);
				second_half.arc = subpath(arc, meet_time + epsilon, reltime(arc, 1));
				first_half.final = false;
				second_half.final = my_segment.final;
				meets = true;
				break;
			}
		}
		if (meets)
		{
			return_value = break_up(first_half);
			return_value.append(break_up(second_half));
		}
		else
		{
			return_value[0] = my_segment;
		}
		return return_value;
	}

///////////////////////////////////////////////////////////////////////////////////////////////////
//The actual drawing takes place from here on

	bool create_vertices_positions = false;
	bool create_vertices_names = false;

	if(v.length == 0)
	{
		create_vertices_positions = true;
	}
	if(vertices_names.length == 0)
	{
		create_vertices_names = true;
	}


	for(int i=0; i < dimension; ++i)
	{
		if(create_vertices_positions)
		{
			v[i] = point(unitcircle, 4*i/dimension);
		}
		if(create_vertices_names)
		{
			vertices_names[i] = "$" + string(i+1) + "$";
		}
		transform t = shift(v[i])*scale(circle_radius);
		circles[i]= t*unitcircle;
		draw(circles[i]);
		label(vertices_names[i], v[i]);
	}

	for(int i=0; i < dimension; ++i)
	{
		for(int j=0; j < dimension; ++j)
		{
			if(trans_probs[i][j] != "$0$")
			{
				segment edge;
				prob_label prob;
				edge.arc = create_edge(i, j);
				edge.final = true;
				drawn_segments.append(break_up(edge));
				int sign = 1;
				if(i == j)
				{
					sign = -1;
				}
				prob.position = point(edge.arc, label_percent);
				prob.position += label_displace*(rotate(sign*90)*dir(edge.arc, label_percent));
				prob.name = trans_probs[i][j];
//				prob.name = rotate(dir(edge.arc, label_percent))*prob.name; //Adding this line will rotate the probabilities labels
				probabilities.push(prob);
			}
		}
	}

	for(int i=0; i < drawn_segments.length; ++i)
	{
		if(drawn_segments[i].final)
		{
			draw(drawn_segments[i].arc, LittleArrow);
		}
		else
		{
			draw(drawn_segments[i].arc);
		}
	}

	for(int i=0; i < probabilities.length; ++i)
	{
		pair center = probabilities[i].position;
		path ball = shift(center)*scale(ball_radius)*unitcircle;
		for(int j=0; j < drawn_segments.length; ++j)
		{
			if(intersect(ball, drawn_segments[j].arc).length != 0)
			{
				pair displace_direction = center - intersect(ball, drawn_segments[j].arc)[0];
				center += label_displace*displace_direction;
				ball = shift(center)*scale(ball_radius)*unitcircle;
			}
		}
		label(probabilities[i].name, center, prob_pen);
	}

}