<jupyter_start><jupyter_text>The ZPDES_Memory algorithm requires a curriculum graph in the form of a tree structure. This notebooks gives two examples of creating this tree.1. Build_Tree will build the tree structure based on a trace based analysis of an execution trace or sentence trace as given in [1, 2]2. Static_Tree takes in a predefined graph in the form of a dictionary that maps nodes to its immediate children to create a tree structure.[1] Andersen, Erik, <NAME>, and <NAME>. "A trace-based framework for analyzing and synthesizing educational progressions." Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2013.[2] <NAME>, <NAME>, and <NAME>. "A unified framework for knowledge assessment and progression analysis and design." Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems. ACM, 2017.  Example ProgressionWe refer to each node of the graph to be a *concept*. We refer to a practice item that a student can complete as a *problem*. Each concept can have one or more problems. Each problem should only belong to one concept. We work for hashable representations for concepts and problems (in our example data, these representations are strings).For both methods, a couple of parameters need to be defined:1. all_concepts: a list of all concepts in the curriculum graph, these are the nodes in the curriculum graph2. concept_problems: a dictionary mapping concept to problems. In the example data below, the problems 'cat', 'tas', and 'cas' coorespond to the concept of 'SAS'. Note there can also be the case where every concept corresponds to one unique problem.3. problem_components: a dictionary mapping problem to basic components(if defined). In the example data below the basic components 'r' and 'c' make up the problem 'rc'. Note that there can also be the case where basic components are not defined, in this case every problem corresponds to one unique basic component (see the ```if problem_components is None or all_basic_components is None``` case).3. all_basic_components: a list of all basic components that make up the problems (if defined). If not defined, then this should be a list of all problems (see the ```if problem_components is None or all_basic_components is None``` case).In this example, we will create the following target curriculum graph:![tree_example_graph.png](attachment:tree_example_graph.png)Where *'Root'* is a dummy root node the connects to all nodes that don't have any prerequisites.<jupyter_code>tree_name = 'example_tree' #base name for saving files
all_concepts = ['S' ,'N', 'C', 'CS', 'SAS', 'CAC', 'CSACS', 'NCS', 'NCSANCS']
concept_problems = {
    'S': ['t', 'c', 's'],
    'C': ['r', 'w', 'g'],
    'N': ['1', '2', '3'],
    'CS':['rc', 'rt', 'gc', 'gt', 'wt', 'ws'],
    'SAS':['cat', 'tas', 'cas'],
    'CAC':['raw', 'rag', 'wag'],
    'CSACS':['rtawt', 'wsagc', 'rcagt'],
    'NCS': ['1rs', '1wc', '1gt', '2wc', '1gc', '2ws'],
    'NCSANCS':['2rta2gc', '3rta3wt', '1wsa2gs', '2wta3gs']
}
all_basic_components = ['r', 'w', 'g', 't', 'c', 's', '1', '2', '3']
problem_components = {
    't': ['t'],
    'c': ['c'],
    's': ['s'],
    'r': ['r'],
    'w': ['w'],
    'g': ['g'],
    '1': ['1'],
    '2': ['2'],
    '3': ['3'],
    'rc': ['r', 'c'],
    'rt': ['r', 't'],
    'gc': ['g', 'c'],
    'gt': ['g', 't'],
    'wt': ['w', 't'],
    'ws': ['w', 's'],
    'cat': ['c', 't'],
    'tas': ['t', 's'],
    'cas': ['c', 's'],
    'raw': ['r', 'w'],
    'rag': ['r', 'g'],
    'wag': ['w', 'g'],
    'rtawt': ['r', 't', 'w', 't'],
    'wsagc': ['w', 's', 'g', 'c'],
    'rcagt': ['r', 'c', 'g', 't'],
    '1rs': ['1', 'r', 's'],
    '1wc': ['1', 'w', 'c'],
    '1gt': ['1', 'g', 't'],
    '2wc': ['2', 'w', 'c'],
    '1gc': ['1', 'g', 'c'],
    '2ws': ['2', 'w', 's'],
    '2rta2gc': ['2', 'r', 't', '2', 'g', 'c'],
    '3rta3wt': ['3', 'r', 't', '3', 'w', 't'],
    '1wsa2gs': ['1', 'w', 's', '2', 'g', 's'],
    '2wta3gs': ['2', 'w', 't', '3', 'g', 's']
}

# all_basic_components = None
# problem_components = None

if problem_components is None or all_basic_components is None:
    problem_components = {}
    for concept, concept_problems_list in concept_problems.items():
        for problem in concept_problems_list:
            problem_components[problem] = [problem]
    all_basic_components = list(problem_components.keys())<jupyter_output><empty_output><jupyter_text>Using Build_Tree and trace based analysis<jupyter_code>#Parameters
n = 1 #the n for creating in ngrams, in our case we are using 1-grams<jupyter_output><empty_output><jupyter_text>The Build_Tree tree needs a Build_Tree_Data object that takes in all_concepts, concept_problems, all_basic_components, problem_components and n.<jupyter_code>data = Build_Tree_Data(all_concepts= all_concepts, concept_problems = concept_problems, 
                       all_basic_components = all_basic_components, problem_components = problem_components, n = n)<jupyter_output><empty_output><jupyter_text>Build_Tree additionally takes in a comparison function (the ```comp_func``` argument). This function must be defined in the file 'compare_function.py' (this necessity is for saving and loading the tree using the pickle package) and should take in node1, node2 and return - -1 if node1 is harder than node2- 1 if node2 is harder than node1- 0 if neither is harder than the other<jupyter_code>print('Creating Tree')

#Define the "Root" tree
progression_tree_build = Build_Tree(name='Root', data=data, comp_func=compare_ngrams)

#Loop through each concept in all_concepts and insert it into the tree
for i, concept_name in enumerate(all_concepts):
    print('Current concept: %d, Current concept Name: %s'%(i, concept_name))
    progression_tree_build.insert_node(concept_name)

#calculate ancestors (prerequisites) after all nodes are inserted
progression_tree_build.calculate_parents()
#Save the tree, this will save the tree as 'tree_name.p'
progression_tree_build.save_tree(tree_name + '.p')<jupyter_output><empty_output><jupyter_text>Using and Static_Tree a predefined tree structure to build a treeStatic tree takes in the predefined structure in the form of a dictionary mapping concept to all immediate children (all problems directly easier than it) in the prerequisite graph. See the ```tree_structure``` below for our example. Note that the 'Root' node must be defined.Similarly to Build_Tree it also takes in all_concepts, concept_problems, all_basic_components, and problem_components.<jupyter_code>tree_structure = {
    'Root': ['S', 'N', 'C'],
    'S': ['CS', 'SAS'],
    'N': ['NCS'],
    'C': ['CS', 'CAC'],
    'CS': ['CSACS', 'NCS'],
    'SAS': ['CSACS'],
    'CAC': ['CSACS'],
    'CSACS': ['NCSANCS'],
    'NCS': ['NCSANCS'],
    'NCSANCS': []
}
#Create the tree
progression_tree_static = Static_Tree(children = tree_structure, all_concepts = all_concepts, 
                                      concept_problems = concept_problems, all_basic_components = all_basic_components, 
                                      problem_components = problem_components)
#save the tree, this will save the tree to a file 'tree_name.txt'
progression_tree_static.save_tree(tree_name + '.txt')<jupyter_output><empty_output><jupyter_text>Other Tree Functionality  Visualizing the curriculum graph made by Build_Tree using the Digraph packageThe following code will make a visualization of the graph made by Build_Tree - will also save the graph as '```tree_name```.gv' and a visualization of the graph as '```tree_name```.gv.png' in the current directory.<jupyter_code>#Some helpful functions for rendering and visualizing and saving graphs with the Digraph package
def create_graph (tree, data):
    graph = Digraph(format='png', strict = True)
    for problem_name, problem_data in data.items():
        graph.node(problem_name, problem_data)
        tree.add_edges_to_progression(graph)
    return graph

def render_save_graph(graph, save_name):
    graph.render(save_name, view=True)
#Choose a tree to use
# progression_tree = progression_tree_build
progression_tree = progression_tree_static
#Visualize and save the graph
concept_names = {concept:concept for concept in all_concepts}
progression_graph = create_graph(progression_tree, concept_names)
render_save_graph(progression_graph, tree_name + '.gv')<jupyter_output><empty_output><jupyter_text>Loading in the trees from fileTo saved trees can be loaded in from the their save files in the following way:<jupyter_code>progression_tree_build_2 = Build_Tree(tree_filename = tree_name + '.p')
progression_tree_static_2 = Static_Tree(tree_filename = tree_name + '.txt')<jupyter_output><empty_output><jupyter_text>Getting additional information:Additionally we can get the immediate children and parents as well as all the children and parents from a tree<jupyter_code>print("Children: " + str(progression_tree.return_children()))
print("All Descendants: " + str(progression_tree.return_all_descendants()))
print("Parents: " + str(progression_tree.return_parents()))
print("All Ancestors: " + str(progression_tree.return_all_ancestors()))<jupyter_output>Children: {'Root': ['S', 'N', 'C'], 'S': ['CS', 'SAS'], 'N': ['NCS'], 'C': ['CS', 'CAC'], 'CS': ['CSACS', 'NCS'], 'SAS': ['CSACS'], 'CAC': ['CSACS'], 'CSACS': ['NCSANCS'], 'NCS': ['NCSANCS'], 'NCSANCS': []}
All Descendants: {'NCSANCS': [], 'CSACS': ['NCSANCS'], 'NCS': ['NCSANCS'], 'CS': ['CSACS', 'NCS', 'NCSANCS'], 'SAS': ['CSACS', 'NCSANCS'], 'S': ['CS', 'SAS', 'NCSANCS', 'CSACS', 'NCS'], 'N': ['NCS', 'NCSANCS'], 'CAC': ['CSACS', 'NCSANCS'], 'C': ['CS', 'NCSANCS', 'CSACS', 'NCS', 'CAC'], 'Root': ['N', 'CS', 'SAS', 'CAC', 'NCSANCS', 'C', 'CSACS', 'NCS', 'S']}
Parents: {'S': [], 'N': [], 'C': [], 'CS': ['S', 'C'], 'SAS': ['S'], 'CAC': ['C'], 'CSACS': ['CS', 'SAS', 'CAC'], 'NCS': ['N', 'CS'], 'NCSANCS': ['CSACS', 'NCS']}
All Ancestors: {'S': [], 'C': [], 'CS': ['C', 'S'], 'SAS': ['S'], 'CAC': ['C'], 'CSACS': ['CS', 'SAS', 'CAC', 'C', 'S'], 'N': [], 'NCS': ['N', 'C', 'CS', 'S'], 'NCSANCS': ['N', 'CS', 'SAS', 'C', 'S', 'CSACS', 'NCS', 'CAC']}
StarcoderdataJupyterStructuredCleanDedup