/*
NAME
    sample04    - Least Cost Path Algorithm (jjGraph Example)
*/

#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <jj/pattern.h>
#include "sample04.b"

enum Bool {FALSE=0, TRUE=1};

class Edge {
    EXT_Edge
  public:
    int  _cost;
    Edge(int c){_cost = c;}
};

class Node {
    EXT_Node
  public:
    char *_name;
    int	  _least;
    Node *_from;

    Node(char *n){ _name = strdup(n); _least=INT_MAX; _from=NULL;}
};

jjGraph(g, Node, Edge);

void lcp(Node &start){	/* find least cost path */
    g_iterator	i(&start);
    Edge	*e;
    while( (e=++i) ){
	if( g.to(e)->_least > start._least + e->_cost ){
	    g.to(e)->_least = start._least + e->_cost;
	    g.to(e)->_from  = &start;
	    lcp(*g.to(e));
	}
    }
}

void put_lcp(Node &start, Node &end){	/* print-out lcp */
    Node *to	= &end;
    if( &end == &start ){
	printf("%s", start._name);
    }else{
	put_lcp(start, *end._from);
	printf("->%s(%d)", end._name, end._least);
    }
}

int main(){
    Node	A("A"),	B("B"),	C("C"), D("D"), E("E"), F("F"),
		G("G"), H("H"), I("I"), J("J"), K("K"), L("L");
    Edge	ab(3), ba(3),
		ae(9), ea(9),
		ac(2), ca(2),
		bd(2), db(2),
		be(4), eb(4),
		ce(6), ec(6),
		cf(9), fc(9),
		dg(3), gd(3),
		eg(1), ge(1),
		eh(2), he(2),
		fh(1), hf(1),
		fi(2), if_(2),
		gj(5), jg(5),
		hj(5), jh(5),
		hl(9), lh(9),
		hk(6), kh(6),
		ik(2), ki(2),
		jl(5), lj(5),
		kl(3), lk(3);

/* build graph */
    g.add(&A,&ab,&B); g.add(&A,&ae,&E); g.add(&A,&ac,&C);
    g.add(&B,&ba,&A); g.add(&B,&be,&E); g.add(&B,&bd,&D);
    g.add(&C,&ca,&A); g.add(&C,&ce,&E); g.add(&C,&cf,&F);
    g.add(&D,&db,&B); g.add(&D,&dg,&G);
    g.add(&E,&ea,&A); g.add(&E,&eb,&B); g.add(&E,&eg,&G); g.add(&E,&eh,&H);
							  g.add(&E,&ec,&C);
    g.add(&F,&fc,&C); g.add(&F,&fh,&H); g.add(&F,&fi,&I);
    g.add(&G,&gd,&D); g.add(&G,&ge,&E); g.add(&G,&gj,&J);
    g.add(&H,&he,&E); g.add(&H,&hf,&F); g.add(&H,&hj,&J); g.add(&H,&hl,&L);
							  g.add(&H,&hk,&K);
    g.add(&I,&if_,&F);g.add(&I,&ik,&K);
    g.add(&J,&jg,&G); g.add(&J,&jh,&H); g.add(&J,&jl,&L);
    g.add(&K,&ki,&I); g.add(&K,&kh,&H); g.add(&K,&kl,&L);
    g.add(&L,&lj,&J); g.add(&L,&lh,&H); g.add(&L,&lk,&K);

/* find lcp */
    A._least = 0;
    lcp(A);
    put_lcp(A,L);
}

/* pattern implementation */
g_class		g;