A priority queue for a simplified agenda manager in a rule-based expert system shell

(Course - Analysis of Algorithms, Spring 2012)

Goal

The goal of this project was to implement a simplified agenda manager which reads a list of rules with priorities from a file and created a heap by using a priority queue to run the manager

View The full project specification

Team Members

Vishal Ghugare

Overview of the project

Implementation language: C

Queue structure used

typedef struct ListItem 
{ 
    int priority; 
    char rule[RULE_LEN]; 
    struct ListItem *next; 
}

Implemented Functions

• BuildQueue()
  Builds a priority queue (heap) from an unsorted array of rule priority pairs. This function is usually called after inserting a rule into the queue by calling the Insert function. This function starts for the mid of the queue which is parent of the newest node inserted and runs a contest between the parent and newly added child. If the priority of parent is less than that of child then we interchange the parent and child. However the new parent might still be out of place at its new position, so have another contest between it and its parent in the tree and run the above check for the parent. We repeat this process until the new item either loses a contest (and therefore is in correct position in the heap) or reaches the root node.

  Sorry I cannot provide the code as this course is currently ongoing. If you still want the code please 
  request for it submitting the form below

• Heapify()
  This function is used by BuildQueue function to maintain the heap properly. When we add a new rule to the heap, a new node is added at the end of the queue. However, simply placing the new rule at that position is likely to violate the property of heap. That is, the new item might have a priority that is greater than the priority of its parent. The solution after placing the new item in the end of the queue, have a contest between the new item added and its parent in the tree. If the new item has higher priority, swap it with its parent. However the new item might still be out of place at its new position, so have another contest between it and its new parent in the tree. Repeat this process until the new item either loses a contest (and therefore is in correct position in the heap) or reaches the root node.

  Sorry I cannot provide the code as this course is currently ongoing. If you still want the code please 
  request for it submitting the form below

• ExtractMax()
  The insert function is used to add a new rule at the end of queue. This is done by first dynamically allocating a new node of the queue type and initializing it with the provided values. The queue structure is then maintained so that the Q_head pointer points to the starting node of the queue and Q_tail points to the ending node of the queue.

  Sorry I cannot provide the code as this course is currently ongoing. If you still want the code please 
  request for it submitting the form below

• 
  Delete()
  Removes a rule from the queue by freeing the node from memory.

  Sorry I cannot provide the code as this course is currently ongoing. If you still want the code please 
  request for it submitting the form below

• Main()
  This function reads input file provided as arguments and performs the steps mentioned in the problem definition which are as follows:
  In each cycle, the agenda manager first deletes from the agenda the activated rule that was executed in a previous cycle. A list of new activated rules is given to the agenda manager to add to the agenda. Once a rule is added to the agenda, it remains there until it is executed. An agenda manager then determines the rule with highest priority for the inference engine to execute in this cycle. Only one rule can be executed in each cycle. A rule that has been executed and removed from the agenda may be put on the agenda again in the next cycle. The system halts when the agenda is empty or after it runs 30 cycles.
  It also checks input file for correct format while reading and displays necessary errors where ever required. The errors could be one of the following for the following rule input format:

  rule1, priority1), (rule2, priority2) 
  (rule3, priority3)

  • If there is no ‘(’ before rule1 string then it will give an error “Missing: opening bracket '('”
  • If there is no ‘,’ after rule1 then it will give an error “Missing: comma after rule!”
  • If priority1 is not detected as a number then it will give an error “Invalid priority for rule: rule1”
  • If there is no ‘)’ after priority1(numeric) then it will give an error “Missing: closing bracket ')' for rule:rule1”
  • Now if no ‘,’ is found after closing bracket then it will give an error “Missing comma after (rule1, priority1)”
  • If there is no ‘ ’(space after the ‘,’(comma)) then it will give an error “Missing space after (rule1, priority1),”
  This will be followed throughout the file

Sorry I cannot provide the code as this course is currently ongoing. If you still want the code please 
request for it submitting the form below