KnapsackTest package

A subpackage for FusionAtlas v0.
October 10, 2008, Scott Morrison

Introduction

---text goes here---

Implementation

Start of package

Specify package dependencies:

BeginPackage["FusionAtlas`KnapsackTest`",{"FusionAtlas`","FusionAtlas`Bigraphs`","FusionAtlas`Debugging`"}];

Usage messages

KnapsackTest::usage="";

Internals

Begin["`Private`"];

KnapsackableQ[x1_,x2_,Y_List]:=KnapsackableQ[x1,x2,Reverse[Sort[Y]],(10^(-3))]
KnapsackableQ[x1_,x2_,Y_List,ϵ_]:=Module[{x=x1 x2,Nx=N[x1 x2],NY=N[Y],i,iterators,result=False,count=0},
iterators=Table[{i[j],If[j==Length[Y],Ceiling[Max[0,((Nx-Sum[i[k]NY[[k]],{k,1,j-1}])/(NY[[j]]))-0.1]],0],If[Y[[j]]==1,If[Abs[N[x1-x2]]<(10^(-3)),1,0],Floor[((Nx-Sum[i[k]NY[[k]],{k,1,j-1}])/(NY[[j]]))+0.1]]},{j,1,Length[Y]}];
Do[If[(Abs[Nx-Sum[i[j]NY[[j]],{j,1,Length[Y]}]]<ϵ),DebugPrint["Checking exactly: ",Table[i[j],{j,1,Length[Y]}]];
If[Abs[N[π+x-Sum[i[j]Y[[j]],{j,1,Length[Y]}],30]-π]<(10^(-25)),
DebugPrint["success!"];
result=True;Break[],
DebugPrint["failure!"];
]],Evaluate[Sequence@@iterators]];
result
]

ProductsKnapsackableQ[Y_List]:=Module[{result=True},
Do[If[!(result=KnapsackableQ[Y[[i]],Y[[j]],Y]),Break[]],{i,1,Length[Y]},{j,1,Length[Y]}];
result
]

BipartiteProductsKnapsackableQ[evens_List,odds_List]:=
Module[{result=True},
If[result,DebugPrint["Knapsacking odds*odds"];Do[If[!(result=KnapsackableQ[odds[[i]],odds[[j]],evens]),Break[]],{i,1,Length[odds]},{j,1,i}]];
If[result,DebugPrint["Knapsacking evens*odds"];Do[If[!(result=KnapsackableQ[evens[[i]],odds[[j]],odds]),Break[]],{i,1,Length[evens]},{j,1,Length[odds]}]];
If[result,DebugPrint["Knapsacking evens*evens"];Do[If[!(result=KnapsackableQ[evens[[i]],evens[[j]],evens]),Break[]],{i,1,Length[evens]},{j,1,i}]];
result
]

KnapsackTest[g_GradedBigraph]:=KnapsackTest[g]=Module[{dimensions=DimensionsByDepth[g],evens,odds},
evens=Sort[Flatten[Table[dimensions[[i]],{i,1,GraphDepth[g]+1,2}]]];
odds=Sort[Flatten[Table[dimensions[[i]],{i,2,GraphDepth[g]+1,2}]]];
BipartiteProductsKnapsackableQ[evens,odds]
]

End

End[];

End of package

EndPackage[];