// Numbas version: exam_results_page_options {"name": "Find a spanning tree in an undirected graph", "extensions": ["graphs"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Find a spanning tree in an undirected graph", "tags": [], "metadata": {"description": "

This question asks students to find a spanning tree for simple undirected graphs.

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "

Find spanning trees for the following graphs over the vertices $\\var{vertices}$. Enter your solution as the list of edges, using square brackets - such as [[a,b],[c,d]].

", "advice": "
    \n
  1. A possible spanning tree for the first graph is $\\var{T1}$.
  2. \n
  3. A possible spanning tree for the first graph is $\\var{T2}$.
  4. \n
", "rulesets": {}, "extensions": ["graphs"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"vertices": {"name": "vertices", "group": "Problem Parameters", "definition": "Set([\"a\",\"b\",\"c\",\"d\",\"e\",\"f\"])", "description": "", "templateType": "anything", "can_override": false}, "E1": {"name": "E1", "group": "Graph 1", "definition": "generateEdges(vertices,0.6,1,false,false)", "description": "", "templateType": "anything", "can_override": false}, "G1": {"name": "G1", "group": "Graph 1", "definition": "map([vertices[x[0]],vertices[x[1]]],x,E1)", "description": "", "templateType": "anything", "can_override": false}, "T1": {"name": "T1", "group": "Graph 1", "definition": "map(map(\"\"+y,y,x),x,spanningTree(vertices,G1))", "description": "", "templateType": "anything", "can_override": false}, "E2": {"name": "E2", "group": "Graph 2", "definition": "generateEdges(vertices,0.6,1,false,false)", "description": "", "templateType": "anything", "can_override": false}, "G2": {"name": "G2", "group": "Graph 2", "definition": "map([vertices[x[0]],vertices[x[1]]],x,E2)", "description": "", "templateType": "anything", "can_override": false}, "T2": {"name": "T2", "group": "Graph 2", "definition": "map(map(\"\"+y,y,x),x,spanningTree(vertices,G2))", "description": "", "templateType": "anything", "can_override": false}, "nvertices": {"name": "nvertices", "group": "Problem Parameters", "definition": "\" as it does not contain the expected number of edges\"", "description": "

This is to construct the solution provided in the advice.

", "templateType": "string", "can_override": false}, "hasloop": {"name": "hasloop", "group": "Problem Parameters", "definition": "\" as it contains a loop\"", "description": "", "templateType": "string", "can_override": false}, "notconnected": {"name": "notconnected", "group": "Problem Parameters", "definition": "\" as it is not connected\"", "description": "", "templateType": "string", "can_override": false}, "reasons": {"name": "reasons", "group": "Problem Parameters", "definition": "[hasloop,notconnected,\"\"]", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "length(T1)>0 and length(T2)>0", "maxRuns": "100"}, "ungrouped_variables": [], "variable_groups": [{"name": "Problem Parameters", "variables": ["vertices", "nvertices", "hasloop", "notconnected", "reasons"]}, {"name": "Graph 1", "variables": ["E1", "G1", "T1"]}, {"name": "Graph 2", "variables": ["E2", "G2", "T2"]}], "functions": {"isTree": {"parameters": [["vert", "list"], ["edges", "list"]], "type": "boolean", "language": "javascript", "definition": "function neighbours(v,G) {\n /* Return all the neighbours of the vector v in the graph G. */\n let nset = []\n for(let e of G) {\n let i = e.indexOf(v)\n if(i > -1) {nset.push(e[1-i])}\n }\n return nset\n}\n\nfunction sum(L) {\n /*Find the sum of the elements in a list.*/\n let s=0\n for (let x of L) { s+=x }\n return s\n}\n\nfunction isTree(vert,G) {\n let visited = []\n let next = [vert[0]]\n while(next.length>0) {\n let v = next.pop()\n let nset = neighbours(v,G)\n if (sum(nset.map(x=>visited.includes(x))) > 1) {return -1}\n visited.push(v)\n for(let n of nset) {if(!visited.includes(n)) next.push(n)}\n }\n if(visited.length === vert.length) return 1\n else return 0\n}\n\nreturn isTree(vert,edges)"}, "spanningTree": {"parameters": [["vert", "list"], ["edges", "list"]], "type": "list", "language": "javascript", "definition": "function neighbours(v,G) {\n /* Return all the neighbours of the vector v in the graph G. */\n let nset = []\n for(let e of G) {\n let i = e.indexOf(v)\n if(i > -1) {nset.push(e[1-i])}\n }\n return nset\n}\n\nfunction sum(L) {\n /*Find the sum of the elements in a list.*/\n let s=0\n for (let x of L) { s+=x }\n return s\n}\n\nfunction spanningTree(vert,G) {\n let visited = []\n let edges = []\n let next = [vert[0]]\n while(next.length>0) {\n let v = next.pop()\n let nset = neighbours(v,G)\n for(var x of nset) {\n if(!visited.includes(x) && !next.includes(x)) edges.push([v,x])\n }\n visited.push(v)\n for(let n of nset) {if(!visited.includes(n) && !next.includes(n)) next.push(n)}\n }\n if(visited.length === vert.length) return edges\n else return []\n}\n\nreturn spanningTree(vert,edges)"}, "randomTree": {"parameters": [["vert", "list"]], "type": "list", "language": "javascript", "definition": "n = vert.length\nedges = [[vert[0],vert[1]]]\nfor(var i=2;ix.sort())\nlet G1 = G.map(x=>x.sort())\n\nfunction isEdge(e,G) {\n return G.some(x => (x[0]===e[0] && x[1]===e[1]) || (x[1] === e[0] && x[0]===e[1]))\n}\n\nreturn T1.every(x=>isEdge(x,G1))"}, "stringLetters": {"parameters": [["input", "string"]], "type": "string", "language": "javascript", "definition": "let fixed = input.replace(/([\\[, ])(\\w)(?=[\\], ])/g,'$1\\\"$2\\\"');\nreturn fixed"}, "subgraphError": {"parameters": [["T", "list of list"], ["G", "list of list"]], "type": "string", "language": "javascript", "definition": "let T1 = T.map(x=>x.sort())\nlet G1 = G.map(x=>x.sort())\n\nfunction isEdge(e,G) {\n return G.some(x => (x[0]===e[0] && x[1]===e[1]) || (x[1] === e[0] && x[0]===e[1]))\n}\n\nlet edge = String(T1.find(x => !isEdge(x,G1)))\nreturn '[' + edge + ']'"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "jme", "useCustomName": true, "customName": "First Graph", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "studentExpr (The student's answer, parsed):\n assert(trim(studentAnswer)<>\"\",\n warn(translate(\"part.marking.nothing entered\"));\n fail(translate(\"part.marking.nothing entered\"))\n );\n try(\n simplify(\n expand_juxtapositions(\n parse(stringLetters(studentAnswer)),\n [\n \"singleLetterVariables\": settings[\"singleLetterVariables\"],\n \"noUnknownFunctions\": not settings[\"allowUnknownFunctions\"],\n \"implicitFunctionComposition\": settings[\"implicitFunctionComposition\"]\n ]\n ),\n 'basic'\n )\n , message,\n warn(translate(\"part.jme.answer invalid\",[\"message\":message]));\n fail(translate(\"part.jme.answer invalid\",[\"message\":message]))\n )\n\ncheckTree:\n isTree(vertices,cleanAnswer)\n\ncheckSubgraph:\n assert(isSubgraph(cleanAnswer,G1),\n incorrect(\"Your tree is not a subgraph of the original graph! For example, \" + findWrongEdge + \" is not an edge.\");end())\n\nfindWrongEdge:\n subgraphError(cleanAnswer,G1)\n\nverifyAnswer:\n if(checkTree=-1,\n warn(\"Your graph is not a tree, as it contains loops.\");\n incorrect(\"Your graph is not a tree, as it contains loops.\");\n end()\n ,\n if(checkTree=0,\n warn(\"Your graph is not connected.\");\n incorrect(\"Your graph is not connected.\");end()\n ,\n correct(\"The graph you entered forms a spanning tree of the original graph.\")\n ))\n \n\nmark:\n apply(studentExpr);\n apply(checkSubgraph);\n apply(checkTree);\n apply(cleanAnswer);\n apply(verifyAnswer)\n\ncleanAnswer (The student's answer, to be reused by other parts):\n Set(map(sort(x),x,eval(studentExpr)))\n\ninterpreted_answer (The student's answer, to be reused by other parts):\n cleanAnswer", "extendBaseMarkingAlgorithm": false, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Enter a spanning tree for the graph with edges {G1}:

", "answer": "{t1}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": true, "customName": "Second Graph", "marks": "1", "scripts": {}, "customMarkingAlgorithm": "studentExpr (The student's answer, parsed):\n assert(trim(studentAnswer)<>\"\",\n warn(translate(\"part.marking.nothing entered\"));\n fail(translate(\"part.marking.nothing entered\"))\n );\n try(\n simplify(\n expand_juxtapositions(\n parse(stringLetters(studentAnswer)),\n [\n \"singleLetterVariables\": settings[\"singleLetterVariables\"],\n \"noUnknownFunctions\": not settings[\"allowUnknownFunctions\"],\n \"implicitFunctionComposition\": settings[\"implicitFunctionComposition\"]\n ]\n ),\n 'basic'\n )\n , message,\n warn(translate(\"part.jme.answer invalid\",[\"message\":message]));\n fail(translate(\"part.jme.answer invalid\",[\"message\":message]))\n )\n\ncheckTree:\n isTree(vertices,cleanAnswer)\n\ncheckSubgraph:\n assert(isSubgraph(cleanAnswer,G2),\n warn(\"Your graph is not a subgraph of the original graph!\")\n incorrect(\"Your grah is not a subgraph of the original graph!\");end())\n\nverifyAnswer:\n if(checkTree=-1,\n warn(\"Your graph is not a tree, as it contains loops.\");\n incorrect(\"Your graph is not a tree, as it contains loops.\");\n end()\n ,\n if(checkTree=0,\n warn(\"Your graph is not connected.\");\n incorrect(\"Your graph is not connected.\");end()\n ,\n correct(\"The graph you entered forms a spanning tree of the original graph.\")\n ))\n \n\nmark:\n apply(studentExpr);\n apply(checkSubgraph);\n apply(checkTree);\n apply(cleanAnswer);\n apply(verifyAnswer)\n\ncleanAnswer (The student's answer, to be reused by other parts):\n Set(map(sort(x),x,eval(studentExpr)))\n\ninterpreted_answer (The student's answer, to be reused by other parts):\n cleanAnswer", "extendBaseMarkingAlgorithm": false, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Enter a spanning tree for the graph with edges {G2}:

", "answer": "{t2}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": "0.001", "failureRate": 1, "vsetRangePoints": "5", "vsetRange": ["0", "1"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "maxlength": {"length": "0", "partialCredit": "0", "message": ""}, "minlength": {"length": "0", "partialCredit": "0", "message": ""}, "valuegenerators": []}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}]}], "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}