Update 45: Implemented Graph Library

I have written a graph library following my graph data structure design.
Currently the utility functions (newGraph, addNode...), the pretty
printing functions and the freeing functions are written. There are
significant memory leaks to be fixed.
Update 46: Debugging and graph pretty printer.

graph.c
- Fixed many bugs: the graph library now adds and removes nodes and edges
  correctly without any memory leaks or other issues.
- Wrote functions to pretty print a graph.

seman.c
- Added a check to prevent freeBiEdgeList being called on a NULL pointer.
- Added code to free the auxiliary GSList interface_ids in interface_scan.

ast.c
- Fixed code to handle the empty string in newASTString.
Update 47: Rewrote pretty printing of graph labels.

I rewrote the pretty printing of graph labels so that there are no
trailing colons and arithmetic expressions are bracketed.
Update 48: Added query operations.

I wrote the functions for the graph querying operations and commented the graph library header and source.
Added hyphens to the identifier character set and changes names of output dot files for printed ASTs.
Update 49: Debugging the graph module.

The integer hash tables for the inedges/outedges of nodes were not
functioning correctly. This is because I was using g_int_hash instead
of g_direct_hash. The latter is the appropriate hash function for
my purposes.

The relabelling functions were also incomplete: I added code to modify
the appropriate index-by-label-class hash tables in the case that the
new label is a different label class to the old one.
Changed some function prototypes and created an explicit structure for labels in the graph module.
Update 50: Started implementing rule matching.

I created the match module which will contain the rule matching
code and the data structures necessary to support it. Currently
I have implemented a stack, a data structure for rules and
morphisms, and a fairly basic static searchplan algorithm.
It's still very rough and does not compile; there are a lot
of changes to be made.
Update 51: Matching Algorithm

Finished coding the logic for a matching algorithm based on a somewhat
unsophisticated static searchplan approach. I have written a function
to populate the morphism data structure once the matching information
has been found. Label matching is still not implemented.

I made some changes to the function headers in the graph module.
The functions now take pointers to nodes and edges instead of
integers. The bodies of the functions are conceptually the same.
Update 52: Rule matching algorithm

I have reworked the rule matching algorithm: it uses a simple stack
to control backtracking should a node match or edge match fail. The
matching of an edge (from its matched source or target) and the
matching of its other incident node are now done in one step since
there is no choice for the other node.

In addition, I have implemented the label matching algorithm.

I added an inedges/outedges list to the node structure so that they
can be accessed independently of their label class. This is neccesary
for the matching algorithm code.
Update 53: Debugging and refactoring.

Many bugs in the label matching algorithm have been fixed!

- In staticSearchplan, when matching a non-root node, the rule node
  was obtained by indexing into the edge list of lhs instead of the
  node list.

- matchNode did not check if index >= 0 before looking up the old host
  node.

- The graph querying functions that found nodes or edges by their label
  class were not updated to the hash key format with G_INT_TO_POINTER.

- The freeing functions of assignments, variable lists and mappings were
  incorrect.

- lookupValue and lookupType compared strings with == when strcmp should
  have been used.

- isSuffix and isPrefix reported a malloc error if the pointer returned
  was *not* NULL.

- verifyAtomVariable did not allocate memory to atom_copy.

- Functions called by staticSearchplan now take their assignment argument
  by reference to ensure that any updates to the assignments are
  preserved.

- There were several bugs concerning the handling of empty lists. In
  particular, the representation of an empty list as a NULL pointer is
  erroneous because the result of lookupValue returns NULL if either no
  value is found or if the value found is the empty list. This is fixed
  by representing empty lists as a GList containing a single ListElement
  with type EMPTY.

- verifyListVariable was not copying the list correctly (list->data in
  the loop instead of list_to_copy->data).

- addVariable returned void instead of a VariableList*.
Update 54: Debugging

If there are multiple variables in a label, and the matching fails
after the first one has been assigned, the assignment of the first
variable is erroneously kept. I have implemented the functionality
to restore the assignment to its original state if labelMatch
fails at any point.

Also, in staticSearchplan there were a few points where I incorrectly
used break instead of continue.
Update 54: Rewrote matching of concatenated strings + debugging

Concatenated strings are now matched by first converting the tree
representation of the AST into a list of string expressions (constants,
character variables, string variables) and matching that list with
an algorithm similar to that of labelMatch.

Bug fixes:

- Added case CHAR_DECLARATIONS to freeAST.

- In labelMatch, when host_list reaches NULL in the main loop, there is
  no check to see if we are examining the rule_list's last element.

- freeVariableList was incorrect.

- verifyAtomVariable returned bool; should return int to coordinate with
  its calling functions.
Update 55: Debugging

assignment made into a global variable, which means the searchplan and
label matching functions take one less parameter, and the address of
assignment no longer has to be passed around. This makes the code
nicer, albeit a little harder to read, and removes strange memory leaks
caused by addAssignment.

I also added a function to support the freeing of GLists generated
by concatExpToList.

Bug fixes:
- removeAssignment did not free the removed assignment pointers
  to heap.
- verifyAtomVariable no longer makes copies of host_atom to pass
Update 56: Debugging

Bugs fixed:

The do-while loop condition in staticSearchplan contained OR instead
of AND.

The node matching loop not break after matching a node; this meant that
more than one node could be matched in a single step which is not the
intended behaviour.

matchEdge did not obtain the correct host node to query for its edge
list.

In the backtracking code, a node mapping was not removed when the node
flag was set to false.
General reorganisation of code, including a header file for global constructs.
Resolved merge conflicts.
Update 57: Updating the graph data structure.

I have added an invariant testing function and a stack-based
backtracking routine for restoring a graph by popping and undoing
small changes.
Update 58: Graph data structure modifications.

The graph's nodes and edges are stored in a hashtable instead of the
old pointer array. I have modified the graph utility/query functions
accordingly, and rewritten the invariant checker according to the
new data structure.

I also moved the stack code to a separate module.
Update 59: Graph Data Structure

The node/edge store has been re-implemented as a pointer array, but
this time I use my own instead of the GPtrArray. Ditto for the adjacent
edge references in the node structures.

Implemented a graph backtracking system that works by copying the
working graph into heap and placing it on a global graph stack.
Restoring the graph is a simple matter of popping the graph stack.
I also wrote a function to free a stack which takes the stack to free
and a function to free its data.

Rewrote the validGraph function and added some more invariants.

Updated the comments in the header file and fixed some minor bugs.