#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
// event node
struct node
{
int event;
int freq;
struct node* next;
struct node* prev;
};
// event list
struct eventList
{
struct node* head;
struct node* tail;
int size;
};
//create new event node
struct node* createNode(int event) {
struct node* ptr = (struct node*) malloc (sizeof(struct node));
ptr->event = event;
ptr->freq = 1;
ptr->next = NULL;
ptr->prev = NULL;
return ptr;
}
// insert new event
void eventInsert(struct eventList* L, int event) {
struct node* newNode = createNode(event);
struct node* ptr = L->head;
if(L->head == NULL) {
L->head = newNode;
L->tail = newNode;
}
else if(event < L->head->event) { // insert as first node
newNode->next = L->head;
L->head->prev = newNode;
L->head = newNode;
}
else {
while (ptr != NULL && ptr->event < event) {
ptr = ptr->next;
}
if(ptr != NULL) { // insert before ptr
newNode->next = ptr;
ptr->prev->next = newNode;
newNode->prev = ptr->prev;
ptr->prev = newNode;
}
else //insert as last node
{
newNode->prev = L->tail;
L->tail->next = newNode;
L->tail = newNode;
}
}
L->size++;
}
// print events
void eventPrint(struct eventList* L) {
struct node* ptr = L->head;
while(ptr != NULL) {
if(ptr->event < 256) {
printf("%c = %d\n", ptr->event, ptr->freq);
}
else {
printf("%d = %d\n", ptr->event, ptr->freq);
}
ptr = ptr->next;
}
}
// increase freqency of an event
void increaseEventFreq(struct eventList* L, int event) {
struct node* ptr = L->head;
while(ptr != NULL) {
if(ptr->event == event) {
ptr->freq++;
break;
}
ptr = ptr->next;
}
}
// search for an event
int eventSearch(struct eventList* L, int event) {
struct node* ptr = L->head;
while(ptr != NULL) {
if(ptr->event == event) {
return 1;
}
ptr = ptr->next;
}
return 0;
}
// trace node
struct trace
{
int* t;
int traceLength;
int frequency;
struct trace* next;
struct trace* prev;
};
// trace list
struct traceList
{
struct trace* head;
struct trace* tail;
int size;
};
// create trace node
struct trace* createTrace(int* trace, int length) {
struct trace* ptr = (struct trace*) malloc (sizeof(struct trace));
ptr->t = trace;
ptr->traceLength = length;
ptr->frequency = 1;
ptr->next = NULL;
ptr->prev = NULL;
return ptr;
}
// insert new trace
void traceInsert(struct traceList* L, int* trace, int length) {
struct trace* newNode = createTrace(trace, length);
if(L->head == NULL) {
L->head = newNode;
L->tail = newNode;
}
else {
newNode->prev = L->tail;
L->tail->next = newNode;
L->tail = newNode;
}
L->size++;
}
// print events in a trace
void printTrace(int *a, int len) {
int i;
for(i = 0; i < len; i++) {
if(a[i] < 256) {
printf("%c", a[i]);
}
else {
printf("%d", a[i]);
}
}
printf("\n");
}
// print all traces
void traceListPrint(struct traceList* L) {
struct trace* ptr = L->head;
while(ptr != NULL) {
printTrace(ptr->t, ptr->traceLength);
ptr = ptr->next;
}
}
// compare two traces
int compareTraces(int* t1, int l1, int* t2, int l2) {
if(l1 != l2) {
return 0;
}
int i;
for(i = 0; i < l1; i++) {
if(t1[i] != t2[i]) {
return 0;
}
}
return 1;
}
//search trace
int traceSearch(struct traceList* L, int* trace, int traceLength) {
struct trace* ptr = L->head;
while(ptr != NULL) {
if(compareTraces(ptr->t, ptr->traceLength, trace, traceLength) == 1) {
return 1;
}
ptr = ptr->next;
}
return 0;
}
// increase frequecy of a trace
void increaseTraceFreq(struct traceList* L, int* trace, int traceLength) {
struct trace* ptr = L->head;
while(ptr != NULL) {
if(compareTraces(ptr->t, ptr->traceLength, trace, traceLength) == 1) {
ptr->frequency++;
break;
}
ptr = ptr->next;
}
}
// find max
int max(int a, int b) {
if(a > b) {
return a;
}
return b;
}
// main function
int main() {
// create new list to store unique events
struct eventList* L;
L = (struct eventList*) malloc (sizeof(struct eventList));
L->head = NULL;
L->tail = NULL;
L->size = 0;
// create new list to store all traces
struct traceList* T;
T = (struct traceList*) malloc (sizeof(struct traceList));
T->head = NULL;
T->tail = NULL;
T->size = 0;
// create new list to store unique traces
struct traceList* UT;
UT = (struct traceList*) malloc (sizeof(struct traceList));
UT->head = NULL;
UT->tail = NULL;
UT->size = 0;
char ch;
int* trace;
int maxfreq = 0;
int traceLength = 0;
int totalEvents = 0;
//array to store events in a trace
trace = (int*) malloc (sizeof(int));
// read data and fill L, T, and UT
while(scanf("%c", &ch) == 1) {
if(ch != EOF && ch != '\n') {
if(isalpha(ch) > 0) {
trace[traceLength] = ch;
totalEvents++;
if(eventSearch(L, ch) == 0) { // new event add it to L
eventInsert(L, ch);
}
else { // old event, ncrease frequecy
increaseEventFreq(L, ch);
}
traceLength++;
trace = (int *) realloc(trace, sizeof(int) * (traceLength + 1));
}
}
else {
if(traceSearch(UT, trace, traceLength) == 0) { //new trace, add it to UT
traceInsert(UT, trace, traceLength);
}
else { // old trace, increase its frequency in UT
increaseTraceFreq(UT, trace, traceLength);
}
traceInsert(T, trace, traceLength); // add all traces to T
traceLength = 0;
trace = (int*) malloc (sizeof(int));
}
}
//add last trace if needed
if(traceSearch(UT, trace, traceLength) == 0) { //last one is a new trace
traceInsert(UT, trace, traceLength);
}
else {
increaseTraceFreq(UT, trace, traceLength);
}
traceInsert(T, trace, traceLength); //insert last trace
//find the most frequent trace
struct trace* ptr1 = UT->head;
while(ptr1 != NULL) {
if(maxfreq < ptr1->frequency) {
maxfreq = ptr1->frequency;
}
ptr1 = ptr1->next;
}
printf("==STAGE 0============================\n");
printf("Number of distinct events: %d\n", L->size);
printf("Number of distinct traces: %d\n", UT->size);
printf("Total number of events: %d\n", totalEvents);
printf("Total number of traces: %d\n", T->size);
printf("Most frequent trace frequency: %d\n", maxfreq);
// print all the traces with maxfreq
ptr1 = UT->head;
while(ptr1 != NULL) {
if(ptr1->frequency == maxfreq) {
printTrace(ptr1->t, ptr1->traceLength);
}
ptr1 = ptr1->next;
}
//print events and frequencies
eventPrint(L);
return 0;
}
Learning Outcomes
In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter
10) and extend your program design, testing, and debugging skills. You will also learn about the problem of
process discovery and implement a simple algorithm for discovering a process model from event data.
Progoce Dicoorom
