%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Metagraph package
% $Id: metagraph.mp,v 1.4 2004/09/07 19:40:23 babenko Exp $

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Drawing parameters

numeric circle_vertex_radius;
circle_vertex_radius := 0.25cm;

numeric square_vertex_radius;
square_vertex_radius := 0.2cm;

numeric rhombus_vertex_radius;
rhombus_vertex_radius := 0.27cm;

numeric small_label_offset_delta;
small_label_offset_delta = 3bp;

numeric label_shade_offset_delta;
label_shade_offset_delta = 2bp;

numeric default_edge_shift;
default_edge_shift = 2pt;

numeric small_vertex_coeff;
small_vertex_scale := 0.5;

numeric vertex_mark_scale;
vertex_mark_scale := 0.6;

numeric edge_cutoff_coeff;
edge_cutoff_coeff := 0.7;

pair subscript_label_shift;
subscript_label_shift = (0,-1pt);

pen vertex_pen;
vertex_pen := pencircle scaled 0.9pt;

pen edge_pen;
edge_pen := pencircle scaled 0.6pt;

pen bold_edge_pen;
bold_edge_pen := pencircle scaled 1.7pt;

pen grayed_edge_pen;
grayed_edge_pen := pencircle scaled 4pt;

pen edge_box_pen;
edge_box_pen := pencircle scaled 0.7pt;

color grayed_edge_color;
grayed_edge_color := 0.7white;

color grayed_vertex_color;
grayed_vertex_color := 0.8white;

color label_shade_color;
label_shade_color := 0.8white;

pair label_shade_gap;
label_shade_gap = (5pt, 2.5pt);

pair label_autoshift_gap;
label_autoshift_gap = (5pt, 2.5pt);

color normal_vertex_color;
normal_vertex_color := background;

color vertex_mark_color;
vertex_mark_color = black;

string default_vertex_style;
default_vertex_style := "circle";

ahlength := 7bp;
ahangle := 25;
linecap := rounded;
defaultfont := "larm1200";

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Debugging

boolean draw_label_pos;
draw_label_pos := false;

boolean draw_label_shade;
draw_label_shade := false;

boolean draw_label_tan_pos;
draw_label_tan_pos := false;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Common definitions

def circle(expr center, r) =
   (center + (r, 0) {up} ..
    center + (0, r) ..
    center + (-r, 0) ..
    center + (0, -r) .. cycle)
enddef;

def square(expr center, r) =
   ((center + (-r, -r)) --
    (center + (-r,  r)) --
    (center + ( r,  r)) --
    (center + ( r, -r)) -- cycle)
enddef;

def rhombus(expr center, r) =
   ((center + ( 0, -r)) --
    (center + ( r,  0)) --
    (center + ( 0,  r)) --
    (center + (-r,  0)) -- cycle)
enddef;

def shade_by_box(expr box, gap) =
    fullcircle
    xscaled (xpart (lrcorner box) - xpart (llcorner box) + xpart gap)
    yscaled (ypart (ulcorner box) - ypart (llcorner box) + ypart gap)
    shifted (center box)
enddef;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Labels

boolean this_has_label;
boolean this_label_boxed;
boolean this_label_shaded;
picture this_label;
numeric this_label_angle;
numeric this_label_offset_delta;
pair this_label_shift;

def begin_graph_label =
    this_has_label := false;
    this_label_boxed := false;
    this_label_shaded := false;
    this_label_angle := 0;
    this_label_offset_delta := 0;
    this_label_shift := (0,0);
enddef;

def end_graph_label(expr at) =
    if this_has_label:
        save box;
        path box;
        box := bbox this_label;
        
        save t;
        transform t;
        t = identity rotated this_label_angle shifted at shifted this_label_shift;
        
        if this_label_boxed:
            unfill box transformed t;
            pickup edge_box_pen;
            draw box transformed t;
        fi

        if this_label_shaded:
            fill shade_by_box(box, label_shade_gap) transformed t withcolor label_shade_color;
        fi
        
        draw this_label transformed t;
    fi
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
vardef graph_label@#(text l) =
    this_has_label := true;
    begingroup
        interim labeloffset := labeloffset + this_label_offset_delta;
        this_label := thelabel@#(l, origin) scaled defaultscale;
    endgroup    
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def graph_label_shift(expr s) =
    this_label_shift := s;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def graph_label_boxed =
    this_label_boxed := true;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def graph_label_offset(expr o) =
    this_label_offset_delta := this_label_offset_delta + o;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def graph_label_shaded =
    this_label_shaded := true;
    graph_label_offset(label_shade_offset_delta);
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def graph_label_angle(expr a) =
    this_label_angle := a;
enddef;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Vertices

pair this_vertex;
string this_vertex_style;
color this_vertex_color;
boolean this_vertex_marked;

def vertex_outline(expr style) =
    % normal vertex styles
    if style = "circle":
        circle(origin, circle_vertex_radius)
    elseif style = "square":
        square(origin, square_vertex_radius)
    elseif style = "rhombus":
        rhombus(origin, rhombus_vertex_radius)    
        
    % small vertex styles
    elseif style = "small_circle":
        circle(origin, circle_vertex_radius * small_vertex_scale)
    elseif style = "small_square":
        square(origin, square_vertex_radius * small_vertex_scale)
    elseif style = "small_rhombus":
        rhombus(origin, rhombus_vertex_radius * small_vertex_scale)
    fi
enddef;

def set_vertex_style_options(expr style) =
    if (style = "small_circle") or
       (style = "small_square") or
       (style = "small_rhombus"):
        graph_label_offset(small_label_offset_delta);
    fi
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def vertex_fill(expr c) =
    this_vertex_color := c;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def vertex_grayed =
    vertex_fill(grayed_vertex_color);
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def vertex_marked =
    this_vertex_marked := true;
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def draw_vertex(text name)(text body) =
    this_vertex := name;
    this_vertex_style := name.style;
    this_vertex_color := normal_vertex_color;
    this_vertex_marked := false;
    
    begingroup
        save label_angle;
        numeric label_angle;
        label_angle := 0;
        
        begin_graph_label;
        set_vertex_style_options(this_vertex_style);
        
        body;
        
        fill vertex_outline(this_vertex_style) shifted this_vertex withcolor this_vertex_color;
        pickup vertex_pen;
        draw vertex_outline(this_vertex_style) shifted this_vertex;
        

        if this_vertex_marked:
            fill vertex_outline(this_vertex_style) scaled vertex_mark_scale shifted this_vertex withcolor vertex_mark_color;
        fi

        end_graph_label(this_vertex);
    endgroup;
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def declare_vertex(suffix name)(expr x, y) =
    declare_vertex_with_style(name)(x, y, default_vertex_style);
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def declare_vertex_with_style(suffix name)(expr x, y, s) =
    pair name;
    name = (x, y);
    
    string name.style;
    path name.outline;
    
    name.style := s;
    name.outline := vertex_outline(s) shifted name;
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
vardef declare_vertices(text name) =
    pair name;
    string name.style;
    path name.outline;
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def create_vertex_with_style(suffix name)(expr x, y, s) =
    name := (x, y);
    name style := s;
    name outline := vertex_outline(s) shifted name;
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def create_vertex(suffix name)(expr x, y) =
    create_vertex_with_style(name)(x, y, default_vertex_style);
enddef;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Edges and arcs

def cutoff_start(expr p, eps) =
    begingroup
        save s, i;
        pair s, i;
        s := point 0 of p;
        i := p intersectiontimes (fullcircle scaled eps shifted s);
        subpath (xpart i, length p) of p
    endgroup
enddef;

def cutoff_end(expr p, eps) =
    reverse cutoff_start(reverse p, eps)
enddef;

def pen_diam(expr p) =
    begingroup
        save pp;
        path pp;
        pp:= makepath p;
        max(xpart lrcorner pp - xpart llcorner pp, ypart ulcorner pp - ypart llcorner pp)
    endgroup    
enddef;

def the_edge(expr aout, bout, p) =
    (p cutbefore aout) cutafter bout
enddef;

pair this_edge_start, this_edge_end;
path this_edge_start_outline, this_edge_end_outline;

boolean this_edge_is_arc;
boolean this_edge_is_bidir_arc;
boolean this_edge_is_grayed;

boolean this_edge_has_dash;
picture this_edge_dash;

pen this_edge_pen;

path this_edge_path;
numeric this_edge_label_pos;
numeric this_edge_shift;

boolean this_edge_label_has_align;
path this_edge_label_align;

boolean this_edge_label_has_autoshift;
boolean this_edge_label_has_inverse_autoshift;
boolean this_edge_label_has_inverse_autoangle;

def path_shift(expr p, s) =
    begingroup
        save a, b, dir;
        
        pair a, b;
        a := point 0 of p;
        b := point infinity of p;
        
        pair dir;
        if a <> b:
            dir := ((unitvector (b - a)) rotated 90);
        else:
            % no shift for loops
            dir := (0, 0);
        fi;                

        (s * dir)
    endgroup
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_dash(expr d) =
    this_edge_has_dash := true;            
    this_edge_dash := d;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_grayed =
    this_edge_is_grayed := true;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_bold =
    this_edge_pen := bold_edge_pen;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_path(expr p) =
    this_edge_path := p;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_pos(expr coeff) =
    this_edge_label_pos := coeff;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_align(expr p) =
    this_edge_label_has_align := true;
    this_edge_label_align := p;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_xalign(expr x) =
    edge_label_align((x, -infinity) -- (x, +infinity));
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_xalign_center =
    edge_label_xalign((xpart this_edge_start + xpart this_edge_end) / 2);
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_yalign_center =
    edge_label_yalign((ypart this_edge_start + ypart this_edge_end) / 2);
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_yalign(expr y) =
    edge_label_align((-infinity, y) -- (+infinity, y));
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_shift(expr s) =
    this_edge_shift := s
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_autoshift =
    this_edge_label_has_autoshift := true;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_inverse_autoshift =
    this_edge_label_has_inverse_autoshift := true;
    this_edge_label_has_autoshift := true;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_shift_plus =
    edge_shift(+default_edge_shift);
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_shift_minus =
    edge_shift(-default_edge_shift);
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_autoangle =
    if this_edge_label_has_inverse_autoangle:
        graph_label_angle(-edge_angle);
    else:
        graph_label_angle(+edge_angle);
    fi        
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_label_inverse_autoangle =
    this_edge_label_has_inverse_autoangle := true;
    edge_label_autoangle;
enddef;

%%%%%%%%%%%% User attribute %%%%%%%%%%%%
def edge_autolabel(expr autoshift, autoangle)(text l) =
    if autoshift:
        edge_label_autoshift;
    fi
    if autoangle:
        edge_label_autoangle;
    fi
    graph_label(l);
enddef;
            
def begin_edge(suffix a, b) =
    this_edge_start := a;
    this_edge_start_outline := a.outline;
    
    this_edge_end := b;
    this_edge_end_outline := b.outline;
    
    this_edge_is_arc := false;
    this_edge_is_bidir_arc := false;
    this_edge_has_dash := false;
    this_edge_is_grayed := false;
    this_edge_path := a -- b;
    this_edge_pen := edge_pen;
    this_edge_shift := 0;
    this_edge_label_has_align := false;
    this_edge_label_pos := 0.5;
    this_edge_label_has_autoshift := false;
    this_edge_label_has_inverse_autoshift := false;
    this_edge_label_has_inverse_autoangle := false;
    
    if a <> b:
        edge_angle := angle (direction 0 of this_edge_path);
        if abs edge_angle > 90:
            edge_angle := edge_angle + 180;
        fi
    fi

    begin_graph_label;
enddef;

def end_edge =
    begingroup
        save shift;
        pair shift;
        shift := path_shift(this_edge_path, this_edge_shift);
        
        save shifted_path;
        path shifted_path;
        shifted_path := this_edge_path shifted shift;

        save cut_path;
        path cut_path;
        
        % first cut the path off according to the outlines of the veritces
        cut_path := the_edge(this_edge_start_outline, this_edge_end_outline, shifted_path);

        % now make a small correction based on edge parameters
        save cutoff_eps;
        numeric cutoff_eps;
        cutoff_eps := edge_cutoff_coeff * pen_diam(vertex_pen) + pen_diam(this_edge_pen);
        if this_edge_is_arc:
            cut_path := cutoff_end(cut_path, cutoff_eps);
        fi
        if this_edge_is_bidir_arc:
            cut_path := cutoff_start(cut_path, cutoff_eps);
        fi        

        if this_edge_is_grayed:
            pickup grayed_edge_pen;
            
            draw cut_path withcolor grayed_edge_color;

            if this_edge_is_arc:
                filldraw arrowhead(cut_path) withcolor grayed_edge_color;
            fi
             
            if this_edge_is_bidir_arc:
                filldraw arrowhead(reverse cut_path) withcolor grayed_edge_color;
            fi
        fi;
            
        pickup this_edge_pen;
        if this_edge_has_dash:
            draw cut_path dashed this_edge_dash;
        else:    
            draw cut_path;
        fi
        
        if this_edge_is_arc:
            filldraw arrowhead(cut_path);
        fi
        
        if this_edge_is_bidir_arc:
            filldraw arrowhead(reverse cut_path);
        fi

        if this_has_label:
            save label_time;
            numeric label_time;
            label_time := arctime (this_edge_label_pos * arclength shifted_path) of shifted_path;
            
            save label_pos;
            pair label_pos;
            label_pos := point label_time of shifted_path;
            
            save label_shade;
            path label_shade;
            label_shade := shade_by_box(bbox this_label, label_autoshift_gap) rotated this_label_angle;
            
            if draw_label_shade:
                pickup pencircle scaled 0.7pt;
                draw label_shade shifted label_pos;
            fi    
            
            save label_tan;
            pair label_tan;
            label_tan := direction label_time of shifted_path;
            
            save shade_tan_time;
            numeric shade_tan_time;
            shade_tan_time := directiontime label_tan of label_shade;

            save shade_tan_pos;
            pair shade_tan_pos;
            shade_tan_pos := point shade_tan_time of label_shade;
            if this_edge_label_has_inverse_autoshift:
                shade_tan_pos := -shade_tan_pos;
            fi    

            if draw_label_tan_pos:
                pickup pencircle scaled 2pt;
                drawdot point shade_tan_time of label_shade shifted label_pos;
            fi    
            
            if this_edge_label_has_autoshift:
                graph_label_shift(-shade_tan_pos);                
            fi
            
            if this_edge_label_has_align:
                label_pos := ((shifted_path shifted this_label_shift) intersectionpoint this_edge_label_align) shifted -this_label_shift;
            fi
            
            end_graph_label(label_pos);
            
            if draw_label_pos:
                pickup pencircle scaled 2pt;
                drawdot label_pos shifted this_label_shift;
            fi
        fi
    endgroup        
enddef;

def begin_arc(suffix a, b) =
    begin_edge(a, b)
    this_edge_is_arc := true;
enddef;

let end_arc = end_edge;

def begin_bidir_arc(suffix a, b) =
    begin_edge(a, b)
    this_edge_is_arc := true;
    this_edge_is_bidir_arc := true;
enddef;

let end_bidir_arc = end_edge;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def draw_edge(suffix a, b)(text body) =
    begingroup
        begin_edge(a, b);
        body;
        end_edge;
    endgroup        
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def draw_arc(suffix a, b)(text body) =
    begingroup
        begin_arc(a, b);
        body;
        end_arc;
    endgroup        
enddef;

%%%%%%%%%%%% User instruction %%%%%%%%%%%%
def draw_bidir_arc(suffix a, b)(text body) =
    begingroup
        begin_bidir_arc(a, b);
        body;
        end_bidir_arc;
    endgroup        
enddef;

