lpd algorithm dev

graph.pdf

list.h

/* 
*      This file is part of the tknet project. 
*    which be used under the terms of the GNU General Public 
*    License version 3.0 as published by the Free Software 
*    Foundation and appearing in the file LICENSE.GPL included 
*    in the packaging of this file.  Please review the following 
*    information to ensure the GNU General Public License 
*    version 3.0 requirements will be met: 
* 
*    http://www.gnu.org/copyleft/gpl.html 
* 
*    Copyright  (C)   2012   Zhong Wei <clock126@126.com>  . 
*/ 
#include <stdint.h>

/*
 * a typical doubly-linked list node
 */
struct list_node {
	struct list_node *prev, *next;
};

/*
 * list node constructor (circular list)
 */
#define LIST_NODE_CONS(_ln) \
	(_ln).prev = &(_ln); \
	(_ln).next = &(_ln)

/* 
 * list iterator 
 *
 * One of the reasons that my list iterator is designed this way 
 * is that the advantage to manipulate list as a string (e.g. 
 * insert a string of list between two nodes) instead of just 
 * one node.
 */
struct list_it {
	struct list_node *now, *last;
};

#define LIST_NULL {NULL, NULL}

#define LIST_CONS(_it) \
	(_it).now = NULL; \
	(_it).last = NULL

/*
 * get a iterator pointing to a list node.
 */
static __inline struct list_it
list_get_it(struct list_node *in_node)
{
	struct list_it res;

	if (in_node == NULL)
		res.now = res.last = NULL;
	else {
		res.now = in_node;
		res.last = in_node->prev;
	}

	return res;
}

/*
 * this is the core basic operation of our doubly linked
 * circular list, to fasten and unfasten two strings of 
 * list pointed by two list iterators respectively.
 *
 * After this operation, list node i->now will still point to
 * what it used to point.
 *
 * refer to doc/pics/list_tk.png
 */
static __inline void
list_tk(struct list_it *i0, struct list_it *i1)
{
	if (i0->now == NULL)
		*i0 = *i1;
	else if (i1->now == NULL)
		*i1 = *i0;

	i0->now->prev = i1->last;
	i0->last->next = i1->now;

	i1->now->prev = i0->last;
	i1->last->next = i0->now;

	i0->last = i1->last;
	i1->last = i1->now->prev;
}

/*
 * list_foreach go through a list and call function passed by
 * 'each_do' for each list node, until 'each_do' function return
 * LIST_RET_BREAK.
 *
 * note: 'fwd' is short for 'forward' which points to the next 
 * iteration nodes.
 */
typedef BOOL list_it_fun(struct list_it*, 
		struct list_it*, 
		struct list_it*,
		void*);

#define LIST_RET_BREAK    1
#define LIST_RET_CONTINUE 0

static __inline void
list_foreach(struct list_it *head, list_it_fun *each_do, 
		void *extra) 
{
	struct list_it fwd, now = *head;

	if (head->now == NULL)
		return;

	for(;;) {
		fwd = list_get_it(now.now->next);
		if (LIST_RET_BREAK == 
				each_do(head, &now, &fwd, extra))
			break;

		now = fwd;
	}
}

/*
 * the following functions do what their name tells you.
 * Generally you just pass NULL to the last two arguments,
 * however, you MUST pass 'now' and 'fwd' if you are using
 * them during the list node iteration (called by list_foreach)
 * for safety reason.
 *
 * list_detach_one returns whether the detached node is the last
 * node in list.
 */
static __inline void
list_insert_one_at_tail(struct list_node *node, 
		struct list_it *head, 
		struct list_it *now,
		struct list_it *fwd)
{
	struct list_it tmp = list_get_it(node);
	list_tk(head, &tmp);

	if (now) {
		*now = list_get_it(now->now);
		*fwd = list_get_it(now->now->next);
	}
}

static __inline void
list_insert_one_at_head(struct list_node *node, 
		struct list_it *head, 
		struct list_it *now,
		struct list_it *fwd)
{
	list_insert_one_at_tail(node, head, now, fwd);
	*head = list_get_it(head->last);
}

static __inline BOOL
list_detach_one(struct list_node *node,
		struct list_it *head, 
		struct list_it *now,
		struct list_it *fwd)
{
	struct list_it inow = list_get_it(node);
	struct list_it inew = list_get_it(node->next);

	if (head->now == head->last)
		*head = list_get_it(NULL);
	else {
		list_tk(&inow, &inew);
		
		if (head->now == node) {
			*head = list_get_it(inew.now);
		}
		*head = list_get_it(head->now);
	}

	if (now) {
		if (now->now == node) {
			/* go back one step so that next iterator in
			 * list_foreach will go back to 'inew.now'.*/
			*now = list_get_it(inew.now->prev);
		}
		*now = list_get_it(now->now);
		*fwd = list_get_it(now->now->next);
	}

	if (head->now == NULL)
		return LIST_RET_BREAK;
	else
		return LIST_RET_CONTINUE;
}

/* 
 * these macros help you define a list_foreach callback 
 * function & return the right value if you want to go over 
 * the list.
 */
#define LIST_IT_CALLBK(_fun_name) \
	BOOL _fun_name(struct list_it *pa_head, \
			struct list_it *pa_now, \
			struct list_it *pa_fwd, \
			void *pa_extra)

#define LIST_GO_OVER \
	if (pa_now->now == pa_head->last) \
		return LIST_RET_BREAK; \
	else \
		return LIST_RET_CONTINUE

/*
 * these macros provide common way to access a struct giving
 * its member addresss. Specifically, use LIST_OBJ to get the 
 * list object by passing the member name of a list node.
 */
#define MEMBER_OFFSET(_type, _member) \
	((uintptr_t)&((_type*)0)->_member)

#define MEMBER_2_STRUCT(_member_addr, _type, _member_name) \
	(_member_addr == NULL) ? NULL : \
	(_type*)((uintptr_t)(_member_addr) - MEMBER_OFFSET(_type, _member_name))

#define LIST_OBJ(_type, _name, _list_node_name) \
	_type* _name = MEMBER_2_STRUCT(pa_now->now, _type, _list_node_name)

/*
 * this macro utility helps you with pointer type cast.
 */
#define P_CAST(_to, _type, _from) \
	_type* _to = (_type*)(_from)

/*
 * comparator function, called specifically by list_sort.
 */
typedef BOOL list_cmp_fun(struct list_node *, 
		struct list_node *,
		void *);

struct list_sort_arg {
	list_cmp_fun     *cmp;
	void             *extra;
};

struct __list_sort_tmp_arg { 
	struct list_it   it;
	void             *extra;
};

#define LIST_CMP_CALLBK(_fun_name) \
	BOOL _fun_name(struct list_node *pa_node0, \
			struct list_node *pa_node1, \
			void *pa_extra)
/*
 * list insert is designed as a callback called by list_foreach
 * function, it can also be used by user-end to insert a node into 
 * certain position.
 * see list_sort on how to use.
 */
#define __CMP(_node) \
	(*sort->cmp)(expa->it.now, pa_now->_node, expa->extra)

static __inline LIST_IT_CALLBK(list_insert)
{
	P_CAST(sort, struct list_sort_arg, pa_extra);
	P_CAST(expa, struct __list_sort_tmp_arg, sort->extra);

	if (pa_now->now == pa_head->now) {
		if(__CMP(now)) {
			list_tk(&expa->it, pa_head);
			*pa_head = list_get_it(pa_head->last);
			return LIST_RET_BREAK;
		} else if (!__CMP(last)) {
			list_tk(&expa->it, pa_head);
			return LIST_RET_BREAK;
		}
	} else if (__CMP(now)) {
		list_tk(&expa->it, pa_now);
		return LIST_RET_BREAK;
	} 

	return LIST_RET_CONTINUE;
}

/*
 * list sort
 * struct list_cmp_arg is used as argument list here.
 * where 'cmp' is sorting compare callback;
 * 'extra' is your extra parameters you need to pass to your 
 * compare callback.
 */
static __inline void
list_sort(struct list_it *head, struct list_sort_arg *sort)
{
	struct list_it tmp_hd = {NULL, NULL};
	struct list_node *node;
	struct __list_sort_tmp_arg expa;
	BOOL res = 0;

	expa.extra = sort->extra; /* save */
	sort->extra = &expa;

	while (!res) {
		node = head->now;
		res = list_detach_one(node, head, NULL, NULL);
		expa.it = list_get_it(node);

		if (tmp_hd.now)
			list_foreach(&tmp_hd, &list_insert, sort);
		else
			list_tk(&expa.it, &tmp_hd);
	}

	*head = tmp_hd;
}

/*
 * this macro provides a quick way to define a list-release 
 * function for convenience.
 */
#define LIST_DECL_FREE_FUN(_fun_name) \
	extern void _fun_name(struct list_it *)
	
#define LIST_DEF_FREE_FUN(_fun_name, _type, _member, _free_statm) \
	static LIST_IT_CALLBK(_ ## _fun_name) \
	{ \
		LIST_OBJ(_type, p, _member); \
		BOOL res = list_detach_one(pa_now->now, \
		               pa_head, pa_now, pa_fwd); \
		_free_statm; /* free(p); */ \
		return res; \
	} \
	void _fun_name(struct list_it *head) \
	{ \
		list_foreach(head, &_ ## _fun_name, NULL); \
	} LIST_DECL_FREE_FUN(_fun_name)

lpd.c

#include <stdio.h>
#include <stdlib.h>
#define BOOL uint8_t
#include "list.h"

#define MAX_PATH_LEN 16
#define MAX_MATCHES  256
#define T_MATCHES    uint8_t
#define T_LEN        uint8_t
#define T_ID         uint8_t
#define T_LABEL      uint8_t

#define PATH_ID(_p) \
	(_p->node_id[_p->len - 1])

#define PATH_ARRAY_LEN(_array) \
	(sizeof(_array) / sizeof(struct path))

#define C_RST     "\033[0m"
#define C_GREEN   "\033[42m\033[1;33m"

struct path {
	T_LEN   len;
	T_LABEL label[MAX_PATH_LEN];
	T_ID    node_id[MAX_PATH_LEN];
};

struct path_ref {
	struct list_node ln;
	struct path_ptr *to;
	struct path_ref *from;
};

struct path_ptr {
	struct path     *path;
	struct list_it   refs;
	uint32_t         n_refs;
	struct list_node ln;
};

int debug = 0;

T_ID path_id(struct path *p)
{
	return p->node_id[p->len - 1];
}

void path_print(struct path *p, FILE *fh)
{
	T_LEN i;
	if (p->len == 0)
		return;

	printf("path #%d: ", PATH_ID(p));
	for (i = 0; i < p->len; i++) {
		fprintf(fh, "%d," C_GREEN "%d" C_RST, 
		        p->node_id[i], p->label[i]);
		if (i != p->len - 1)
			fprintf(fh, "--");
	}
}

T_LEN path_merge_pos(struct path *p0, struct path *p1)
{
	T_LEN i;
	for (i = 0; i < p0->len; i++) {
		if (p0->node_id[i] != p1->node_id[i])
			break;
	}

	return i;
}

BOOL path_similar(struct path *p0, struct path *p1)
{
	T_LEN i;
	if (p0->len != p1->len)
		return 0;
	
	for (i = 0; i < p0->len; i++) {
		if (p0->label[i] != p1->label[i])
			return 0;
	}

	return 1;
}

struct path_ptr 
*path_li_add(struct list_it *li, struct path *path)
{
	struct path_ptr *ptr = malloc(sizeof(struct path_ptr));
	debug ++;
	ptr->path = path;
	LIST_CONS(ptr->refs);
	ptr->n_refs = 0;
	LIST_NODE_CONS(ptr->ln);
	list_insert_one_at_tail(&ptr->ln, li, NULL, NULL);
	return ptr;
}

void path_ptr_link(struct path_ptr *a, struct path_ptr *b)
{
	struct path_ref *a_ref, *b_ref;
	a_ref = malloc(sizeof(struct path_ref));
	debug ++;
	b_ref = malloc(sizeof(struct path_ref));
	debug ++;
	LIST_NODE_CONS(a_ref->ln);
	LIST_NODE_CONS(b_ref->ln);
	a_ref->to = b;
	a_ref->from = b_ref;
	b_ref->to = a;
	b_ref->from = a_ref;

	list_insert_one_at_tail(&a_ref->ln, &a->refs, NULL, NULL);
	list_insert_one_at_tail(&b_ref->ln, &b->refs, NULL, NULL);
	a->n_refs ++;
	b->n_refs ++;
}

LIST_DEF_FREE_FUN(path_ref_free, struct path_ref, ln, free(p);debug--);

static LIST_IT_CALLBK(match_d)
{
	LIST_OBJ(struct path_ptr, d, ln);
	P_CAST(q, struct path_ptr, pa_extra);

	if (path_similar(d->path, q->path))
		path_ptr_link(d, q);

	LIST_GO_OVER;
}

static LIST_IT_CALLBK(match_in_D)
{
	LIST_OBJ(struct path_ptr, q, ln);
	P_CAST(D, struct list_it, pa_extra);

	list_foreach(D, &match_d, q);
	LIST_GO_OVER;
}

static LIST_IT_CALLBK(print_refs)
{
	uint32_t i;
	LIST_OBJ(struct path_ref, ref, ln);

	if (ref->to) 
		printf("#%d", PATH_ID(ref->to->path));
	else
		printf("null");

	if (pa_now->now == pa_head->last) {
		printf(".");
		return LIST_RET_BREAK;
	} else {
		printf(", ");
		return LIST_RET_CONTINUE;
	}
}

static LIST_IT_CALLBK(print_ptr)
{
	uint32_t i;
	LIST_OBJ(struct path_ptr, ptr, ln);

	path_print(ptr->path, stdout);
	if (ptr->n_refs) {
		printf(" -> ");
		list_foreach(&ptr->refs, &print_refs, NULL);
	} 

	printf("\n");
	LIST_GO_OVER;
}

void print_D_Q_set(struct list_it *D, struct list_it *Q)
{
	printf(C_GREEN "D set:\n" C_RST);
	list_foreach(D, &print_ptr, NULL);
	printf(C_GREEN "Q set:\n" C_RST);
	list_foreach(Q, &print_ptr, NULL);
	printf("\n");
}

static LIST_IT_CALLBK(path_ptr_destory)
{
	LIST_OBJ(struct path_ptr, ptr, ln);
	BOOL res;
	res = list_detach_one(&ptr->ln, pa_head, pa_now, pa_fwd);
	path_ref_free(&ptr->refs);

	free(ptr);
	debug --;
	return res;
}

static LIST_IT_CALLBK(eliminate)
{
	LIST_OBJ(struct path_ptr, ptr, ln);
	P_CAST(if_fail, BOOL, pa_extra);
	BOOL res;

	if (ptr->n_refs == 0) {
		*if_fail = 1;
		return LIST_RET_BREAK;

	} 

	LIST_GO_OVER;
}

struct heavy_path_arg {
	struct path_ptr *hvy;
	T_LEN        longest;
};

static LIST_IT_CALLBK(choose_longest)
{
	LIST_OBJ(struct path_ptr, q, ln);
	P_CAST(cha, struct heavy_path_arg, pa_extra);
	if (cha->hvy == NULL || q->path->len > cha->longest) {
		cha->hvy = q;
		cha->longest = q->path->len;
	}

	LIST_GO_OVER;
}

struct path_ptr
*heavy_path(struct list_it *Q)
{
	struct heavy_path_arg cha = {NULL, 0};
	list_foreach(Q, &choose_longest, &cha);

	return cha.hvy;
}

struct path_li_exist_arg {
	struct path     *path;
	struct path_ptr *found;
};

static LIST_IT_CALLBK(find_exist)
{
	LIST_OBJ(struct path_ptr, ptr, ln);
	P_CAST(plea, struct path_li_exist_arg, pa_extra);

	if (plea->path == ptr->path) {
		plea->found = ptr;
		return LIST_RET_BREAK;
	}

	LIST_GO_OVER;
}

struct path_ptr 
*path_li_exist(struct list_it *li, struct path *path)
{
	struct path_li_exist_arg plea = {path, NULL};
	list_foreach(li, &find_exist, &plea);
	return plea.found;
}

struct decompose_arg {
	BOOL             res;
	T_LEN            t;
	struct path_ptr *hvy, *save_q;
	struct path     *d_j, *q_m;
	struct list_it  *Q, *Q_, *D_;
};

static LIST_IT_CALLBK(decompose_inner)
{
	LIST_OBJ(struct path_ref, ref, ln);
	P_CAST(da, struct decompose_arg, pa_extra);
	struct path *d_i = ref->to->path;
	struct path_ptr *save_ptr;

	if (d_i != da->d_j && da->t == path_merge_pos(d_i, da->d_j)) {

		printf("\t\tpath #%d also merge at %d in D.\n", 
		       PATH_ID(d_i), da->t);

		save_ptr = path_li_exist(&da->D_[da->t], d_i);

		if (save_ptr) {
			printf("\t\tlink to an existing D entry...\n");
			path_ptr_link(save_ptr, da->save_q);
		} else {
			printf("\t\tcreate a new D entry...\n");
			save_ptr = path_li_add(&da->D_[da->t], d_i);
			path_ptr_link(save_ptr, da->save_q);
		}
	}

	LIST_GO_OVER;
}

static LIST_IT_CALLBK(decompose_outter)
{
	LIST_OBJ(struct path_ptr, q, ln);
	P_CAST(da, struct decompose_arg, pa_extra);
	struct path  *q_n;

	if (q != da->hvy) {
		q_n = q->path;
		da->t = path_merge_pos(q_n, da->q_m);
		printf("\tpath #%d merge at %d in Q.\n", 
		       PATH_ID(q_n), da->t);

		da->save_q = path_li_add(&da->Q_[da->t], q_n);
		list_foreach(&q->refs, &decompose_inner, da);
	}

	LIST_GO_OVER;
}

BOOL lpd(struct list_it*, struct list_it*);

BOOL decompose(struct decompose_arg *dcpa)
{
	uint32_t t;
	BOOL res = 1;

	struct list_it *D_ = calloc(dcpa->d_j->len, 
	                            sizeof(struct list_it) *
	                            sizeof(struct path_set*)); 
	struct list_it *Q_ = calloc(dcpa->q_m->len, 
	                            sizeof(struct list_it) *
	                            sizeof(struct path_set*)); 
	debug += 2;
	dcpa->D_ = D_;
	dcpa->Q_ = Q_;

	list_foreach(dcpa->Q, &decompose_outter, dcpa);

	for (t = 0; t < dcpa->q_m->len; t++) {
		if (NULL != Q_[t].now) {
			printf("sub-problem @ %d \n", t);
			print_D_Q_set(&D_[t], &Q_[t]);
		}
	}

	for (t = 0; t < dcpa->q_m->len; t++) {
		if (NULL != Q_[t].now) {
			printf("solving sub-problem @ %d...\n", t);
			if (0 == (res = lpd(&D_[t], &Q_[t]))) {
				printf("no luck.\n");
				break;
			} else
				printf("good.\n");
		}
	}
	printf("\n");

	for (t = 0; t < dcpa->q_m->len; t++) {
		if (NULL != Q_[t].now) {
			list_foreach(&D_[t], &path_ptr_destory, NULL);
			list_foreach(&Q_[t], &path_ptr_destory, NULL);
		}
	}
	
	free(D_);
	free(Q_);
	debug -= 2;
	return res;
}

static LIST_IT_CALLBK(try_hvy_path)
{
	LIST_OBJ(struct path_ref, ref, ln);
	P_CAST(dcpa, struct decompose_arg, pa_extra);
	struct path_ptr *d = ref->to;

	printf("try #%d as hvy match in D...\n", PATH_ID(d->path));
	dcpa->d_j = d->path;
	
	if (decompose(dcpa)) {
		printf("decomposition successful.\n");
		printf(C_GREEN "#%d and #%d match!\n" C_RST, 
		       PATH_ID(dcpa->d_j), PATH_ID(dcpa->q_m));
		dcpa->res = 1;
		return LIST_RET_BREAK;
	}

	LIST_GO_OVER;
}

BOOL lpd(struct list_it *D, struct list_it *Q)
{
	struct path_ptr *hvy;
	struct decompose_arg dcpa;
	BOOL   if_fail = 0;

	list_foreach(Q, &eliminate, &if_fail);

	if (if_fail) {
		printf("no candidate, fail.\n");
		return 0;
	}

	if (Q->now == NULL) {
		printf("Q is empty, success.\n");
		return 1;
	} else if (D->now == NULL) {
		printf("D is empty, fail.\n");
		return 0;
	}

	hvy = heavy_path(Q);
	printf("choose hvy path: #%d in Q.\n\n", PATH_ID(hvy->path));

	dcpa.Q = Q;
	dcpa.res = 0;
	dcpa.hvy = hvy;
	dcpa.q_m = hvy->path;

	list_foreach(&hvy->refs, &try_hvy_path, &dcpa);
	
	return dcpa.res;
}

int main()
{
	uint32_t i;

//	struct path D_path[] = {
//		{3, {0, 0, 0}, {6, 4, 1}},
//		{3, {0, 0, 0}, {6, 5, 2}},
//		{3, {0, 0, 0}, {6, 5, 3}}
//	};
//
//	struct path Q_path[] = {
//		{3, {0, 0, 0}, {4, 3, 1}},
//		{3, {0, 0, 0}, {4, 3, 2}}//,
//		//{3, {0, 0, 0}, {4, 3, 5}}
//	};

//	struct path D_path[] = {
//		{5, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5}},
//		{4, {0, 0, 0, 0}, {1, 6, 7, 8}},
//		{3, {0, 0, 0}, {1, 9, 10}}
//	};
//
//	struct path Q_path[] = {
//		{5, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5}},
//		{4, {0, 0, 0, 0}, {1, 6, 7, 8}},
//		{3, {0, 0, 0}, {1, 6, 10}}
//	};

	struct path D_path[] = {
		{3, {0, 0, 0}, {0, 1, 3}},
		{3, {0, 0, 0}, {0, 1, 4}},
		{4, {0, 0, 0, 0}, {0, 2, 5, 12}},
		{5, {0, 0, 0, 0, 0}, {0, 2, 5, 11, 23}},
		{5, {0, 0, 0, 0, 0}, {0, 2, 5, 11, 24}},
		{5, {0, 0, 0, 0, 0}, {0, 2, 6, 14, 30}},
		{6, {0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 27, 56}},
		{6, {0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 28, 57}},
		{6, {0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 59}},
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 27, 55, 111}},
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 27, 55, 112}},
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 28, 58, 118}},
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 60, 121}},
		{8, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 28, 58, 117, 235}},
		{8, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 28, 58, 117, 236}},
		{8, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 60, 122, 245}},
		{8, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 60, 122, 246}}
	};

	struct path Q_path[] = {
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 27, 55, 111}},
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 27, 55, 112}},
		{6, {0, 0, 0, 0, 0, 0}, {0, 2, 6, 13, 27, 56}},
		{7, {0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 60, 121}},
		{8, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 60, 122, 245}},
		{8, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 6, 14, 29, 60, 122, 246}}
	};

	struct list_it D, Q;
	LIST_CONS(D);
	LIST_CONS(Q);

	for (i = 0; i < PATH_ARRAY_LEN(D_path); i++) {
		path_li_add(&D, &D_path[i]);
	}
	
	for (i = 0; i < PATH_ARRAY_LEN(Q_path); i++) {
		path_li_add(&Q, &Q_path[i]);
	}
	
	list_foreach(&Q, &match_in_D, &D);
	printf("initial match:\n");
	print_D_Q_set(&D, &Q);
	
	printf("result is %d.\n", lpd(&D, &Q));

	list_foreach(&D, &path_ptr_destory, NULL);
	list_foreach(&Q, &path_ptr_destory, NULL);

	printf("debug = %d\n", debug);
	return 0;
}

lpd.pseudo.py

# path a and b are said to be similar when |a|=|b|
# and the sequence of labels in a and b are equal.
# denote a ~ b.

# define similar set:
S(q, D) = {d in D: d ~ q}

# given a set of document paths in D, and a set of
# query paths in Q, test if the tree of query is the 
# subtree of that of document.
test_subtree(D, Q) 
{
	for q_k in Q:
		# candidate set
		C_k := S(q_k, D)
	lpd(D, C, Q)
}

# long path decomposition algorithm.
lpd(D, C, Q)
{
	for q_k in Q:
		if |C_k| = 0:
			return FAIL

	if Q = ∅ :
		return SUCC
	else if D = ∅ :
		return FAIL

	# choose an arbitrary path (a heavy path here) 
	q_m := heavy_path_in(Q)
	for d_j in C_m:
		if decompose(C, Q, d_j, q_m) = SUCC:
			return SUCC
	return FAIL
}

decompose(C, Q, d_j, q_m)
{
	# a | b is the merge position of a and b.
	for q_n in Q, n != m:
		t := q_n | q_m
		Q_t := Q_t U {q_n}
		for d_i in C_n, i != j:
			if t = d_i | d_j:
				D_t := D_t U {d_i}
				C_t_n := C_t_n U {d_i}
				P := P U {t}

	# solve the sub-problems.
	for t in P:
		if lpd(D_t, C_t, Q_t) = FAIL:
			return FAIL	

	return SUCC
}