The treewidth is a measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition.

I wrote Mathemaitca code to calculate Treewidth based on the Python code provided in the CodeGolf question.

I am now looking for a review in terms of approach, clarity, performance, etc.

eliminationWidth[graph_] := Module[{maxNeighbors = 0, currentGraph = graph, vertices, i, neighbors, newEdges},
 vertices = Union[Flatten[graph]];
 Do[
 neighbors = Union[
 Cases[currentGraph, {a_, i} :> a] ~Join~ 
 Cases[currentGraph, {i, b_} :> b]
 ];
 maxNeighbors = Max[Length[neighbors], maxNeighbors];
 newEdges = Select[Tuples[neighbors, 2], #[[1]] < #[[2]] &];
 currentGraph = Select[currentGraph, FreeQ[#, i] &] ~Join~ newEdges;
 , {i, Sort[vertices]}];
 maxNeighbors
 ]
treewidth[graph_] := Module[{vertices, minWidth, permutations, newGraph},
 vertices = Union[Flatten[graph]];
 minWidth = Length[vertices];
 permutations = Permutations[vertices];
 Do[
 newGraph = graph /. Thread[vertices -> perm];
 minWidth = Min[eliminationWidth[newGraph], minWidth];
 , {perm, permutations}];
 minWidth
 ]
(* Test cases *)
testCases = {
 {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {3, 5}},
 {{0, 1}, {0, 2}, {1, 2}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {3, 4}, {4, 6}, {4, 7}, {5, 6}, {6, 7}}
};
expectedResults = {1, 2};
(* Run tests *)
Do[
 result = treewidth[testCases[[i]]];
 Print["Test case ", i, ": Expected ", expectedResults[[i]], ", Got ", result, 
 If[result == expectedResults[[i]], " ✓", " ✗"]];
 , {i, Length[testCases]}]

The treewidth is a measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition.

I wrote Mathematica code to calculate Treewidth based on the Python code provided in the CodeGolf question.

I am now looking for a review in terms of approach, clarity, performance, etc.

eliminationWidth[graph_] := Module[{maxNeighbors = 0, currentGraph = graph, vertices, i, neighbors, newEdges},
 vertices = Union[Flatten[graph]];
 Do[
 neighbors = Union[
 Cases[currentGraph, {a_, i} :> a] ~Join~ 
 Cases[currentGraph, {i, b_} :> b]
 ];
 maxNeighbors = Max[Length[neighbors], maxNeighbors];
 newEdges = Select[Tuples[neighbors, 2], #[[1]] < #[[2]] &];
 currentGraph = Select[currentGraph, FreeQ[#, i] &] ~Join~ newEdges;
 , {i, Sort[vertices]}];
 maxNeighbors
 ]
treewidth[graph_] := Module[{vertices, minWidth, permutations, newGraph},
 vertices = Union[Flatten[graph]];
 minWidth = Length[vertices];
 permutations = Permutations[vertices];
 Do[
 newGraph = graph /. Thread[vertices -> perm];
 minWidth = Min[eliminationWidth[newGraph], minWidth];
 , {perm, permutations}];
 minWidth
 ]
(* Test cases *)
testCases = {
 {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {3, 5}},
 {{0, 1}, {0, 2}, {1, 2}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {3, 4}, {4, 6}, {4, 7}, {5, 6}, {6, 7}}
};
expectedResults = {1, 2};
(* Run tests *)
Do[
 result = treewidth[testCases[[i]]];
 Print["Test case ", i, ": Expected ", expectedResults[[i]], ", Got ", result, 
 If[result == expectedResults[[i]], " ✓", " ✗"]];
 , {i, Length[testCases]}]

The treewidth is a measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition.

I wrote Mathemaitca code to calculate Treewidth based on the Python code provided in the CodeGolf question.

I am now looking for a review in terms of approach, clarity, performance, etc.

eliminationWidth[graph_] := Module[{maxNeighbors = 0, currentGraph = graph, vertices, i, neighbors, newEdges},
 vertices = Union[Flatten[graph]];
 Do[
 neighbors = Union[
 Cases[currentGraph, {a_, i} :> a] ~Join~ 
 Cases[currentGraph, {i, b_} :> b]
 ];
 maxNeighbors = Max[Length[neighbors], maxNeighbors];
 newEdges = Select[Tuples[neighbors, 2], #[[1]] < #[[2]] &];
 currentGraph = Select[currentGraph, FreeQ[#, i] &] ~Join~ newEdges;
 , {i, Sort[vertices]}];
 maxNeighbors
 ]
treewidth[graph_] := Module[{vertices, minWidth, permutations, newGraph},
 vertices = Union[Flatten[graph]];
 minWidth = Length[vertices];
 permutations = Permutations[vertices];
 Do[
 newGraph = graph /. Thread[vertices -> perm];
 minWidth = Min[eliminationWidth[newGraph], minWidth];
 , {perm, permutations}];
 minWidth
 ]
(* Test cases *)
testCases = {
 {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {3, 5}},
 {{0, 1}, {0, 2}, {1, 2}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {3, 4}, {4, 6}, {4, 7}, {5, 6}, {6, 7}}
};
expectedResults = {1, 2};
(* Run tests *)
Do[
 result = treewidth[testCases[[i]]];
 Print["Test case ", i, ": Expected ", expectedResults[[i]], ", Got ", result, 
 If[result == expectedResults[[i]], " ✓", " ✗"]];
 , {i, Length[testCases]}]

The treewidth is a measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition.

I wrote Mathemaitca code to calculate Treewidth based on the Python code provided in the CodeGolf question.

I am now looking for a review in terms of approach, clarity, performance, etc.

eliminationWidth[graph_] := Module[{maxNeighbors = 0, currentGraph = graph, vertices, i, neighbors, newEdges},
 vertices = Union[Flatten[graph]];
 Do[
 neighbors = Union[
 Cases[currentGraph, {a_, i} :> a] ~Join~ 
 Cases[currentGraph, {i, b_} :> b]
 ];
 maxNeighbors = Max[Length[neighbors], maxNeighbors];
 newEdges = Select[Tuples[neighbors, 2], #[[1]] < #[[2]] &];
 currentGraph = Select[currentGraph, FreeQ[#, i] &] ~Join~ newEdges;
 , {i, Sort[vertices]}];
 maxNeighbors
 ]
treewidth[graph_] := Module[{vertices, minWidth, permutations, newGraph},
 vertices = Union[Flatten[graph]];
 minWidth = Length[vertices];
 permutations = Permutations[vertices];
 Do[
 newGraph = graph /. Thread[vertices -> perm];
 minWidth = Min[eliminationWidth[newGraph], minWidth];
 , {perm, permutations}];
 minWidth
 ]
(* Test cases *)
testCases = {
 {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {3, 5}},
 {{0, 1}, {0, 2}, {1, 2}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {3, 4}, {4, 6}, {4, 7}, {5, 6}, {6, 7}}
};
expectedResults = {1, 2};
(* Run tests *)
Do[
 result = treewidth[testCases[[i]]];
 Print["Test case ", i, ": Expected ", expectedResults[[i]], ", Got ", result, 
 If[result == expectedResults[[i]], " ✓", " ✗"]];
 , {i, Length[testCases]}]